2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – IQ472 Jul 8 '12 at 0:00
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – IQ472 Jul 8 '12 at 0:54
  • $\begingroup$ $\(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$ $\endgroup$ – Bill Dubuque Jul 8 '12 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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