Proving a natural odd number n is prime based on constraints on order of numbers mod n

Question

Let n be an odd natural (positive) number such that $3 \nmid n$.

It is further given that:

1. $3^{\frac{n-1}{2}} \equiv -1 \pmod{n}$
2. The order of 9 modulo n is $\frac{n-1}{2}$

Prove that n must be prime.

---

I went about it in the following way, which seems to work, however I'm not making full use of both given facts which makes me suspect I got something wrong or otherwise the problem statement is redundant.

My solution:

we know n is odd, and therefore n-1 is even, and n is not a multiple of 3. Therefore, we can use 1. above to deduce that $3^{n-1} \equiv (3^{\frac{n-1}{2}})^2 \equiv 1 \pmod{n}$. The order of any number relatively prime to n must divide $\phi(n)$ therefore $\phi(n) = k \cdot (n-1)$.

Now we can use a property of Euler's phi function which is that $\phi(n) \leq n - \sqrt{n}$ for every n which is composite. But we have $\phi(n) = k \cdot (n-1) \geq n-1 > n - \sqrt{n}$ , which holds in our case and therefore n is necessarily prime, QED.

Is this right?

Answer 1

The error that you made is that even though $3^{n-1} \equiv 1 \pmod{n}$, the order of 3 mod n need not be $n-1$. This is because the order is the smallest $k$ that satisfies $3^k \equiv 1 \pmod{n}$, and you've not checked that there are no smaller solutions (other than checking $ \frac{n-1}{2}$).

Thus, even though "The order of any number relatively prime to n must divide $\phi(n)$" is true, the statement "$\phi(n) = k(n-1)$ is not true.

---

Proof of the question

• We are given that the order of $9$ is $\frac{n-1}{2}$. Thus, $\phi (n) = k \frac{n-1}{2}$.
• Since $\phi(n) \leq n-1$, thus $ k \leq 2$.
• We want to show that $ k = 2$, from which we can conclude that $\phi(n) = n-1$ so $n$ is prime.
• So let's eliminate $k=1$ as a possibility. Note that we haven't used the first assumption as yet, so it will likely come into play here.

If $k = 1$, then $\phi(n) = \frac{n-1}{2}$ and thus $3^{\frac{n-1}{2} } \equiv 1 \pmod{n}$, which contradicts the first assumption (since $n \neq 2$).

Note: We still have no control over the order of $3$, other than being a divisor of $n-1$ but not a divisor of $\frac{n-1}{2}$. For example, it could theoretically be $\frac{n-1}{3}$. OP continually makes an error of not allowing this possibility.