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

I have been stumped on this question for a while. There is an additional hint:

Show first that if $p$ is any prime divisor of $n$ then $ord_p(a)$ must be a divisor of $n-1=2^mk$ and not a divisor of $\frac{1}{2}(n-1) = 2^{m-1}k$, and use Fermat's Little Theorem to deduce that $p\equiv1\mod2^m$.

I'm not even sure how to do the first part of the hint. I have that since $a^n\mod p$ will be periodic, $ord_p(a)|n$. But then doesn't that imply $ord_p(a)|(2^mk+1) \implies2^mk+1\equiv0\mod ord_p(a)$? I thought we were trying to show $2^mk\equiv0\mod ord_p(a)$.

Any help on any part of this question or hint would be greatly appreciated!


If $p$ is a prime divisor of $n$ let $\text{ord}_p(a)=x$...... Then $a^{(n-1)/2}\equiv -1 \pmod n$ implies $a^{(n-1)/2 } \equiv -1 \pmod p$ which implies $a^{(n-1)/2} \not \equiv 1 \pmod p$ (because $p$ must be odd) which implies $x \not | (n-1)/2.$..... But $a^{n-1} \equiv 1 \pmod n$ implies $x|(n-1)=2^m k$ so $x=2^b c$ where $b \le m$ and $c$ is odd (because $k$ is odd) and $c|k.$.... So $y=(n-1)/x=2^{m-b}(k/c)$ is an integer but $y/2$ is not.And because $k/c$ is an odd integer, this requires that $b=m.$.... Hence $2^m c=x=\text{ord}_p(a)|(p-1)$ which implies $ p=2^m j+1$ for some positive integer $j.$..... Now if $n$ is not prime then $ n/p$ is divisible by a prime $p^*$ but then, applying the above argument for $ p^*$ we have$ p^*=2^m j^*+1$ for positive integer $j^*$...... But $k<2^m$ so if $n$ is not prime then $4^m+1>n\ge p p^*>4^m j j^*+1 \ge 4^m+1$ which is absurd. You wrote " $\text{ord_p(a)}|n$ " (after the hint),which is an error.

  • $\begingroup$ Thanks a lot! I was going to come back to post my breakthrough, but you beat me to it! My only remaining question is why $\text{ord}_p(a) = 2^mc$ when $2^m|\text{ord}_p(a)$ as well as $2^mc|\text{ord}_p(a)$. Especially since it says in the hint that $p \equiv \pmod 2^m$ I realised my mistake was in the initial approach to the problem, and it came easily after realising that $p|a^{\frac{1}{2}(n-1)}+1$. $\endgroup$ – filterjuice Sep 11 '15 at 8:02
  • $\begingroup$ $ord_p(a)=x|2^mk =n-1$ with $k$ odd so $x=2^bc$ where $b\leq m$ and $ c|k$ . But $b=m$ otherwise $ x|2^{m-1}k= (n-1)/2.$ $\endgroup$ – DanielWainfleet Sep 15 '15 at 19:58
  • $\begingroup$ Yes but why does there have to be a $c$ there, when $2m|ordp(a)$ anyway? $\endgroup$ – filterjuice Sep 16 '15 at 12:31
  • 1
    $\begingroup$ c could be 1.All we know at that stage is that c is an odd divisor of the odd number k and that b can't exceed m. .For example if m=4 and k=7 so n-1=112, and if x|112 then x=$2^b c$ where $b\le 4 $, and $c=1$ or $c=7$. $\endgroup$ – DanielWainfleet Sep 19 '15 at 2:18
  • $\begingroup$ Thank you for all your help! $\endgroup$ – filterjuice Sep 19 '15 at 2:49

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.