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!!


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.

  • $\begingroup$ Many thanks for your help Daniel. While I do understand and follow your answer, I am just wondering, since $a^{k}\equiv a^{p-1}\equiv a^{n-1}\equiv 1 (mod \space p)$ $\implies k|p-1$ and $p-1|n-1$ and $n-1=2^{h}m$, could I not go from here to the last part of answer, to deduce that $p-1=2^{m}h$? Thanks again for the assistance. $\endgroup$ – JackReacher Sep 7 '13 at 3:10
  • 2
    $\begingroup$ You only get to $(p-1) \mid (n-1)$ once you know $p = n$. What you get from $a^{\frac12(n-1)} \equiv -1 \pmod{p}$ is that $2^m$ divides the order of $a$ modulo $p$. So $2^m \mid (p-1)$, or $p \equiv 1 \pmod{2^m}$. But that means $n$ has only one prime factor, since the product of two such primes would be too large. $\endgroup$ – Daniel Fischer Sep 7 '13 at 9:51

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.