square polynomials (mod 8 )

• Sep 12th 2006, 11:25 PM
beta12
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.
• Sep 13th 2006, 08:36 AM
ThePerfectHacker
Quote:

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)
• Sep 14th 2006, 12:45 AM
beta12
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?
• Sep 14th 2006, 01:25 AM
malaygoel
Quote:

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
• Sep 14th 2006, 05:00 AM
ThePerfectHacker
Quote:

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).
• Sep 14th 2006, 05:25 AM
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!
• Sep 14th 2006, 05:31 AM
ThePerfectHacker
Quote:

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
• Sep 14th 2006, 09:07 AM
beta12
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).
• Sep 14th 2006, 10:05 AM
ThePerfectHacker
Quote:

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.
• Sep 16th 2006, 01:28 AM
beta12
Hi perfecthacker,

Thank you very much.