Author |
Topic: Poly Factorizations (Read 1221 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Poly Factorizations
« on: Jun 18th, 2007, 12:01pm » |
 Quote  Modify
|
Has this been posted before? 
Factorize the polynomial x3 + 1 modulo prime p.
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Poly Factorizations
« Reply #1 on: Jun 18th, 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)(x2 - x + 1) ?
|
| « Last Edit: Jun 18th, 2007, 12:19pm by Aryabhatta » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Poly Factorizations
« Reply #2 on: Jun 18th, 2007, 1:18pm » |
Quote Modify
|
Is x^2-x+1 always irreducible mod p, though?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Poly Factorizations
« Reply #3 on: Jun 18th, 2007, 2:10pm » |
Quote Modify
|
Does "factorize" always imply irreducible factors?
Anyway, I understand the question now 
|
| « Last Edit: Jun 18th, 2007, 2:11pm by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Poly Factorizations
« Reply #4 on: Jun 19th, 2007, 1:37am » |
Quote 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:
Posts: 2276
|
|
Re: Poly Factorizations
« Reply #5 on: Jun 19th, 2007, 5:48am » |
Quote 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! 
Can you elaborate?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Poly Factorizations
« Reply #6 on: Jun 19th, 2007, 9:21am » |
Quote 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:
Posts: 1321
|
|
Re: Poly Factorizations
« Reply #7 on: Jun 19th, 2007, 10:08pm » |
Quote 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:
Posts: 2276
|
|
Re: Poly Factorizations
« Reply #8 on: Jun 20th, 2007, 7:08am » |
Quote Modify
|
Nicely done, Aryabhatta!
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:
Posts: 1321
|
|
Re: Poly Factorizations
« Reply #9 on: Jun 20th, 2007, 10:05am » |
Quote 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:
Posts: 1321
|
|
Re: Poly Factorizations
« Reply #10 on: Jun 21st, 2007, 10:21am » |
Quote 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:
Posts: 2276
|
|
Re: Poly Factorizations
« Reply #11 on: Jun 21st, 2007, 11:20am » |
Quote Modify
|
on Jun 21st, 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 22nd, 2007, 3:55am » |
Quote 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:
Posts: 2276
|
|
Re: Poly Factorizations
« Reply #13 on: Jun 24th, 2007, 9:21am » |
Quote 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:
Posts: 2276
|
|
Re: Poly Factorizations
« Reply #14 on: Jun 26th, 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, 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:
Posts: 1321
|
|
Re: Poly Factorizations
« Reply #15 on: Jun 26th, 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 27th, 2007, 4:18pm » |
Quote 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:
Posts: 2276
|
|
Re: Poly Factorizations
« Reply #17 on: Jun 28th, 2007, 5:36am » |
Quote 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:
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:
Posts: 2276
|
|
Re: Poly Factorizations
« Reply #18 on: Jul 1st, 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 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print