Factoring polynomials over Z/nZ

Feb 2010
422
141
The irreducible quadratic n^2-5n+18 factors as (n-6)(n+1) mod 24. How can I determine this algorithmically?
 

Pim

Dec 2008
91
39
The Netherlands
While I personally never have seen a problem like this, I would solve it as follows.
Find two numbers, that when added give the "b". (-6,+1), but (-3, -2) also works here.
Then use long division with your functions to calculate the remainder of n^2-5n+1/((n-6)(n+1))
Does this answer your question?
 
  • Like
Reactions: maddas

HallsofIvy

MHF Helper
Apr 2005
20,249
7,909
\(\displaystyle (n- 6)(n+ 1)= n^2- 5n- 6\). since 6+ 18= 24= 0 (mod24), -6= 18 (mod 24) so this is the same as \(\displaystyle (n- 6)(n+ 1)= n^2- 5n+ 18\) (mod 24).
 
  • Like
Reactions: maddas
Feb 2010
422
141
Sorry, I was unclear. I know this is true, I found it basically how HallsOfIvy did: guess to replace -5 with 16 and factor as usual. My question was, if I did not know the factorization of the polynomial, how could I find it algorithmically?