gcd proofs

**pirouette** · January 19th 2009, 01:35 PM

Edited to add:
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.

**vincisonfire** · January 19th 2009, 01:49 PM

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.

**Isomorphism** · January 19th 2009, 04:51 PM

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)$

**pirouette** · January 19th 2009, 05:57 PM

Thanks to both of you!

**pirouette** · January 20th 2009, 07:32 PM

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.

**chiph588@** · January 20th 2009, 08:50 PM

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$ .

**ThePerfectHacker** · January 20th 2009, 09:15 PM

Originally Posted by pirouette

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

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)$
And so it is 1 or 3.

**Isomorphism** · January 20th 2009, 09:18 PM

Directly follows from the observation: $(n^2 - n + 1) - (n-2)(n+1) = 3$

Thread: gcd proofs

LinkBack

Thread Tools

Display

gcd proofs

Similar Math Help Forum Discussions

proofs

lim sup and lim inf proofs

More Proofs

Proofs

Sequence Convergence Proofs vs. Continuity Function Proofs

Search Tags