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

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.

-

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

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

-
Did you read the part where $q$ is an odd integer? – Erick Wong Apr 21 '14 at 2:26