Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I would really appreciate some hints. Sorry if this is too easy. Thanks sincerely. Also, technically this is not homework but it is a problem from a textbook. Prove:

$a^{N-1} \not \equiv 1($mod$ \ N)$ if the gcd$(a,N)>1$. Where $a,N \in \mathbb{Z}$ and $N \geq 1$.

I have tried by contradiction as follows:

Suppose $a^{N-1} \equiv 1 $ mod$(N)$. Then,

$$ \begin{align} a^{N} & \equiv a \ \text{mod}(N) \iff \\ cN & = a^{N} - a, \ \text{for some} \ c \in \mathbb{Z} \end{align} $$

But I can't seem to get a contradiction. It looks like I could try two things here 1) trying to the right side as $a(a^{N-1}-1)$ or rewriting the equation as $a = \lambda a+ \mu N$ for some $\lambda,\mu \in \mathbb{Z}$.

Similarly, I have tried beginning with gcd$(a,N)>1$, so $$ \begin{align} \text{gcd}(a,N)= d & = \lambda a+ \mu N \ \text{for some} \ \lambda,\mu \in \mathbb{Z} \\ \mu N & = d - \lambda a \iff \\ N& | d - \lambda a \iff \\ \lambda a & \equiv d \ (\text{mod}N) \end{align} $$ Which looks like a rabbit trail.

share|cite|improve this question
You want $N\ge 2$. – André Nicolas Jul 7 '12 at 23:53
are you saying that bc if $N = 1$ then the gcd$(a,N) = 1$? – IQ472 Jul 8 '12 at 0:01
If $N=1$ then $a^{N-1}=1$. This is certainly congruent to $1$ (modulo anything you like). – André Nicolas Jul 8 '12 at 0:04
up vote 4 down vote accepted

Suppose that $\gcd(a,N)=d>1$. Then $d\mid a$ and $d\mid N$. Because $d\mid a$, we have $d\mid a^s$ for any $s\geq 1$. Thus $d\mid \gcd(a^s,N)$ for any $s\geq 1$, so that for any integers $x$ and $y$, $$d\mid xa^s+yN.$$ But the statement that $a^{N-1}\equiv 1\bmod N$ is just that there is an integer $y$ such that $$a^{N-1}+yN=1,$$ so when $N\geq 2$ we would have to have $d\mid 1$, which is a contradiction.

share|cite|improve this answer
O I totally get it! I was just beginning to think of ways to use the fact if d divided a, then d divides a*...*a. Thanks! – IQ472 Jul 8 '12 at 0:00

We need $N \ge 2$.

Suppose that $d$ divides $a$ and $N$, where $d\gt 1$. Then $d$ divides $a^{N-1}$.

If $N$ divides $a^{N-1}-1$, then $d$ divides $a^{N-1}-1$. But since $d$ divides $a^{N-1}$, this implies that $d$ divides $1$. That is impossible, since $d\gt 1$.

share|cite|improve this answer

Hint $\rm\ p\:|\:a,n\:$ and $\rm\:p\:|\:n\:|\:a^{n-1}\!-1\:\Rightarrow\:p\:|\:1\:\Rightarrow\Leftarrow$

More generally: $\rm\:(a,n) > 1\:\Rightarrow\:a\,$ is a zero-divisor mod $\rm\,n,\:$ and $\rm\:a^k \equiv 1\:\Rightarrow\:a\,$ is a unit.
But a zero-divisor $\rm\, a\,$ is never a unit in any ring since

$$\rm\qquad\quad 1=\color{#0A0}{\bar a\,a},\ \,0\,=\,\color{#C00}{ab},\ a,b\ne 0 \\ \Rightarrow\ \ b = (\color{#0A0}{\bar a\,a})b = \bar a\,(\color{#C00}{ab}) = 0$$

share|cite|improve this answer
Thanks so much... – IQ472 Jul 8 '12 at 0:09
I'm not sure if I understand, when you say, $(a,n)>1$ implies a is a zero-divisor mod n. I'm thinking of particular numbers. Say, (a,n)=(8,14). What does zero divisor mean here? It's not $[8]_{14}=0$. Right? – IQ472 Jul 8 '12 at 0:54
$\(8,14) = 2,\,$ and $\rm\,mod\ 14\!:\ 2\cdot 7 \equiv 0,\ \ 2,7\not\equiv 0,\: $ so $\,2\,$ is a zero-divisor, so it is not a unit (invertible). Note if $\rm\:k>0\:$ and $\rm\,a^k\equiv 1\,$ that $\rm\:a\,a^{k-1}\equiv 1\:$ so $\rm\,a\,$ is a unit (invertible), i.e. a divisor of $1$. $\qquad$ – Bill Dubuque Jul 8 '12 at 1:46

Your Answer


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.