# Math Help - 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 $ua+vb = d$. More over, it is the smallest positive integer of this form.
Divide each side by d $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.
$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 $n \mod{3}$:

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

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

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

Hence either $1$ or $3$.

7. Originally Posted by pirouette
Note that if $a,b$ are positive integers then $\gcd(a+b,b)=\gcd(a,b)$
Now $n^2 - n + 1 = n^2 + 2n + 1 - 3n = (n+1)^2 - 3n$
Thus, $\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: $(n^2 - n + 1) - (n-2)(n+1) = 3$