Properties of Primes of the form 4k+1 and 4k+3

So starting off with a very simple result on primes of the form $4k+1$ and $4k+3$ where $k \in \mathbb{N}$. Before going into the main theorems let us define some notations for simplicity.

• Let $\mathbb{P}_1 := $ denote the set of prime numbers of the form $4k+1$ and
• $ \mathbb{P}_3 :=$ denote the set of prime numbers of the form $4k+3$
  
• Also let $ Q_2 :=  $ denote the set of all numbers that can be written as a sum of two perfect squares.

Theorem $1$ : ( Thue's Theorem ) If  $ n $ is a positive integer and  is relatively prime to $ a $, then there exists integers $ 0 < x,y  \leq \sqrt{n} $ such that $ xa \equiv \pm y ( \mbox{ mod } n \ ) $ for a suitable choice of the signs $ + $ or $ - $.

Proof : Let $  0 < x,y \leq \lfloor \sqrt{n} \rfloor $ and let us consider all the values of  $ xa-y $ There are total $ \left( \lfloor \sqrt{n} \rfloor + 1 \right)^2  < n $ numbers of the form $ xa-y $. So by PHP, $ \exists$  at least two of them which leave same remainder when divided by $ n $. Let them be  $ ax_1 - y_1 $ and $ ax_2 - y_2 $. Let us assume that $ x_1 > x_2 $. Then setting $ x = x_1 - x_2 $ and $ y = | y_1 - y_2 |$  we get our required choice of $x,y $.

Theorem $2$ : $\mathbb{P}_1 $ is a subset of  $ Q_2 $

Proof : Let $ p = 4k+1 $ be a prime number.

Claim :  $\exists \ n $ such that $ p \ | \ n^2 + 1 $ 

By Wilson's Theorem we have $\boxed{ (p-1)! \equiv -1 ( \mbox{ mod } p \ ) }$

$$ \boxed{\therefore -1 \equiv 1 \cdot 2 \cdot \dots \left( \frac{p-1}{2} \right) \cdot \left( p - \frac{p-1}{2} \right) \cdot \dots \cdot (p-1) \equiv (-1)^{\frac{p-1}{2}} \left( \left( \frac{p-1}{2} \right)! \right)^2 ( \mbox{ mod } p \ ) }$$

Let $ n = \left( \frac{p-1}{2} \right)! $, then we have $ p \ | \ n^2 + 1 $

So our claim is true.

Now we apply Theorem 1 letting $ a = n $ to get integers  $ 0 < x,y < \sqrt{p} \ ( \because \sqrt{p} \not \in \mathbb{Q}) $ such that $ n^2 x^2 \equiv y^2 ( \mbox{ mod } p \ ) \Rightarrow x^2 + y^2 \equiv 0 ( \mbox{ mod } p \ ) $

Now as $ 0 < x,y \leq \sqrt{p} \Rightarrow 0 < x^2 + y^2 < 2p $. So we can conclude that $ p = x^2 + y^2 $.

Hence the theorem is proved.

Now let us focus on very useful property of prime numbers of the form $ 4k+3 $.

Theorem 3 : Let $ p \in \mathbb{P}_3 $ and suppose that $x$ and $y$ are integers such that $ p \ | \ x^2+y^2 $. Then $ p \ | \ \gcd(x,y) $.

Proof : Suppose $ p \ \not | \ \gcd(x,y) $. Then clearly $ p \ \not | \ xy $, thus $ \gcd(x,p) = \gcd(y,p) =1 $.

Now by Fermat's Little Theorem $ \boxed{ x^{p-1} \equiv y^{p-1} \equiv 1 ( \mbox{ mod } p \ ) } $

Because $ p \ | \ x^2 + y^2 $ we get

$ x^2 \equiv - y^2 ( \mbox{ mod } p \ ) $

$\Rightarrow x^{p-1} \equiv (-1)^{\frac{p-1}{2}}y^{p-1} ( \mbox{ mod } p \ ) $

$ \boxed{ \Rightarrow x^{p-1} \equiv (-1)^{2k+1} = -1 ( \mbox{ mod } p \ ) }$

Which gives us a contradiction, hence $ p \ | \ \gcd(x,y) $.

Note : The crucial consequence of theorem 3 is that any number of the form $ n^2 + 1 $ has only prime factors that belongs to $ \mathbb{P}_1 $ or are equal to $2$.