Proof of Primality Testing

Question

I am learning some Cryptography and I came across this exercise where I have to make the following proof (translated from German, so I hope it is accurate).

Proof the following assertion: Let $n \in \mathbb{Z}$ be odd and $a \in \mathbb{Z}_n^*$. If $a^{\frac{n-1}{2}} \neq \pm 1 \mod n$ , then $n$ is a composite.

Now I don't really have any math background, so my proof goes as follows, but I am not sure if I really proofed the assertion:

Proof by contradiction. Assume that $n$ is a composite.

$$a^{\frac{n-1}{2}} \equiv 1 \mod n$$ $$\Rightarrow a^{\frac{n-1}{2}}\cdot a^{\frac{n-1}{2}} \equiv 1 \cdot 1 \mod n$$ $$\Rightarrow a^{n-1} \equiv 1 \mod n$$

Now since $a^{\varphi(n)} \equiv 1 \mod n$ for any finite group and with $\varphi$ being the Euler's totient function. But $\varphi(n) = n - 1$ if and only if $n$ is prime.

And I could do the same thing $a^{\frac{n-1}{2}} \equiv -1 \mod n$

Answer 1

Consider the contrapositive. Suppose p an odd prime and $a \in \mathbb{Z}_p^*$. Then $a^\frac{p-1}{2} \equiv \pm 1 \mod p$.

Hint. $(a^\frac{p-1}{2})^2 \equiv 1 \mod p$ since p is prime, i.e. $(a^\frac{p-1}{2} - 1)(a^\frac{p-1}{2}+1)$ is divisible by p.

Note on your proof:

The implication "A implies B" is false only when A is true and B is false, which we assume in a proof by contradiction, and not A is False and B is true.

If $a^{n-1} \equiv 1 \mod n$ for all $a \in \mathbb{Z}_p^*$, then n need not be prime, consider the composite number n = 561, $a \in \mathbb{Z}_{561}^*$ then $a^{560} \equiv 1 \mod 561$. These numbers are called Carmichael.

The euler-phi $\phi(n)$ is not the order of a, i.e. it is not the smallest such that $a^{\phi(n)} \equiv 1 \mod n$. Indeed, if n = 7, then $\phi(7) = 6$ and $2^3 \equiv 1 \mod 7$.