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

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
    $$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 :(2012-08-21
  • 0
    $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?2012-08-21
  • 0
    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.2012-08-21
  • 0
    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....2012-08-21
  • 0
    Why are there only 4 values r can take? Why not 7?2012-08-21
  • 0
    Which 7? If the remainder is 2 for example, can p be odd? ;)2012-08-21
  • 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
    Okay. Stupid question time - what does that tell me about p? I struggle to extract that information from your answer.2012-08-21
  • 0
    @Moschops By the quadratic reciprocity law, this is equivalent to $p \equiv 1, 7$ (mod 8).2012-08-21
  • 0
    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.2012-08-21
  • 0
    @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.2012-08-21
  • 0
    Ah! Gotcha. Thanks.2012-08-21
  • 0
    @Moschops: It tells you that $2$ is a quadratic residue mod $p$. Since you say this is just "leading into" quadratic reciprocity, the bit about $p$ mod $8$ should not be the answer, but this is what leads into quadratic reciprocity.2012-08-21
  • 0
    "2 is a quadratic residue mod p" means that there is some number, which when squared, is equal to 2 mod p (I think). So p is just any prime number for which there is some number that when squared is 2? So p could equal 7, because 3 squared = 9 = 2 mod 7... or p could equal 23, because 5 squared = 25 = 2 mod 23. p is any prime number for which I can find a value that when squared = 2 mod p.2012-08-21
  • 0
    @Robert Israel : I don't follow this: 2(p−1)/2=bk(p−1)/2≡1modp iff k(p−1)/2 is a multiple of p−1. Why is this true? Why does k(p-1)/2 have to be a multiple of (p-1)?2012-08-21
  • 0
    @Moschops : To say $b$ is a primitive root mod $p$ means that the order of $b$ mod $p$, i.e. the least positive $m$ such that $b^m \equiv 1 \mod p$, is the order of the group, namely $p-1$. Every $n$ such that $b^n \equiv 1 \mod p$ must be a multiple of this order.2012-08-21
  • 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