# gcd's and modulus proof

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.

-

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.

-
The main concern with these sums is determining whether division by $a-1$ is possible mod $m$. Here, we know $(a-1,m)=1$, so indeed it is possible. I do not see the point of the third hint. – peoplepower Feb 5 '13 at 0:30
@peoplepower That is the point of the third hint. The $a$ and $m$ are variables, to be replaced with something suitable. For example, if you are told the formula for $f'$, that tells you the formula for $g'$. – Calvin Lin Feb 5 '13 at 0:32
Ah, but the variable $a$ is already in use so it appears that you are saying that $a^{-1}$ itself is to be used. So if you had that hint first and said "if $(x,m)=1$, then $x^{-1}$ mod $m$ exists" I would have read it correctly. – peoplepower Feb 5 '13 at 0:36
@peoplepower :) That was intentional. OP should be thinking of how to solve the problem, and not just expecting to be spoon fed an answer. Your comment showed that you were thinking, and were very close to an answer. – Calvin Lin Feb 5 '13 at 0:40
I don't like to divide, multiplying is more fun. We have $(1-a)(1+a+\cdots+a^{\varphi(m)})=1-a^{\varphi(m)}$/ The right side is congruent to $0$, now cancellation does it. Same proof, no explicit mention of inverses. – André Nicolas Feb 5 '13 at 0:59

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})$

-

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.

-