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.

  • 1
    If $N=1$ then $a^{N-1}=1$. This is certainly congruent to $1$ (modulo anything you like).2012-07-08

3 Answers 3

4

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.

  • 0
    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!2012-07-08
1

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

1

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$

  • 0
    $\(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$2012-07-08