Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $q$ be an odd integer such that $p = 4q+1$ is prime.

a. Show that $(2|p) = -1$

b. Prove that $p | (4^q+1)$

So far I see that: $(2|p) = (-1)^{ (\frac{(p^2-1)}{(8)} )}$. Not sure if this helps or where to go from here on either part.

share|cite|improve this question
up vote 3 down vote accepted

Let $q$ be an odd integer, say $q=2k+1$. Then $p=4q+1=8k+5$. Note that $p^2=(8k+3)^2=64k^2+48k+9$, so $\frac{p^2-1}{8}=8k^2+6k+1$, and therefore $(-1)^{(p^2-1)/8}=-1$.

It follows that the Legendre symbol $(2/p)$ is equal to $-1$.

Remark: I am not so happy about the (correct) formula for the Legendre symbol $(2/p)$, preferring the equivalent version $(2/p)=1$ if $p\equiv \pm 1\pmod{8}$, and $(2/p)=-1$ if $p\equiv \pm 3\pmod{8}$.

As to the remaining question, one hesitates to guess what is intended. But as currently written, there is nothing to do. If $p=4q+1$, then of course $p\mid 4q+1$.

Added: The second part of the question has been changed to $p$ divides $4^q+1$. So we want to show that $p$ divides $2^{2q}+1$.

Note that by Fermat's Theorem we have $p$ divides $2^{4q}-1$, so $p$ divides $(2^{2q}+1)(2^{2q}-1)$. We will be finished if we can show that $p$ does not divide $2^{2q}-1$. If $p$ divided $2^{2q}-1$, then $2$ would be a quadratic residue of $p$ by Euler's Criterion. But in the first part of the problem we have shown that $2$ is not a quadratic residue of $p$.

share|cite|improve this answer
We have proven this in class, so I can use (2|p) = -1 if p = +-3 (mod 8) – User011123521 Apr 21 '14 at 2:32
an edit has been made regarding question b, 4^q + 1 – User011123521 Apr 21 '14 at 2:33
Yes, that is the way I would have done it if you had not mentioned $\frac{p^2-1}{8}$. If $q=2k+1$, then $4q+1=8k+5$, so $p\equiv -3\pmod{8}$. – André Nicolas Apr 21 '14 at 2:34
Question here though, how is 4q + 1 = 8k + 3 and not 8k + 5? either way the result is the same with +- 3 (mod 8)? – User011123521 Apr 21 '14 at 2:51
@JonathanMckibbin: Yes, thank you, it is $8k+5$. Luckily that does not affect the argument. I have added a little thing to the answer to take care of the $p$ divides $4^q+1$. – André Nicolas Apr 21 '14 at 3:03

EDIT: Proving the relevant question...

By Euler's Criterion, $\left( \frac{2}p \right) \equiv 2^{(p-1)/2} \equiv 4^q \pmod p$. Since $4^q \equiv -1,$ ,we have $p|4^q+1$ as desired.

share|cite|improve this answer
Did you read the part where $q$ is an odd integer? – Erick Wong Apr 21 '14 at 2:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.