wu :: forums « wu :: forums - Poly Factorizations » Welcome, Guest. Please Login or Register. Sep 17th, 2024, 2:44pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Eigenray, william wu, towr, Icarus, SMQ, Grimbal)    Poly Factorizations « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 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)

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

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...

 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:
 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:
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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »