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.

  • 0
    Are you assuming $p$ is prime? There are some pseudoprimes that satisfy this condition, e.g. $341$ and $561$.2012-08-21
  • 0
    If $p$ is a prime, it is such that $2$ is a quadratic residue $(mod~p)$.2012-08-21
  • 0
    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?2012-08-21
  • 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