hmm, don't like this. if b = a then it doesn't really work, since none of the p's can be 1.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 <= .
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.
it's a lot simpler than you are making it. by definition, and . Thus, if , we have, in particular, that .
correct. you did phrase it weird though. and you jumped to t > a with little justification. i'd clean it up a bit.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.
uh, what's the forward backward method?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.