# 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 $\displaystyle d=(a,a+n)$ it means $\displaystyle d|a,d|(a+n)$ so $\displaystyle 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 ($\displaystyle a,b\not = 0$). If $\displaystyle d = (a,b) \text{ and }d' = (a,-b)$ then $\displaystyle d|a,d|b\implies d|a,d|(-b)$ so $\displaystyle d'|d$. However, $\displaystyle d'|a,d'|(-b)\implies d'|a,d'|b$ so $\displaystyle d|d'$ which means $\displaystyle 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 $\displaystyle ax+by=c$ let $\displaystyle d=(a,b)$ then LHS is divisible by $\displaystyle d$ so $\displaystyle d|c$. Now for conserve. We can write $\displaystyle ax+by=d$ since $\displaystyle d|c$ it means $\displaystyle de=c$ and so $\displaystyle 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 $\displaystyle (a/d)x+(b/d)y=1$, now it is clear that $\displaystyle (x,y)=1$.

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