• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Reducible polynomials over Zp.

find a formula that depends on p
that determines the number of reducible monic degree 2 polynomials over Zp.

so the polynomials look like x^2+ax+b with a,b in Zp.

I examined the case for Z3 and Z5 to try and see what was going on.
in Z3 we had 9 monic degree 2 polynomials, 6 of them were reducible
and 3 were not. in Z5 we had 25 monic degree 2's 15 were reducible and
10 were not. it appears that (p(p+1))/2 is the formula but just showing two cases is obviously not enough work.
Is my guess right and how on earth would I prove it.

thanks!
 
Last edited:

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
Well, if you can't figure out how many are irreducible, maybe you can get it indirectly by figuring out how many are reducible?
 
I need to figure out how many are reducible. I only know how to find out how many are irreducible and reducible by plugging and chugging and that is not good enough for proof.
 
60
0
Your formula is not quite correct. The best way to solve this is to find the number of reducible polynomials of the form x^2+ax+b, where a,b are in Z_p, then the number of reducible quadratics, and subtract this from the total number of quadratics.
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
I only know how to find out how many are irreducible and reducible by plugging and chugging and that is not good enough for proof.
Then that's what we need to work on.

What does it mean for a quadratic polynomial to be reducible? I know of at least two good ways of answering this question, one of which leads to a very easy counting problem, and the other leads to a fairly easy counting problem if you know a little number theory.
 
it can be factored into two one degree polynomials
(x-a)(x-b)
 

matt grime

Science Advisor
Homework Helper
9,394
3
That'd be the harder one, perhaps.

Do you for instance know of a simple transformation of variables that in a degree n polynomial allows you to assume that the coefficient of x^{n-1} is zero? You might not in general, but you certainly know how to do it for degree 2 things, so think back to when you had to try and find roots of quadratics over C and didn't use the quadratic forumla b^2-4ac (or also think how you proved that the quadratic formula is true).
 
to prove the quadratic formula I would just complete the square.
should I be looking at the quadratic formula, the b^2-4ac term?
 

matt grime

Science Advisor
Homework Helper
9,394
3
ah, the magic words: complete the square... we after all know exactly when we can square root a number....
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
math-chick_41 said:
it can be factored into two one degree polynomials
(x-a)(x-b)
mattgrime said:
That'd be the harder one, perhaps.
Actually, I thought otherwise! Counting things of the form (x-a)(x-b) seemed the easiest!
 

matt grime

Science Advisor
Homework Helper
9,394
3
Guess I just like legendre symbols which are positive half of the time exactly (ignore the 0 case)
 

HallsofIvy

Science Advisor
Homework Helper
41,698
871
You guys are probably confusing the poor girl now- I know you are confusing me!

math-chick-41, What matt grime meant (I think!) when he asked "Do you for instance know of a simple transformation of variables that in a degree n polynomial allows you to assume that the coefficient of x^{n-1} is zero? " is that we can always substitute, say, [itex]x= y- \alpha[/itex] and then choose [itex]\alpha[/itex] so that the coefficient of x is 0. That is, x2+ ax+ b can always be written in the form y2- c which is reducible if and only is c is a "perfect square". What percentage of numbers in Zp are squares (including 0 and 1)? (Although if I'm right about this, I'm puzzled by BerkMath's "your formula is not quite correct".)
 
here is what I have, x^2+ax+b over Zp is reducible if we can factor it into
(x-s)(x-t) where s,t are in Zp. if s=t then there are p choices for s,t so there are p reducible polynomial. if s is not t then there are p choices for s and p-1 for t and when you switch s and t you get the same polynomial.

after that I dont know
 

matt grime

Science Advisor
Homework Helper
9,394
3
if you count correctly, then you have counted the number of reducibles, and you know the total number of polys, hence you can work out the number of irreds. of course that is implicitly assuming factorization behaves properly in Z_p, which it does, fortunately.

That is probably the best way to count the irreds. Mine complete the sqaure method is the way to actually tell if a given quadratic is reducibly.
 
Last edited:
60
0
HallsofIvy said:
- (Although if I'm right about this, I'm puzzled by BerkMath's "your formula is not quite correct".)
Carrying out the method I described earlier, you get (p(p-1)^2)/2.
 

Related Threads for: Reducible polynomials over Zp.

  • Posted
Replies
0
Views
2K
  • Posted
Replies
6
Views
2K
Replies
3
Views
1K
  • Posted
Replies
2
Views
1K
  • Posted
Replies
4
Views
3K
Replies
1
Views
610
  • Posted
Replies
1
Views
1K
  • Posted
Replies
4
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top