# Thread: Greatest common divisor proofs

1. ## Greatest common divisor proofs

Here are some GCD questions I am struggling with:

1. Prove that, for a,n positive integers:
(a) n is divisible by gcd(a,a+n). (hint use the division identity M=aq+r)
(b) Hence show that GCD(a,a+1)=1

2. Show that for a,b gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)

3. prove that, for a,b,c,x, y integers tha c=ax+by if and only if gcd(a,b) divides c

4. Prove that for a,b,x,y integers if ax+by=gcd(a,b), then x and y are relatively prime.

5. Prove that the product of any three consecutive integers is divisible by 6.

Any help much appreciated.

cheers
Cabouli

2. Originally Posted by Cabouli
:
1. Prove that, for a,n positive integers:
(a) n is divisible by gcd(a,a+n). (hint use the division identity M=aq+r)
(b) Hence show that GCD(a,a+1)=1
Let $d=(a,a+n)$ it means $d|a,d|(a+n)$ so $d|((a+n)-a)\implies d|n$.
2. Show that for a,b gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)
These are straight forward ( $a,b\not = 0$). If $d = (a,b) \text{ and }d' = (a,-b)$ then $d|a,d|b\implies d|a,d|(-b)$ so $d'|d$. However, $d'|a,d'|(-b)\implies d'|a,d'|b$ so $d|d'$ which means $d=d'$. Likewise for all the other ones.

3. prove that, for a,b,c,x, y integers tha c=ax+by if and only if gcd(a,b) divides c
If $ax+by=c$ let $d=(a,b)$ then LHS is divisible by $d$ so $d|c$. Now for conserve. We can write $ax+by=d$ since $d|c$ it means $de=c$ and so $a(xe) + b(ye) = de = c$.

4. Prove that for a,b,x,y integers if ax+by=gcd(a,b), then x and y are relatively prime.
You can write $(a/d)x+(b/d)y=1$, now it is clear that $(x,y)=1$.

5. Prove that the product of any three consecutive integers is divisible by 6.
We want to prove $6|x(x+1)(x+2)$. Notice that $(2,3)=1$ and $2\cdot 3 = 6$. Thus, it is sufficient to prove that $2|x(x+1)(x+2)\text{ and }3|x(x+1)(x+2)$. It is easy to see why that is true.