# Basic theory about divisibility and modular arithmetic

I am awfully bad with number theory so if one can provide a quick solution of this, it will be very much appreciated!

Prove that if $p$ is a prime with $p \equiv 1(\mod4)$ then there is an integer $m$ such that $p$ divides $m^2 +1$

-
I assume $p$ is a prime. –  user17762 Nov 21 '12 at 5:51
Indeed it is! I wil amend the post immediately! –  user44069 Nov 21 '12 at 6:01
Are you familiar with Euler's criterion? en.wikipedia.org/wiki/Euler's_criterion –  user17762 Nov 21 '12 at 6:13

I will assume that you know Wilson's Theorem, which says that if $p$ is prime, then $(p-1)!\equiv -1\pmod{p}$.

Let $m=\left(\frac{p-1}{2}\right)^2$. We show that if $p\equiv 1\pmod{4}$, then $m^2\equiv -1\pmod{p}$. This implies that $p$ divides $m^2+1$.

The idea is to pair $1$ with $p-1$, $2$ with $p-2$, $3$ with $p-3$, and so on until at the end we pair $\frac{p-1}{2}$ with $\frac{p+1}{2}$. To follow the argument, you may want to work with a specific prime, such as $p=13$. So we pair $1$ with $12$, $2$ with $11$, $3$ with $10$, $4$ with $9$, $5$ with $8$, and finally $6$ with $7$.

Thus for any $a$ from $1$ to $\frac{p-1}{2}$, we pair $a$ with $p-a$. Note that $a(p-a)\equiv -a^2\pmod{p}$.

So the product of all the numbers from $1$ to $p-1$ is congruent modulo $p$ to the product $$(-1^2)(-2^2)(-3^2)\cdot(-\left(\frac{p-1}{2}\right)^2).$$ This is congruent to $$(-1)^{\frac{p-1}{2}}m^2.$$ But $p-1$ is divisible by $4$, so $\frac{p-1}{2}$ is even, and therefore our product is congruent to $m^2$.

But our product is congruent to $(p-1)!$, and therefore, by Wilson's Theorem, it is congruent to $-1$.

We conclude that $m^2\equiv -1\pmod{p}$, which is what we wanted to show.

-

The Legendre symbol sutisfies: $$\left(\frac{-1}{p}\right) = (-1)^\tfrac{p-1}{2} =\begin{cases} \;\;\,1\mbox{ if }p \equiv 1\pmod{4} \\ -1\mbox{ if }p \equiv 3\pmod{4} \end{cases}.$$

Thus for $p\equiv 1 \pmod4, \ \left(\frac{-1}{p}\right)=1$ and the result follows.

Also see this.

-