Polynomial Congruence

Date: 02/28/2001 at 03:14:14
From: David Kwan
Subject: Polynomial Congruence

I am having a problem understanding how to solve a polynomial 
congruence. Here is the problem:

Find a polynomial (F) in Field(7) with degree less then 4.

( x^2 -1 ) F == ( x^3 + 2x + 5 ) mod ( x^4 + 2x^2 + 1)

Please help to find F.

I looked at many topics on linear congruence but none talked about 
polynomials.

Date: 02/28/2001 at 15:36:46
From: Doctor Rob
Subject: Re: Polynomial Congruence

Thanks for writing to Ask Dr. Math, David.

You need to find the multiplicative inverse of x^2 - 1, so that you 
can multiply both sides by this to isolate F on one side of the 
congruence. You do this by using the Euclidean Algorithm, starting 
with inputs x^4 + 2*x^2 + 1 and x^2 - 1:

   x^4 + 2*x^2 + 1 = (x^2 - 1)*(x^2 + 3) + 4.

Since the remainder is a constant, you are ready to backtrack:

   1 = 2*4 (mod 7)
     = 2*[(x^4 + 2*x^2 + 1) - (x^2 + 3)*(x^2 - 1)] (mod 7),
     = 2*(x^4 + 2*x^2 + 1) - 2*(x^2 + 3)*(x^2 - 1) (mod 7),
     = 2*(x^4 + 2*x^2 + 1) + (5*x^2 + 1)*(x^2 - 1) (mod 7),
   1 = (5*x^2 + 1)*(x^2 - 1) (modd x^4 + 2*x^2 + 1, 7).

That means that 5*x^2 + 1 is the multiplicative inverse of x^2 - 1.
Now multiply both sides of your original congruence by 5*x^2 + 1,
and reduce both sides modulo x^4 + 2*x^2 + 1, and also reduce all
coefficients modulo 7, and you'll have your answer.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/28/2001 at 17:28:41
From: David Kwan
Subject: Re: Polynomial Congruence

Thank you, Doctor Rob, for answering the question for me.

But I have one more step to clarify, on the second step to third step.
We have 2*(x^4 + 2*x^2 + 1) - 2*(x^2 + 3)*(x^2 - 1) (mod 7)
which becomes 2*(x^4 + 2*x^2 + 1) + (5*x^2 +1)*(x^2 - 1) (mod 7)

How does -2*(x^2 + 3)*(x^2 - 1) become (5*x^2 + 1)*(x^2 - 1) ?

Or can we just have -2(x^2 + 3) as the inverse?

David

Date: 03/01/2001 at 11:45:32
From: Doctor Rob
Subject: Re: Polynomial Congruence

Thanks for writing back, David.

-2*(x^2 + 3) = -2*x^2 - 6 = 5*x^2 + 1 + 7*(-x^2 - 1).  When you
reduce coefficients modulo 7, the last part reduces to zero.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/