wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Poly Factorizations
        
(Message started by: Barukh on Jun 18th, 2007, 12:01pm)
Title: Poly Factorizations
Post by Barukh on Jun 18th, 2007, 12:01pm
Has this been posted before?  ???

Factorize the polynomial x3 + 1 modulo prime p.
Title: Re: Poly Factorizations
Post by Aryabhatta on Jun 18th, 2007, 12:19pm
Note sure If this has been asked before, but I don't understand the question.

What is wrong with (x+1)(x2 - x + 1) ?
Title: Re: Poly Factorizations
Post by Obob on Jun 18th, 2007, 1:18pm
Is x^2-x+1 always irreducible mod p, though?
Title: Re: Poly Factorizations
Post by Aryabhatta on Jun 18th, 2007, 2:10pm
Does "factorize" always imply irreducible factors?

Anyway, I understand the question now ;D
Title: Re: Poly Factorizations
Post by Aryabhatta on Jun 19th, 2007, 1:37am
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)
Title: Re: Poly Factorizations
Post by Barukh on Jun 19th, 2007, 5:48am

on 06/19/07 at 01:37:11, 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!  :D

Can you elaborate?
Title: Re: Poly Factorizations
Post by Aryabhatta on Jun 19th, 2007, 9:21am
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.
Title: Re: Poly Factorizations
Post by Aryabhatta on Jun 19th, 2007, 10:08pm
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.
Title: Re: Poly Factorizations
Post by Barukh on Jun 20th, 2007, 7:08am
Nicely done, Aryabhatta!  :D

But:


on 06/19/07 at 22:08:58, 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?
Title: Re: Poly Factorizations
Post by Aryabhatta on Jun 20th, 2007, 10:05am

on 06/20/07 at 07:08:41, Barukh wrote:
But:

I think p=2 should be excluded.


Yes, you are right.
Title: Re: Poly Factorizations
Post by Aryabhatta on Jun 21st, 2007, 10:21am

on 06/20/07 at 07:08:41, 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?
Title: Re: Poly Factorizations
Post by Barukh on Jun 21st, 2007, 11:20am

on 06/21/07 at 10:21:02, Aryabhatta wrote:
Do you know of a solution to this?

Partially...  :o

The more interesting may be the discussion!  ;)
Title: Re: Poly Factorizations
Post by Barukh on Jun 22nd, 2007, 3:55am
Example:

x5+1 = (x+1)(x+36)(x+84)(x+87)(x+95) mod 101
Title: Re: Poly Factorizations
Post by Barukh on Jun 24th, 2007, 9:21am
How about this?

If p = 1 mod q, then xq + 1 is a product of linear factors modulo p.
Title: Re: Poly Factorizations
Post by Barukh on Jun 26th, 2007, 12:58am
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.
Title: Re: Poly Factorizations
Post by Aryabhatta on Jun 26th, 2007, 12:46pm
Interesting...

Alas, I am too busy with work to do anything about this  :(

Please keep updating this thread with your findings.
Title: Re: Poly Factorizations
Post by Eigenray on Jun 27th, 2007, 4:18pm

on 06/24/07 at 09:21:34, 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 [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?action=display;board=riddles_putnam;num=1182193300;start=0#4]here[/link].


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 [hide]z, zp, zp^2, ...[/hide].  (There's a sketch of the argument [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam&action=display&num=1156557417&start=8#8]here[/link].)
Title: Re: Poly Factorizations
Post by Barukh on Jun 28th, 2007, 5:36am

on 06/27/07 at 16:18:56, 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 [hide]z, zp, zp^2, ...[/hide].  (There's a sketch of the argument [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam&action=display&num=1156557417&start=8#8]here[/link].)

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.
Title: Re: Poly Factorizations
Post by Barukh on Jul 1st, 2007, 1:29am
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.


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