Show that ## p ## divides ## 2^{(p-1)/2}-1 ##

[Math100]

Homework Statement

If $p\equiv 7\pmod {8}$, where $p$ is prime, show that $p$ divides $2^{(p-1)/2}-1$. Deduce that $2^{75}-1$ and $2^{155}-1$ are composite.

Relevant Equations

Euler's criterion. Let $p$ be an odd prime. Then for all $n$ we have $(n|p)\equiv n^{(p-1)/2}\pmod {p}$.

Proof:

Suppose $p\equiv 7\pmod {8}$.
By Euler's criterion, we have that $(2|p)\equiv 2^{(p-1)/2}\pmod {p}$.
Note that $(2|p)=(-1)^{\frac{p^2-1}{8}}$ if $p$ is an odd prime.
Thus, $2$ is a quadratic residue of all primes $p\equiv \pm1\pmod {8}$, so $(2|p)=1$.
This implies $2^{(p-1)/2}-1\equiv 0\pmod {p}$.
Therefore, $p\mid (2^{(p-1)/2}-1)$ if $p\equiv 7\pmod {8}$ where $p$ is prime.
Now we consider $2^{75}-1$ and $2^{155}-1$.
Observe that
\begin{align*}
&75=\frac{p-1}{2}\implies p=151=7+18\cdot 8\\
&155=\frac{p-1}{2}\implies p=311=7+38\cdot 8.\\
\end{align*}
Thus, we have deduced that $75$ and $155$ are of the form $p=8k+7$ for some $k\in\mathbb{Z}$.
Therefore, $2^{75}-1$ and $2^{155}-1$ are composite.

 

[fresh_42]

Looks good. I couldn't find any mistakes.