Thread: gcd proofs:

I'm kinda just starting out in this sort of stuff, and i'm rather confused. The professor assigned us to prove these. Not really sure how to start it to be honest. If I could see how these things get solved I think i'll understand it much better.

1. If a and b are 2 positive integers show that gcd(a,b) = gcd(a - b, b)

2. if a and b are 2 positive integers show taht gcd(a,b) = gcd(a, a +b)

3. show that gcd(fn,fn+1) = 1 for all natural numbers n.

Originally Posted by Mr.Obson

1. If a and b are 2 positive integers show that gcd(a,b) = gcd(a - b, b)

Say a > b >0 . Let gcd(a,b) = d. Now we compute gcd(a - b, b), we claim d is a common divisor. Indeed, d|(a-b) because d|a and d|b. Now we claim that if d' is a larger divisor then d'|(a-b) and d'|b implies d'|(a-b + b) thus d'|a, so d'|a, so d' is a common divisor to a and b so d' <= d.

2. if a and b are 2 positive integers show taht gcd(a,b) = gcd(a, a +b)

Same ideal

3. show that gcd(fn,fn+1) = 1 for all natural numbers n.

Use induction.
The inductive step if f_n+1 = f_n + f_n-1
But gcd(f_n,f_n-1) = 1 so gcd (f_n+1,f_n)=1 by Euclid's algorithm .

wow, thx it all makes a lot more sense now