How does one prove that $1 + a + a^2 + ... +a^{\phi(n)-1} = 0$ mod $n$ if $a$ and $a-1$ are both units mod n?

Question

If a has order $\phi(n)$, then this is easy, because (if n>=3) all units arise in pairs a and n-a.

However, the two conditions a and a-1 units do NOT imply that the order of a is $\phi(n)$, so we can't use that.

Let us look at mod 15, with phi(15) = 2*4 = 8

example 1: a = 8 and a-1 = 7 are both units and indeed for a=8 we get

8+4+2+1+8+4+2+1 = 15 +15 =0 mod 15

example 2: a= 14 and a -1 = 13 are both units and we get for a = 14

14 + 1 + 14 + 1 +14 + 1 +14 + 1 = 0 mod 15

non-example 1: a = 7 and a-1 =6 are NOT both units and for a =7 we get

7+4+13+1+7+4+13+1 = 25 + 25 = 5 mod 15

Answer 1

Euler's theorem asserts that every element $a$ which is coprime to $n$, i.e. which is a unit mod. $n$, satisfies $\:a^{\varphi(n)}\equiv 1\mod n$.

This does not mean the order of $a$ is $\varphi(n)$, only that it is a divisor of $\varphi(n)$.

Now, let's use the high school factorisation: $$0\equiv 1-a^{\varphi(n)}=(1-a)(1+a+a^2+\dots+a^{\varphi(n)-1}).$$ By hypothesis, $1-a$ is a unit mod. $n$, so this implies the second factor is congruent to $0$.

Answer 2

Let the sum be $S$. Then multiply by $a$. We get $$aS=\sum_{i=1}^{\phi(n)}a^i=a^{\phi(n)}+\sum_{i=1}^{\phi(n)-1}a^i =S,$$ since even if $a$ doesn't have order $\phi(n)$, we still know $a^{\phi(n)}=1$.

Then $(a-1)S=0$, and $a-1$ is a unit. Thus $S=0$.