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

Asked on by svjr

1 Answer | Add Yours

justaguide's profile pic

justaguide | College Teacher | (Level 2) Distinguished Educator

Posted on

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

We’ve answered 319,816 questions. We can answer yours, too.

Ask a question