# prove this Highest Common Factor property

• May 22nd 2008, 06:56 AM
szpengchao
prove this Highest Common Factor property
(m,n)=(m+kn,n)
• May 22nd 2008, 09:53 AM
Moo
Hello,

Quote:

Originally Posted by szpengchao
(m,n)=(m+kn,n)

Let d=gcd(m,n) and d'=gcd(m+kn,n)

1st part
d divides m.
It also divides n.
So it divides every linear combination of the two, and in particular m+kn.

Therefore, d divides both m+kn and n.
We can conclude that d divides d' (because d' is the highest common factor)

2nd part
d' divides n.
d' also divides m+kn.
So it divides every linear combination of the two, and in particular m+kn+(-k)n=m.

Therefore, d' divides both m and n.
We can conclude that d' divides d.

----> d=d'
• May 22nd 2008, 09:55 AM
szpengchao
can u prove this
p is an odd prime
prove:

1^k+2^k+3^k+....(p-1)^k = 0 mod p if p-1 doesnt divid k
• May 22nd 2008, 02:27 PM
ThePerfectHacker
Quote:

Originally Posted by szpengchao
p is an odd prime
prove:

1^k+2^k+3^k+....(p-1)^k = 0 mod p if p-1 doesnt divid k

Hint: \$\displaystyle p\$ has a primitive root \$\displaystyle r\$ note, \$\displaystyle r,r^2,...,r^p\$ ranges over \$\displaystyle 1,2,...,(p-1)\$. Now use geometric series.