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 $p$ be prime number:

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

or:

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

Proof:

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

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

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

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

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

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

Hence:

$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 $1^n+2^n+...+(p-1)^n\equiv 0 (\bmod p)$ if $(p-1)\nmid{n}$, you should also add that $p$ is odd.