# Thread: prove this Highest Common Factor property

1. ## prove this Highest Common Factor property

(m,n)=(m+kn,n)

2. Hello,

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'

3. ## 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

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