$p$ divides $2^{(p-1)/2} - 1$; what is p?

$$p | 2^{(p-1)/2}-1$$

p is prime. I can prove that if $(p-1)/2$ is composite, then $$2^{(p-1)/2}-1$$ is also composite. I cannot manage to deduce anything about $p$. I'm trying to come up with some set of criteria that $p$ must fulfil such that $$p | 2^{(p-1)/2}-1$$

I've experimented with $$2^{(p-1)/2} \equiv 1 \pmod p$$ but didn't really get anywhere. I think this question is leading me into quadratic reciprocity, so I shouldn't need quadratic reciprocity to solve it (so should, presumably, be able to do it with things like the fundamental theorem of arithmetic, Fermat's Little Theorem, and things of that nature). I've also tried treating this as $$(2^{(p-1)/4})(2^{(p-1)/4}) \equiv 1\pmod p$$ which looked like it was going somewhere for a while.

This is supposed to be the easy one mark intro to a much bigger question and should presumably take about sixty seconds. I've spent a few hours on it so far and got nowhere. I am terrible at number.

Edited to confirm that p is prime.

• Are you assuming $p$ is prime? There are some pseudoprimes that satisfy this condition, e.g. $341$ and $561$. – Robert Israel Aug 21 '12 at 19:15
• If $p$ is a prime, it is such that $2$ is a quadratic residue $(mod~p)$. – Karolis Juodelė Aug 21 '12 at 19:16
• Yes, p is definitely a prime. "2 is a quadratic residue (mod p)"; to me, this means "there is some number that, when you square it, it is congruent to 2 mod p" (hope that's right; I stand by to be corrected). However, to me that's just magic words - I have no idea why it's true. Can it be proved from something more akin to first principles? – Moschops Aug 21 '12 at 19:21
• @Moschops: Since you are close to getting to Reciprocity, perhaps you have already seen a proof of Euler's Criterion. and you may already have seen a proof of the fact that $2$ is a quadratic residue of the odd prime $p$ iff $p$ is of the form $8k\pm 1$. – André Nicolas Aug 21 '12 at 19:24

2 Answers

The problem gives you

$$2^{\frac{p-1}2} \equiv 1 \mod p$$

Euler Criteria tell you that $$\left( \frac{2}{p} \right)=1$$

But

$$\left( \frac{2}{p} \right) =(-1)^\frac{p^2-1}{8}$$

This tells you what $p$ is modulo 8.

Also note that every implication is if and only if. You get that for a odd prime $p$ we have

$$2^{\frac{p-1}2} \equiv 1 \mod p \Leftrightarrow p \in \{ ..., ... \} \mod 8$$

• $$1 = (-1)^\frac{p^2-1}{8}$$ $$\frac{p^2-1}{8}=2,4,6,8...$$ $${p^2-1}=16,32,48,62...$$ $$p^2=17,33,49,63...$$ I don't follow :( – Moschops Aug 21 '12 at 19:47
• $p$ is either $1,3,5$ or $7$ modulo $8$. If $p=8k+r$ then $p^2=16(4k^2+kr)+r^2$. Then, $\frac{p^2-1}{2}=$even+$\frac{r^2-1}{2}$... What can $r$ be? – N. S. Aug 21 '12 at 20:18
• I promise you, I'm not being deliberately obtuse. I push that through to get r, and r comes out as root(8-even+1) or root(16-even+1) or root(24-even+1) or root(32-even+1)... which now just gives me two unknown values. I think I'm missing completely whatever point you're making. I do this a lot in number. – Moschops Aug 21 '12 at 20:33
• Don't try to solve $p^2-1/8=2,4,6,8...$ for $p$ or $r$, because you have too many choices. If instead you take $r$ to be the remainder when $p$ is divided by $8$, there are only $4$ values $r$ can take, and you can check which works in the equation.... – N. S. Aug 21 '12 at 20:39
• Why are there only 4 values r can take? Why not 7? – Moschops Aug 21 '12 at 21:08

Assume $p$ is an odd prime. If $b$ is a primitive root mod $p$, $2 \equiv b^k \mod p$ for some integer $k$, and $2^{(p-1)/2} = b^{k(p-1)/2} \equiv 1 \mod p$ iff $k(p-1)/2$ is a multiple of $p-1$, i.e. iff $k$ is even. If $k$ is even, $2 \equiv (b^{k/2})^2$ is a quadratic residue mod $p$. Conversely, if $2$ is a quadratic residue, say $2 \equiv a^2 \mod p$ where $a \equiv b^m \mod p$, then $2 \equiv b^{2m}$ so $k$ is even.

• Okay. Stupid question time - what does that tell me about p? I struggle to extract that information from your answer. – Moschops Aug 21 '12 at 19:31
• @Moschops By the quadratic reciprocity law, this is equivalent to $p \equiv 1, 7$ (mod 8). – Makoto Kato Aug 21 '12 at 19:33
• You say "$b$ is a primitive root mod $p$"--a primitive root of what? It looks like it should be apparent from your answer, but I'm not seeing it. – Cameron Buie Aug 21 '12 at 19:35
• @CameronBuie: A primitive root modulo $p$ (or of $p$) is a generator $g$ of the multiplicative group modulo $p$. There is such a $g$ (indeed several) for any prime $p$. Depending on the order one does things, one might show existence of primitive roots and their basic properties in the chapter before Reciprocity, or in the chapter after. – André Nicolas Aug 21 '12 at 19:46
• Ah! Gotcha. Thanks. – Cameron Buie Aug 21 '12 at 20:21