Primality test for $n$ 
Assume $a,n\in\mathbb{N}$ such that $\gcd{(a,n)}=1$. We say $n$ is prime if $a^{n-1}\equiv 1\mod{n}$ and $a^x\not\equiv1\mod{n}$ for any divisor $x$ of $n-1$.

I am presented with the following proof but there are jumps within it that I don't understand.

Proof: Suppose $\gcd{(a,n)} = 1$. Let $d$ be the order of $a$ modulo $n$, i.e. the smallest $x$ such that $a^x\equiv1\mod{n}$. Then $d\mid n-1$. We write $n-1=sd+r$ where $0\le r<d$. Hence $$1\equiv a^{n-1} \equiv a^{sd+r} \equiv a^r\mod{n}$$
Since $d\mid n-1$, we know $d\mid\varphi(n)$. Since $a^{\varphi(n)}\equiv 1\mod{n}$ we note that $d=n-1$. Also $d\mid\varphi(n) \le n-1\implies \varphi(n)=n-1\implies n$ is prime.

Questions:


*

*How does $d\mid n-1$?

*If $d\mid n-1$ why do we write $n-1=sd+r$, surely $r=0$?

*What relevance does showing $1\equiv a^r\mod{n}$ have?

*How does $d\mid n-1\implies d\mid \varphi(n)$?

*How does $a^\varphi(n)\equiv 1\mod{n}\implies d=n-1$?

*Can we always say that $\varphi(n)\le n-1$?

*Is it true to say if $\varphi(n)=n-1$ then $n$ is prime?

 A: *

*For $1,2,3$ :
Let $n-1=sd+r$ where $0 \leq r <d$ .Then as you noted it follows that :
$$1 \equiv a^{n-1} \equiv \left (a^d \right )^s \cdot a^r \equiv a^r \pmod{n}$$ and so :
$$a^r \equiv 1 \pmod{n}$$ But $d$ is the smallest non-zero number such that :
$$a^d \equiv 1 \pmod{n}$$ so because $r<d$ it must follow that $r=0$ and then $n-1=sd$ or $d \mid n-1$ .

*

*For $4$ :

It's known from Euler's theorem that $$a^{\phi(n)} \equiv 1 \pmod{n}$$ so now applying the same argument as above (with $\phi(n)=sd+r$ ) it follows that also $d \mid \phi(n)$ .

*

*For $5$ :

You know that $a^x \not\equiv 1 \pmod{n}$  for $x$ a divisor of $n-1$ (except $x=n-1$ of course ) .
But $a^d \equiv 1 \pmod{n}$ and $d \mid n-1$ and so it must follow that $d=n-1$ and because $ d \mid \phi(n)$ it follows that $n-1 \mid \phi(n)$ .

*

*For $6,7$ :

Do you know the definition of $\phi(n)$ ? :

$\phi(n)$ represents the number of positive integers prime with $n$ and less than $n$ .

There are exactly $n-1$ numbers less than $n$ so $$\phi(n) \leq n-1$$ is a direct consequence of the definition .
The equality is achieved when all the numbers less than $n$ are prime with $n$ which can only happen when $n$ is prime because :
If for example $q \mid n$ with $q$ prime then if $q<n$ we would have $(n,q) \neq 1$ so we can't have $\phi(n)=n-1$ .This means that $n=q$ is a prime number .
A: Assertion 1 is false in general, except if $n$ is a prime number (in the ordinary sense). The definition here given is that of a (Fermat) pseudoprime relative to base $a$ (first condition) $+$ an extra condition on the order..
A counter-example: $\gcd(3,8)=1$, but the order of $3$ mod. $8$ est $2$ – not a divisor of $7$.
