7
$\begingroup$

$ 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.

  • 1
    @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$.2012-08-21

2 Answers 2

3

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$

  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/4585/discussion-between-moschops-and-n-s)2012-08-21
1

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.

  • 0
    Yes, $2$ is$a$quadratic residue mod $p$ means there is some $a$ such that $a^2 \equiv 2 \mod p$.2012-08-21