1. ## Primitive roots

Use primitive roots to prove that

1^100 + 2^100 + ... +(p-1)^100 = 0 (mod p)

for all except five primes p. What are these primes?

2. When 100/(p-1)=t in Z

then:

1^100 + 2^100 + ... +(p-1)^100 = -1(mod p)

So, the primes are:
2,3,5,11, and... 101

================================

Let $\displaystyle p$ be prime number:

$\displaystyle 1^n+2^n+...+(p-1)^n\equiv 0(mod p)$ if $\displaystyle (p-1)\nmid{n}$

or:

$\displaystyle 1^n+2^n+...+(p-1)^n\equiv -1(mod p)$ if $\displaystyle (p-1)\mid{n}$

Proof:

Suppose $\displaystyle (p-1)\mid{n}$ so to every $\displaystyle t$ witch is co-prime to $\displaystyle p$ :

$\displaystyle t^n=(t^{p-1})^{\frac{n}{p-1}}\equiv 1^{\frac{n}{p-1}}\equiv 1(modp)$

Hence, $\displaystyle 1^n+2^n+...+(p-1)^n\equiv 1+1+...+1=p-1=-1(modp)$

Now, suppose $\displaystyle (p-1)\nmid{n}$ , and $\displaystyle r$ primitive root of $\displaystyle p$ .

hence, $\displaystyle r,r^2,...,r^{p-1}$ congruent modulo $\displaystyle p$ to $\displaystyle 1,2,...,(p-1)$ in some order.

Prove by yourself now that: $\displaystyle r^n,r^{2n},...,r^{n(p-1)}$ is also system of congruent modulo $\displaystyle p$.

Hence:

$\displaystyle 1^n+2^n+...+(p-1)^n\equiv r^n+r^{2n}+...+r^{n(p-1)}\equiv 1+2+...+(p-1)=\frac{p(p-1)}{2}\equiv 0(modp)$

3. For $\displaystyle 1^n+2^n+...+(p-1)^n\equiv 0 (\bmod p)$ if $\displaystyle (p-1)\nmid{n}$, you should also add that $\displaystyle p$ is odd.