Author 
Topic: Poly Factorizations (Read 1221 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


Poly Factorizations
« on: Jun 18^{th}, 2007, 12:01pm » 
Quote Modify

Has this been posted before? Factorize the polynomial x^{3} + 1 modulo prime p.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Poly Factorizations
« Reply #1 on: Jun 18^{th}, 2007, 12:19pm » 
Quote Modify

Note sure If this has been asked before, but I don't understand the question. What is wrong with (x+1)(x^{2}  x + 1) ?

« Last Edit: Jun 18^{th}, 2007, 12:19pm by Aryabhatta » 
IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Poly Factorizations
« Reply #2 on: Jun 18^{th}, 2007, 1:18pm » 
Quote Modify

Is x^2x+1 always irreducible mod p, though?


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Poly Factorizations
« Reply #3 on: Jun 18^{th}, 2007, 2:10pm » 
Quote Modify

Does "factorize" always imply irreducible factors? Anyway, I understand the question now

« Last Edit: Jun 18^{th}, 2007, 2:11pm by Aryabhatta » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Poly Factorizations
« Reply #4 on: Jun 19^{th}, 2007, 1:37am » 
Quote Modify

Elimination of certain cases. if p > 6 then for x^{2}  x + 1 to be reducible mod p, p must be of the form 6k+1. (We must have that in (Z/p)^{*} some element satisfies a^{6} = 1 and no other lesser power of a is 1)

« Last Edit: Jun 19^{th}, 2007, 1:38am by Aryabhatta » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Poly Factorizations
« Reply #5 on: Jun 19^{th}, 2007, 5:48am » 
Quote Modify

on Jun 19^{th}, 2007, 1:37am, Aryabhatta wrote:if p > 6 then for x^{2}  x + 1 to be reducible mod p, p must be of the form 6k+1. 
 Nice observation! Can you elaborate?


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Poly Factorizations
« Reply #6 on: Jun 19^{th}, 2007, 9:21am » 
Quote Modify

Sure. If a^{2}a+1 = 0 Then a^{3} = 1 which implies a^{6} = 1 Also a =/= 1. Let y be the smallest power of a which equals 1. Then y  6. If a^{2} = 1 then 1 = a^{3} = a We already know a^{3} =/= 1 (as p != 2) Thus (Z/p)^{*} has a subgroup of order 6. So 6 must divide p1.

« Last Edit: Jun 19^{th}, 2007, 11:10pm by Aryabhatta » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Poly Factorizations
« Reply #7 on: Jun 19^{th}, 2007, 10:08pm » 
Quote Modify

Ok. I think we have a way of solving this. Assume p > 6. We are working modulo p. x^{2}  x +1 = 0 iff 4(x^{2}  x +1) = 0 iff (2x  1)^{2} = 3 Now if y^{2} = 3 has a solution then there is some x =/= 1 for which 2x1 = y. (if it turns out that x = 1, then y must 3 so 9 = 3 (mod p). Not possible) By quadratic reciprocity theorem... if one of p, q is of the form 4k+1, y^{2} = p (mod q) has a solution if and only if z^{2} = q (mod p) has a solution i.e y^{2} = 3 (mod p) has a solution iff z^{2} = p (mod 3) has a solution i.e iff p = 1 (mod 3) Thus the only primes p for which x^{2}x+1 is reducible are p=2, p =3 and any prime of the form 6k+1.

« Last Edit: Jun 19^{th}, 2007, 10:10pm by Aryabhatta » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Poly Factorizations
« Reply #8 on: Jun 20^{th}, 2007, 7:08am » 
Quote Modify

Nicely done, Aryabhatta! But: on Jun 19^{th}, 2007, 10:08pm, Aryabhatta wrote:Thus the only primes p for which x^{2}x+1 is reducible are p=2, p =3 and any prime of the form 6k+1. 
 I think p=2 should be excluded. Let's consider now a generalization: for which p, the polynomial x^{q} + 1 is a product of linear factors modulo p, where p, q are both primes?


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Poly Factorizations
« Reply #9 on: Jun 20^{th}, 2007, 10:05am » 
Quote Modify

on Jun 20^{th}, 2007, 7:08am, Barukh wrote: But: I think p=2 should be excluded. 
 Yes, you are right.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Poly Factorizations
« Reply #10 on: Jun 21^{st}, 2007, 10:21am » 
Quote Modify

on Jun 20^{th}, 2007, 7:08am, Barukh wrote: Let's consider now a generalization: for which p, the polynomial x^{q} + 1 is a product of linear factors modulo p, where p, q are both primes? 
 Do you know of a solution to this?


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Poly Factorizations
« Reply #11 on: Jun 21^{st}, 2007, 11:20am » 
Quote Modify

on Jun 21^{st}, 2007, 10:21am, Aryabhatta wrote:Do you know of a solution to this? 
 Partially... The more interesting may be the discussion!


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Poly Factorizations
« Reply #12 on: Jun 22^{nd}, 2007, 3:55am » 
Quote Modify

Example: x^{5}+1 = (x+1)(x+36)(x+84)(x+87)(x+95) mod 101

« Last Edit: Jun 22^{nd}, 2007, 3:56am by Barukh » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Poly Factorizations
« Reply #13 on: Jun 24^{th}, 2007, 9:21am » 
Quote Modify

How about this? If p = 1 mod q, then x^{q} + 1 is a product of linear factors modulo p.

« Last Edit: Jun 24^{th}, 2007, 9:22am by Barukh » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Poly Factorizations
« Reply #14 on: Jun 26^{th}, 2007, 12:58am » 
Quote Modify

In fact, much more is known! Of course, (x+1) is always a factor. Let d = p mod q, and d a multiplicative order of r in Z/Zq (that is, r^{d} = 1 mod q for the first time). Then, (x^{q}+1)/(x+1) is a product of (q1)/d factors of degree d! Example: q = 11, p = 43, r = 10, d = 2 (10^{2} = 1 mod 11). And indeed: x^{11}+1 = (x+1)(x^{2}+4x+1)(x^{2}+9x+1)(x^{2}+14x+1)(x^{2}+22x+1)(x ^{2}+36x+1) mod 43 This is attributed to Gauss. I am going to figure out how.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Poly Factorizations
« Reply #15 on: Jun 26^{th}, 2007, 12:46pm » 
Quote Modify

Interesting... Alas, I am too busy with work to do anything about this Please keep updating this thread with your findings.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Poly Factorizations
« Reply #16 on: Jun 27^{th}, 2007, 4:18pm » 
Quote Modify

on Jun 24^{th}, 2007, 9:21am, Barukh wrote:How about this? If p = 1 mod q, then x^{q} + 1 is a product of linear factors modulo p. 
 This only holds if q is odd, in which case x^{q}+1 is equivalent to x^{q}1. And x^{q}1 splits into linear factors over Z_{p} if and only if p=q or p=1 mod q. This can be shown using the same argument Aryabhatta used here. Quote:Let d = p mod q, and d a multiplicative order of r in Z/Zq (that is, r^{d} = 1 mod q for the first time). Then, (x^{q}+1)/(x+1) is a product of (q1)/d factors of degree d! 
 You mean, r = p mod q. To prove this, consider a root z of (x^{q}+1)/(x+1) over F_{p}, and the elements z, z^{p}, z^{p^2}, .... (There's a sketch of the argument here.)


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Poly Factorizations
« Reply #17 on: Jun 28^{th}, 2007, 5:36am » 
Quote Modify

on Jun 27^{th}, 2007, 4:18pm, Eigenray wrote: This only holds if q is odd, in which case x^{q}+1 is equivalent to x^{q}1. 
 Yes. But what do you mean by "equivalent"? Quote: Of course... Quote:To prove this, consider a root z of (x^{q}+1)/(x+1) over F_{p}, and the elements z, z^{p}, z^{p^2}, .... (There's a sketch of the argument here.) 
 This is too heavy machinery. I wonder if there exists a more elementary argument. For instance, the case p = 1 mod q may be shown with purely combinatorical argument.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Poly Factorizations
« Reply #18 on: Jul 1^{st}, 2007, 1:29am » 
Quote Modify

Ok, things are clearer now (for me). I managed even to understand Eigenray's very concise argument in another thread. As usual, I again messed up things by confusing the finite field F_{pn} with the group Z/p^{n}Z, which isn't even a field when n > 1! If anybody is interested, I will try to find time and inspiration to explain the solution in more detailed manner.


IP Logged 



