# Prove n is prime

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.

• 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$. – filterjuice Sep 11 '15 at 8:02
• $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.$ – DanielWainfleet Sep 15 '15 at 19:58
• Yes but why does there have to be a $c$ there, when $2m|ordp(a)$ anyway? – filterjuice Sep 16 '15 at 12:31
• 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$. – DanielWainfleet Sep 19 '15 at 2:18
• Thank you for all your help! – filterjuice Sep 19 '15 at 2:49