Prove that $n$ must be prime.

Here is the complete question:

Suppose that $n=2^{m}h+1$, where m is an integer and $h$ is an odd positive integer less than $2^{m}$. Suppose that there is an integer $a$ such that $a^{\frac{1}{2}(n-1)}\equiv -1 (mod \space n)$. Prove that $n$ must be prime.

[Hint: show first that if $p$ is any prime divisor of $n$ then $ord_{p}(a)$ must be a divisor of $n-1=2^{m}k$ and not a divisor of $\frac{1}{2}(n-1)=2^{m-1}h$, and use Fermat's Little Theorem to deduce that $p\equiv1 (mod \space 2^{m})$.]

This is one of the hardest exam practice questions for my class, and I've been thinking over this question a few days and I think I am close, but I just need a bit of help. I am trying to follow the hint as much as I can. Here is what I have so far:

Assume $p$ is a prime divisor of n.

Since $p|n$ and $n|a^{\frac{1}{2}(n-1)}+1 = a^{2^{m-1}h}+1$

$\implies p\nmid a$

Then by Fermat's Theorem,

$a^{p-1}\equiv 1 (mod \space p) $ and we have that $p|a^{\frac{1}{2}(n-1)}+1 = a^{2^{m-1}h}+1$

$\implies a^{\frac{1}{2}(n-1)}\equiv -1 (mod \space p)$ $\implies a^{(n-1)}\equiv 1 (mod \space p)$ (after squaring both sides)

So we have that $p | a^{p-1}-1$ and $p | a^{n-1}-1$

$\implies a^{p-1}\equiv a^{n-1} \equiv 1 (mod \space p)$

(here is where I am a bit fuzzy. I am sort of just assuming $ord_p(a) = p-1$)

so $(p-1)|(n-1) = 2^{m}h$ (also not too sure about that?)

It follows that $2^{m}|(p-1)$ i.e. $(p-1) = 2^{m}h$

So $n = (p-1)+1$ $\implies n$ must be prime, since our assumption was that $p$ is a prime.

I know I haven't used the hint exactly and I also haven't made use of the fact that $h$ is a an odd smaller than $2^{m}$.

If someone can help me, it would be greatly appreciated!!

Solution 1:

You can't simply assume $\operatorname{ord}_p(a) = p-1$. However, you are given

$$a^{\frac12(n-1)} \equiv -1 \pmod{n} \Rightarrow a^{\frac12(n-1)} \equiv -1 \pmod{p} \Rightarrow a^{n-1} \equiv 1 \pmod{p}.$$

Since $\operatorname{ord}_p(a)$ is the smallest positive number $k$ with $a^k \equiv 1 \pmod{p}$, you can deduce that $\operatorname{ord}_p(a) \mid n-1$.

Let $p = 2^s\cdot u + 1$ with $u$ odd. Then $a^{p-1} = a^{2^su} \equiv 1 \pmod{p}$. But $a^{2^{m-1}h} \equiv -1 \pmod{p}$, hence $(a^{2^{m-1}u})^h \equiv -1 \pmod{p}$, and thus $s \geqslant m$, so $p \equiv 1 \pmod{2^m}$, hence $p \geqslant 2^m + 1$.

Now, if $n$ were not prime, it would have at least two prime factors, all of which are $\equiv 1 \pmod{2^m}$, and hence the product of two such primes would be $\geqslant (2^m+1)^2$.

More detailed exposition:

We have an integer $n = 2^m\cdot h +1$ with $0 < h < 2^m$ odd, and we are assured of the existence of an integer $a$ with $a^{\frac12(n-1)} \equiv -1 \pmod{n}$.

To show that $n$ is prime, we take any prime $p$ dividing $n$ - such a prime exists, since we have $1 < 2^m$, hence $1 < n$ by $0 < h < 2^m$ - and then show that $p = n$. Since $m \geqslant 1$, it follows that $n$ is odd, and hence so is $p$. Write $p = 2^s\cdot u + 1$ with $u$ odd. Since by assumption

$$n \mid \left(a^{\frac12(n-1)} +1\right),$$

and $p$ divides $n$, we also have

$$p \mid \left(a^{\frac12(n-1)} +1\right) \iff a^{\frac12(n-1)} \equiv -1 \pmod{p}.$$

In particular, $a$ is not a multiple of $p$. By Fermat's theorem, we know that $\operatorname{ord}_p(a) \mid (p-1)$, hence

$$a^{p-1} = a^{2^s\cdot u} \equiv 1 \pmod{p}.$$

But $\frac12(n-1) = 2^{m-1}h$, and

$$\left(a^{2^{m-1}u}\right)^h = \left(a^{2^{m-1}h}\right)^u \equiv (-1)^u \equiv -1 \pmod{p},$$

so $a^{2^{m-1}u} \not\equiv 1 \pmod{p}$, but $a^{2^su} \equiv 1 \pmod{p}$, hence $s > m-1$, or equivalently $s \geqslant m$.

Thus we have $2^m \mid 2^s\cdot u = (p-1)$. In particular, $p \geqslant 2^m + 1$. But

$$\left(2^m+1\right)^2 = 2^{m}\cdot 2^m + 2\cdot 2^m + 1 = 2^m\cdot h + 1 + \left(2^m(2^m-h) +2\cdot 2^m\right) > 2^mh+1 = n,$$

so $p > \sqrt{n}$.

If $n$ were composite, it would have at least one prime factor $\leqslant \sqrt{n}$, but we just saw that all prime factors of $n$ are $> \sqrt{n}$, hence $n$ must be prime.