# Prove pseudoprime $N$ and base a must be relatively prime.

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.

-
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

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.

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

-

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

-
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