# Thread: Simple proofs - need opinion/guidance

1. ## 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.

2. Originally Posted by gate13
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, $\displaystyle \text{gcd}(a,b)|a$ and $\displaystyle \text{gcd}(a,b)|b$. Thus, if $\displaystyle \text{gcd}(a,b) = a$, we have, in particular, that $\displaystyle 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?

3. ## 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.

4. Originally Posted by gate13
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)

5. ## Simple proofs - need opinion/guidance

Thanks again Jhevon. Looking at that now. Have a good now.