Results 1 to 5 of 5

Math Help - Simple proofs - need opinion/guidance

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    34

    Simple proofs - need opinion/guidance

    Good day to all. I apologize for the lengthy post, but I am seeking an opinion on some proofs we have been asked to construct as well as guidance for one that has puzzled me. I have omitted the theorems and definitions used in order to avoid making the post heavier than it already is. I wanted something fairly solid before seeking any advice. Any opinion/suggestion will be greatly appreciated. Here they are:

    Question 1: if m\n, then m <= n (m, n are positive integers)
    Proof:

    if m\n then n = k.m for some positive integer k
    Then m = (n/k)
    if k = 1 then m = n
    if k > 1 then (n/k) < n i.e. m < n
    therefore m <= n (Q.E.D)

    Question2: Prove: Let a and b be positive integers, gcd(a; b) = a if and only if a \ b.
    Use direct proof for =>and contradiction method for <= .
    Proof:
    step1: (Direct proof)
    if gcd(a;b) then a belongs in the prime factorization of b
    then b = p1^s1 . p2^s2 . ... .pn^sn . a
    Let k = p1^s1 . p2^s2 . ... .pn^sn
    then b = k . a and a\b Q.E.D.

    step2: (By contradiction)
    We assume that a\b and that gcd(a;b)<>a
    Therefore there exists t (positive integer) such that gcd(a;b) = t.
    But t > a, i.e. t does not divide a.
    This contradicts our assumption that there exists an larger integer t such that gcd(a;b) = t since gcd(a;b)=t => t\a and t\b.
    Q.E.D

    Finally, this last question is the one that has puzzled me somewhat. I am searching for some guidance and not the answer (I know this is not complicated but I cannot seem to see the process).

    Question3:Use forward-backward method to prove: If a < 1 and b < 1, then ab + 1 > a + b.
    Last edited by gate13; January 23rd 2010 at 02:07 PM. Reason: Correction
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by gate13 View Post
    Good day to all. I apologize for the lengthy post, but I am seeking an opinion on some proofs we have been asked to construct as well as guidance for one that has puzzled me. I have omitted the theorems and definitions used in order to avoid making the post heavier than it already is. I wanted something fairly solid before seeking any advice. Any opinion/suggestion will be greatly appreciated. Here they are:

    Question 1: if m\n, then m <= n (m, n are positive integers)
    Proof:

    if m\n then n = k.m for some positive integer k
    Then m = (n/k)
    if k = 1 then m = n
    if k > 1 then (n/k) < n i.e. m < n
    therefore m <= n (Q.E.D)
    this is fine.

    Question2: Prove: Let a and b be positive integers, gcd(a; b) = a if and only if a \ b.
    Use direct proof for =>and contradiction method for <= .
    Proof:
    step1: (Direct proof)
    if gcd(a;b) then a belongs in the prime factorization of b
    then b = p1^s1 . p2^s2 . ... .pn^sn . a
    Let k = p1^s1 . p2^s2 . ... .pn^sn
    then b = k . a and a\b Q.E.D.
    hmm, don't like this. if b = a then it doesn't really work, since none of the p's can be 1.

    it's a lot simpler than you are making it. by definition, \text{gcd}(a,b)|a and \text{gcd}(a,b)|b. Thus, if \text{gcd}(a,b) = a, we have, in particular, that a|b.

    step2: (By contradiction)
    We assume that a\b and that gcd(a;b)<>a
    Therefore there exists t (positive integer) such that gcd(a;b) = t.
    But t > a, i.e. t does not divide a.
    This contradicts our assumption that there exists an larger integer t such that gcd(a;b) = t since gcd(a;b)=t => t\a and t\b.
    Q.E.D
    correct. you did phrase it weird though. and you jumped to t > a with little justification. i'd clean it up a bit.

    Finally, this last question is the one that has puzzled me somewhat. I am searching for some guidance and not the answer (I know this is not complicated but I cannot seem to see the process).

    Question3:Use forward-backward method to prove: If a < 1 and b < 1, then ab + 1 > a + b.
    uh, what's the forward backward method?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    34

    Simple proofs - need opinion/guidance

    Thanks Jhevon for your response. I will make sure to clean up the the wording and order the thoughts in a more rigorous manner. As for the forward-backward method, I should have written direct proof. I apologize for that glaring oversight. Any help would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by gate13 View Post
    Thanks Jhevon for your response. I will make sure to clean up the the wording and order the thoughts in a more rigorous manner. As for the forward-backward method, I should have written direct proof. I apologize for that glaring oversight. Any help would be greatly appreciated.
    Hint: consider the product of (a - 1) and (b - 1)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    34

    Simple proofs - need opinion/guidance

    Thanks again Jhevon. Looking at that now. Have a good now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a few simple proofs
    Posted in the Calculus Forum
    Replies: 7
    Last Post: March 15th 2011, 07:23 PM
  2. Simple set proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 3rd 2011, 05:52 AM
  3. Replies: 3
    Last Post: March 7th 2010, 03:41 PM
  4. Simple linear algebra question - opinion needed
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 3rd 2010, 10:29 AM
  5. 'simple' proofs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 30th 2007, 01:12 PM

Search Tags


/mathhelpforum @mathhelpforum