# Prove that the odd prime divisors of the integer n^2+1 are of the form 4k+1

### 1 Answer | Add Yours

We have to verify that for any integer n^2 + 1, the odd prime divisors are of the form 4k + 1.

According to Euler's theorem, if p is an arbitrary odd prime, then x^2`-=` -1(mod p) has a solution p`-=` 1 (mod 4)

We'll use this to arrive at the proof.

Let the integer n^2 + 1 be divisible by an odd prime divisor p, n^2 + 1`-=` 0(mod p)

=> n^2 `-=` -1(mod p)

The solution to this is p`-=` 1(mod 4)

or p = 4k + 1

**This proves that all odd prime divisors of n^2 + 1 are of the form 4k + 1**