Find a prime P 5 such that x2 1 is reducible in Zpx and gi

Find a prime P > 5 such that x^2 + 1 is reducible in Z_p[x], and give the factorization.

Solution

IF we can find p so that

1=-a^2 modulo p,for some integer a

then, x^2+1=x^2-a^2=(x-a)(x+a)

So we look at squares of integers larger than 5 and see if -a^2=1 mod some prime

6^2=36=-1 mod 37

So, 1=-36=-6^2 mod 37

SO, p=37 is the prime we need

x^2+1=x^2-36 mod 37

x^2-36=(x-6)(x+6) mod 37