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.

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|improve this question
2  
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
1  
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
add comment

3 Answers 3

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|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
add comment

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|improve this answer
add comment

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|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
add comment

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.