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)
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.
p is an odd prime
1^k+2^k+3^k+....(p-1)^k = 0 mod p if p-1 doesnt divid k