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