Thread: square polynomials (mod 8 )

How should I prove this question?

Prove :
If a is any integer and the polynomial f(x) = x^2 +ax + 1 factors (polymod 8) , then f(x) is in fact a square; i.e. f(x)≡(x+c)^2 (polymod 8) for some non-negative integer c less than 8.

Originally Posted by beta12

How should I prove this question?

Prove :
If a is any integer and the polynomial f(x) = x^2 +ax + 1 factors (polymod 8) , then f(x) is in fact a square; i.e. f(x)≡(x+c)^2 (polymod 8) for some non-negative integer c less than 8.

It seems to me it is a direct connection to quadradic residues.
Remember from field theory that a polynomial of degree 2 or 3 is reducible over a polynomial ring (in this case the integers under multiplication modulo 8) if and only if it has a zero.

Thus, what we are saying is that
x^2+ax+1≡0(mod 8)
For some x.
We will express this in a more efficient way,
x^2+ax+1≡0(mod 2^3)
That means the discriminant of this quadradic is a quadradic residue of 2.

Hi perfecthacker,

This question wants us to find the possible values of a. i.e. for which non-negative a less than 8 does f(x) factor?

Do you have any idea about that?

Originally Posted by beta12

How should I prove this question?

Prove :
If a is any integer and the polynomial f(x) = x^2 +ax + 1 factors (polymod 8) , then f(x) is in fact a square; i.e. f(x)≡(x+c)^2 (polymod 8) for some non-negative integer c less than 8.

what is meant by statement:
f(x)≡(x+c)^2 (polymod 8)

I am missing something!

Keep SMiling
Malay

Originally Posted by malaygoel

what is meant by statement:
f(x)≡(x+c)^2 (polymod 8)

I am missing something!

That means the quadradic polynomial is equal to the square of (x+c) (under modulo 8).

Let me write the question again clearly.

Prove :
If a is any integer and the polynomial f(x) = x^2 +ax + 1 factors (polymod 8) , then f(x) is in fact a square; i.e. f(x)≡(x+c)^2 (polymod 8) for some non-negative integer c less than 8.

What are the possible values of a ? That is , for which non-negative a less than 8 does f(x) factor?

still can't figure out the values of a!

Originally Posted by beta12

Let me write the question again clearly.

Prove :
If a is any integer and the polynomial f(x) = x^2 +ax + 1 factors (polymod 8) , then f(x) is in fact a square; i.e. f(x)≡(x+c)^2 (polymod 8) for some non-negative integer c less than 8.

What are the possible values of a ? That is , for which non-negative a less than 8 does f(x) factor?

still can't figure out the values of a!

It was clearly the first time I was lazy to answer.
---
Since,
x^2+ax+1≡(x+c)^2=x^2+2cx+c^2 (mod 8)
By definition of polynomial equality we need that,
a=2c
1=c^2
.
So for what values of Z_8 do you have that, a number is is its own inverse. Basic computation for 0,1,...,7 shows that: 3,5,7.
Then,
a=2(3)=6
a=2(5)=2
a=2(7)=6

So the two polynomials you have are,
x^2+2x+1
x^2+6x+1

Hi perfecthacker,

I got it now.

Do you know how to prove this question too?

Prove: If a is any integer and the polynomial f(x) = x^2 + ax +1 factors (polymod 9), then there are three distinct non-negative integers y less than 9 such that f(y)≡ 0 ( mod 9).

Originally Posted by beta12

Prove: If a is any integer and the polynomial f(x) = x^2 + ax +1 factors (polymod 9), then there are three distinct non-negative integers y less than 9 such that f(y)≡ 0 ( mod 9).

It factos,
x^2+ax+1 = (x+b)(x+c)
Thus,
x^2+ax+1=x^2+(b+c)x+bc
Thus,
a=b+c
1=bc
Thus, you need to find all values of 'a'
such that you can find integers 1<=b,c<=9
That make the above statement true.

There should be 3 values of 'b' and 'c'.
The first condition: a=b+c is not important.
All you need to find is distinct 'b' and 'c' such that they are inverses (bc=1) and then declare a=b+c.

Hi perfecthacker,

Thank you very much.