Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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