Prove: If $p$ is prime and $ (a,p)=1 $, then $\ 1 + a + a^2 + ... + a^{p-2}=0$(mod $p$) Prove: If $p$ is prime and $ (a,p)=1 $, then $\ 1 + a + a^2 + ... + a^{p-2}≡0 \pmod p$
As an example, for $a=2$ and $p=5$, then:
$$1+2+2^2+2^3=1+2+4+8=15≡0 \pmod 5$$
This can also be written as:
$$1 \pmod 5 + 2 \pmod 5 + 4 \pmod 5 + 3 \pmod 5 ≡ 10 \pmod 5 ≡ 0 \pmod 5$$
Which is a complete residue system (mod 5). This is where I'm stuck. At a glance it looks like fermat's little theorem, but it seems like I have to prove this creates a CRS for any $a$ and any $p$. How can I proceed? Thanks!
 A: If $p=2$, then $a^{p-2}=a^0=1$, so in this case is false, because $1\not\equiv 0(mod \ 2)$.
If $p\neq 2$, then $1+a+\dots+ a^{p-2}=\frac{a^{p-1}-1}{a-1}$. From the fermat theorem, if $(a,p)=1$, then $a^{p-1}\equiv 1 (mod\ p)$ (if this doesn't happen, maybe the $p$ factor of $a^{p-1}-1$ will dissapear), so you need now to see that $p\not\mid a-1$, because if not, for example if $p=7$ and $a=8$, you will have 
$$1+8+\dots+8^5\equiv 6\not\equiv 0 (mod\ 7)$$
If $p\neq 2$ and $(a(a-1),p)=1$, then it's true.
A: Notice that Fermat's Little Theorem tells us that if $p$ is prime and $\gcd(a,p)=1$, then
$$a^{p-1} \equiv 1 \bmod p$$
Clearly $a^{p-1}-1 \equiv 0 \bmod p$. Recall that $x^n-1 = (x-1)(1 + x + x^2 + \cdots + x^{n-1})$, and so
$$a^{p-1}-1 = (a-1)(1+a+a^2 + \cdots + a^{p-2})$$
We know that $a^{p-1}-1 \equiv 0 \bmod p$, i.e. $p$ divides $a^{p-1}-1$. Since $p$ is prime, it follows that either $p$ divides $a-1$ or that $p$ divides $1+a+a^2 + \cdots + a^{p-2}$.
In summary: if $\gcd(a,p)=\gcd(a-1,p)=1$ then $p$ will divide $1+a+a^2 + \cdots + a^{p-2}$.
A: Hint: $\mathbb{Z}_p = \mathbb{Z}/p\mathbb{Z}$ is a field, and, in this field,
$$
(a-1)(1+a+a^2 + \ldots + a^{p-2}) = (a^{p-1}-1)
$$
A: If $a\equiv1\pmod p,$ $$\sum_{r=0}^{p-2}a^r\equiv\sum_{r=0}^{p-2}1^r\equiv p-1\equiv-1\pmod p$$
Else  $(a-1,p)=1$
$$\sum_{r=0}^{p-2}a^r=\dfrac{a^{p-1}-1}{a-1}$$
Now by Fermat's Little Theorem $a^{p-1}-1\equiv0\pmod p$
As $(a-1,p)=1$ $$\dfrac{a^{p-1}-1}{a-1}\equiv0\pmod p$$
A: All the other methods written work perfectly.
To start notice one thing. The statement holds for prime numbers such that $p>2$ (indeed if $p=2$ we cannot have $1\equiv 0 \pmod p$).
Now we will build the solution step by step :
We begin with : $1\equiv 1 \pmod p$.
Then $a\equiv 1 \pmod p$ because $\gcd(a,p)=1$.
Now for $k\in \{2,...,p-2\}$ we prove that if $\gcd(a,k)=1$ then for all the $k$ we have $\gcd(a^k,p)=1$.
We start with $k=2$. By Bachet-Bézout's theorem we can write : $1=(au+pv)$ with $u,v\in \mathbb{Z}$. Multiplying by itself we find $1=a^2U+pK$ with $U,K\in \mathbb{Z}$. So we conclude that $\gcd(a^2,p)=1$. We repeat the process until $k=p-2$. Then we have $\gcd(a^k,p)=1$.
By summing we obtain : $1+...+a^{p-2}\equiv p-1 \equiv -1\pmod p$ but it's a geometric sequence so $\frac{a^{p-1}-1}{a-1}=1+...+a^{p-2}$. So we have $a^{p-1}\equiv 1-a+1\pmod p$ with $a\equiv 1 \pmod p$. We conclude by Fermat Little Theorem with $a^{p-1} \equiv 1 \pmod p$.
