Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
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
2  
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})$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.