wu :: forums
« wu :: forums - Poly Factorizations »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 11:35am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: SMQ, towr, Eigenray, Grimbal, Icarus, william wu)
   Poly Factorizations
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Poly Factorizations  (Read 1214 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Poly Factorizations  
« on: Jun 18th, 2007, 12:01pm »
Quote Quote Modify Modify

Has this been posted before?  Huh
 
Factorize the polynomial x3 + 1 modulo prime p.
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Poly Factorizations  
« Reply #1 on: Jun 18th, 2007, 12:19pm »
Quote Quote Modify Modify

Note sure If this has been asked before, but I don't understand the question.
 
What is wrong with (x+1)(x2 - x + 1) ?
« Last Edit: Jun 18th, 2007, 12:19pm by Aryabhatta » IP Logged
Obob
Senior Riddler
****





   


Gender: male
Posts: 489
Re: Poly Factorizations  
« Reply #2 on: Jun 18th, 2007, 1:18pm »
Quote Quote Modify Modify

Is x^2-x+1 always irreducible mod p, though?
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Poly Factorizations  
« Reply #3 on: Jun 18th, 2007, 2:10pm »
Quote Quote Modify Modify

Does "factorize" always imply irreducible factors?
 
Anyway, I understand the question now Grin
« Last Edit: Jun 18th, 2007, 2:11pm by Aryabhatta » IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Poly Factorizations  
« Reply #4 on: Jun 19th, 2007, 1:37am »
Quote Quote Modify Modify

Elimination of certain cases.
 
if p > 6 then for x2 - 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 a6 = 1 and no other lesser power of a is 1)
« Last Edit: Jun 19th, 2007, 1:38am by Aryabhatta » IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Poly Factorizations  
« Reply #5 on: Jun 19th, 2007, 5:48am »
Quote Quote Modify Modify

on Jun 19th, 2007, 1:37am, Aryabhatta wrote:
if p > 6 then for x2 - x + 1 to be reducible mod p, p must be of the form 6k+1.

Nice observation!  Cheesy
 
Can you elaborate?
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Poly Factorizations  
« Reply #6 on: Jun 19th, 2007, 9:21am »
Quote Quote Modify Modify

Sure.
 
If a2-a+1 = 0 Then a3 = -1 which implies a6 = 1
 
Also a =/= -1.
Let y be the smallest power of a which equals 1.
 
Then y | 6.
 
If a2 = 1 then -1 = a3 = a
 
We already know a3 =/= 1 (as p != 2)
 
Thus (Z/p)* has a subgroup of order 6. So 6 must divide p-1.
« Last Edit: Jun 19th, 2007, 11:10pm by Aryabhatta » IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Poly Factorizations  
« Reply #7 on: Jun 19th, 2007, 10:08pm »
Quote Quote Modify Modify

Ok. I think we have a way of solving this.
 
Assume p > 6.
 
We are working modulo p.
 
x2 - x +1 = 0  
 
iff 4(x2 - x +1) = 0
iff  (2x - 1)2 = -3
 
Now if  
y2 = -3 has a solution then there is some x =/= -1 for which 2x-1 = 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,
 
y2 = p (mod q)  
has a solution if and only if
z2 = q (mod p) has a solution
 
i.e y2 = -3 (mod p) has  a solution iff
 z2 = p (mod -3) has a solution
 
i.e iff p = 1 (mod 3)
 
Thus the only primes p for which x2-x+1 is reducible are
 
p=2, p =3 and any prime of the form 6k+1.
« Last Edit: Jun 19th, 2007, 10:10pm by Aryabhatta » IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Poly Factorizations  
« Reply #8 on: Jun 20th, 2007, 7:08am »
Quote Quote Modify Modify

Nicely done, Aryabhatta!  Cheesy
 
But:
 
on Jun 19th, 2007, 10:08pm, Aryabhatta wrote:
Thus the only primes p for which x2-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 xq + 1 is a product of linear factors modulo p, where p, q are both primes?
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Poly Factorizations  
« Reply #9 on: Jun 20th, 2007, 10:05am »
Quote Quote Modify Modify

on Jun 20th, 2007, 7:08am, Barukh wrote:

But:
 
I think p=2 should be excluded.
 

 
Yes, you are right.
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Poly Factorizations  
« Reply #10 on: Jun 21st, 2007, 10:21am »
Quote Quote Modify Modify

on Jun 20th, 2007, 7:08am, Barukh wrote:

Let's consider now a generalization: for which p, the polynomial xq + 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: male
Posts: 2276
Re: Poly Factorizations  
« Reply #11 on: Jun 21st, 2007, 11:20am »
Quote Quote Modify Modify

on Jun 21st, 2007, 10:21am, Aryabhatta wrote:
Do you know of a solution to this?

Partially...  Shocked
 
The more interesting may be the discussion!  Wink
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Poly Factorizations  
« Reply #12 on: Jun 22nd, 2007, 3:55am »
Quote Quote Modify Modify

Example:
 
x5+1 = (x+1)(x+36)(x+84)(x+87)(x+95) mod 101
 
« Last Edit: Jun 22nd, 2007, 3:56am by Barukh » IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Poly Factorizations  
« Reply #13 on: Jun 24th, 2007, 9:21am »
Quote Quote Modify Modify

How about this?
 
If p = 1 mod q, then xq + 1 is a product of linear factors modulo p.
« Last Edit: Jun 24th, 2007, 9:22am by Barukh » IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Poly Factorizations  
« Reply #14 on: Jun 26th, 2007, 12:58am »
Quote Quote Modify 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, rd = 1 mod q for the first time).
 
Then, (xq+1)/(x+1) is a product of (q-1)/d factors of degree d!
 
Example: q = 11, p = 43, r = 10, d = 2 (102 = 1 mod 11). And indeed:  
 
x11+1 = (x+1)(x2+4x+1)(x2+9x+1)(x2+14x+1)(x2+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: male
Posts: 1321
Re: Poly Factorizations  
« Reply #15 on: Jun 26th, 2007, 12:46pm »
Quote Quote Modify Modify

Interesting...
 
Alas, I am too busy with work to do anything about this  Sad
 
Please keep updating this thread with your findings.
 
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Poly Factorizations  
« Reply #16 on: Jun 27th, 2007, 4:18pm »
Quote Quote Modify Modify

on Jun 24th, 2007, 9:21am, Barukh wrote:
How about this?
 
If p = 1 mod q, then xq + 1 is a product of linear factors modulo p.

This only holds if q is odd, in which case xq+1 is equivalent to xq-1.
 
And xq-1 splits into linear factors over Zp 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, rd = 1 mod q for the first time).
 
Then, (xq+1)/(x+1) is a product of (q-1)/d factors of degree d!

You mean, r = p mod q.
 
To prove this, consider a root z of (xq+1)/(x+1) over Fp, and the elements z, zp, zp^2, ....  (There's a sketch of the argument here.)
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Poly Factorizations  
« Reply #17 on: Jun 28th, 2007, 5:36am »
Quote Quote Modify Modify

on Jun 27th, 2007, 4:18pm, Eigenray wrote:

This only holds if q is odd, in which case xq+1 is equivalent to xq-1.

Yes. But what do you mean by "equivalent"?
 
Quote:
You mean, r = p mod q.

Of course...
 
Quote:
To prove this, consider a root z of (xq+1)/(x+1) over Fp, and the elements z, zp, zp^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: male
Posts: 2276
Re: Poly Factorizations  
« Reply #18 on: Jul 1st, 2007, 1:29am »
Quote Quote Modify 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 Fpn with the group Z/pnZ, 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board