Prove Proposition (4.19) of Chapter 4.
We remind ourselves of Proposition (4.19).
Let $p= 2n + 1$ be prime. Then we have the following:
(a) If $p \equiv \pm 1 \pmod 8$ then $p \mid (2^n-1)$.
(b) If $p \equiv \pm 3 \pmod 8$ then $p \mid (2^n+1)$.
(a) By Proposition (7.15) we have that if $p \equiv \pm 1 \pmod 8$ where $p$ is an odd prime, then $(\frac{2}{p}) = 1$.
By Euler's Criterion we have $2^{\frac{p-1}{2}} \equiv 1 \pmod p$. Substituing $p=2n+1$ gives us the desired result
$$ p \mid 2^n - 1 $$
(b) By Proposition (7.15) we have that if $p \equiv \pm 3 \pmod 8$ where $p$ is an odd prime, then $(\frac{2}{p}) = -1$.
By Euler's Criterion we have $2^{\frac{p-1}{2}} \equiv -1 \pmod p$. Substituing $p=2n+1$ gives us the desired result
$$ p \mid 2^n + 1 $$