Proving $\sum_{i=0}^{\phi(n)-1} a^i\equiv 0\pmod n$, where $\gcd(a,n)=\gcd(a-1,n)=1 $, from Euler's theorem

Question

If $\gcd(a,n)=\gcd(a-1,n)=1 $ Then: $$\sum_{i=0}^{\phi(n)-1} a^i\equiv 0\pmod n$$

I don’t know how to prove this result, i’ve just made some stuffs : $$\sum_{i=0}^{\phi(n)}(a^i)-a^{\phi(n)}= \sum_{i=0}^{\phi(n)-1}a^i$$ But i don’t where should i use this.

Answer 1

Note that $$(a-1)\sum_{i=0}^{\phi(n)-1}a^i=a^{\phi(n)}-1$$ Since $\gcd(a,n)=1$ we get $a^{\phi(n)}-1\equiv 0\pmod n$. As $\gcd(a-1,n)=1$ we may cancel $a-1$ from both sides: $$(a-1)\sum_{i=0}^{\phi(n)-1}a^i\equiv 0\pmod n\implies\sum_{i=0}^{\phi(n)-1}a^i\equiv0\pmod n$$