Thread: greatest common divisor

ok i'm trying to do 2 proofs for gcd

show that if ax + by =1 then gcd(a,b)=1

and

gcd(a,a+k) divides k

just need a little hint on where to start
thanks

Originally Posted by action259

ok i'm trying to do 2 proofs for gcd

show that if ax + by =1 then gcd(a,b)=1

Suppose c>1 is the gcd(a,b), then c divides (ax+by), but c does not
divide 1, a contradiction.

and

gcd(a,a+k) divides k

let c be the gcd(a, a+k), then by definition c divides a, and c divides a+k.

RonL