Associated Topics || Dr. Math Home || Search Dr. Math

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)

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

- 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/
```
Associated Topics:
College Algorithms
College Modern Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search