# Thread: gcd proofs

1. ## gcd proofs

Prove that for every n, gcd(n+1, n^2-n+1) is either 1 or 3.

I'm having a lot of difficulty with some of these proofs. I'm not quite sure where to begin...

First, If (a,b)=d, then prove (a/d, b/d)=1 (where a/d is a fraction... I can't figure out how to get the cool math symbols in here like everyone else!)
So far I have: d/a (d divides a) and d/b, so a=dv and b=dw where v,w belong to the set of intergers. Then I can plug that in, so (a/d, b/d) becomes (v,w) but that doesn't really get me anywhere... help?

Also, If (a,c)=1 and (b,c)=1, prove that (ab,c)=1.
So far I have 1=av+cw for some v,w belonging to the set of intergers. Similarly, 1=bx+cz, but that's as far as I've been able to get.

2. You can express the GCD as $\displaystyle ua+vb = d$. More over, it is the smallest positive integer of this form.
Divide each side by d $\displaystyle u\frac{a}{d}+v\frac{b}{d} = 1$ This looks like the expression of a GCD. You can be sure it is because 1 is the smallest positive integer you can get.
For number 2 you can use the fact that they have no common factors.
For the "cool" writting, you should learn Latex script. Double-click on the things other people wrote to see how it is. With some time you should learn.

3. Originally Posted by pirouette
Also, If (a,c)=1 and (b,c)=1, prove that (ab,c)=1.
So far I have 1=av+cw for some v,w belonging to the set of intergers. Similarly, 1=bx+cz, but that's as far as I've been able to get.
$\displaystyle 1 = (av+cw)(bx+cz) = ab(vx) + c(avz + bwx + cwz)$

4. Thanks to both of you!

5. Ok, I have one more that I'm having a lot of trouble with.

Prove that for every n, gcd(n+1, n^2-n+1) is either 1 or 3.

6. Look at $\displaystyle n \mod{3}$:

Suppose $\displaystyle n \equiv 0 \mod{3}$, then $\displaystyle (n+1,n^2-n+1) = (0+1,0^2-0+1) = (1,1) = 1$

Suppose $\displaystyle n \equiv 1 \mod{3}$, then $\displaystyle (n+1,n^2-n+1) = (1+1,1^2-1+1) = (2,1) = 1$

Suppose $\displaystyle n \equiv 2 \mod{3}$, then $\displaystyle (n+1,n^2-n+1) = (2+1,2^2-2+1) = (3,3) = 3$

Hence either $\displaystyle 1$ or $\displaystyle 3$.

7. Originally Posted by pirouette
Note that if $\displaystyle a,b$ are positive integers then $\displaystyle \gcd(a+b,b)=\gcd(a,b)$
Now $\displaystyle n^2 - n + 1 = n^2 + 2n + 1 - 3n = (n+1)^2 - 3n$
Thus, $\displaystyle \gcd(n+1, (n+1)^2 - 3n) = \gcd(n+1, - 3n) = \gcd(n+1, - 3n + 3(n+1)) = \gcd(n+1, 3)$
8. Directly follows from the observation: $\displaystyle (n^2 - n + 1) - (n-2)(n+1) = 3$