gcd's and modulus proof

Question

Suppose that $m \in \mathbb{N}$ and $\gcd (a^2 - a), m) = 1.$

(i) Prove that $1 + a + a^2 + ... + a^{\phi(m)-1} ≡ 0 \pmod m$

How can I go about solving this? I recognize that $\gcd(a^2 - a, m)$ can be written as $\gcd(a(a-1),m)$ but I am not sure if this helps.

Answer 1

Hint: LHS = $\frac {a^{\phi(m)}-1}{a-1}$.

Hint: Euler's Theorem states that if $\gcd(a,m)=1$, then $a^{\phi(m)} \equiv 1 \pmod{m}$.

Hint: If $\gcd(x,y) = 1$, then $x^{-1}$ modulo $y$ exists.

Answer 2

As $(a(a-1),m)=1,(a,m)=1$ so using Euler's Totient theorem, $a^{\phi(m)}\equiv1\pmod m\iff m\mid(a^{\phi(m)}-1)$

As $(a(a-1),m)=1,(a-1,m)=1\implies m\mid \frac{(a^{\phi(m)}-1)}{a-1}$ which is an integer as $(x-y)\mid (x^n-y^n)$ where $x,y,n$ are positive integers $x\ne y$

$\implies m\mid (1+a+a^2+\cdots+a^{\phi(m)-2}+a^{\phi(m)-1})$

Answer 3

Per André's comment, here is a proof avoiding explicit use of both inverses and cancellation:

$$\rm \begin{eqnarray}\rm\color{#0A0}{(a\!-\!1)^j}\!\! &=& 1\\ \rm \color{#C00}{a^k}\! &=& \color{#C00}1\end{eqnarray}\bigg\rbrace \Rightarrow\ a^{k-1}\!+\cdots+\!a\!+\!1 = \color{#0A0}{(a\!-\!1)^j} (a^{k-1}\!+\cdots+\!a\!+\!1) = (a\!-\!1)^{j-1} (\color{#C00}{a^k\!-\!1}) = 0$$

Above $\rm\:j,k\ge 1,\:$ and $\rm\: j = \phi(m) = k\:$ work for your special case.