Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|improve this answer
We have proven this in class, so I can use (2|p) = -1 if p = +-3 (mod 8) –  Jonathan Mckibbin Apr 21 at 2:32
an edit has been made regarding question b, 4^q + 1 –  Jonathan Mckibbin Apr 21 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 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)? –  Jonathan Mckibbin Apr 21 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 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|improve this answer
Did you read the part where $q$ is an odd integer? –  Erick Wong Apr 21 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.