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

Question

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.

Answer 1

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

Answer 2

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.