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$


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.