Show Reducibility of x^4+1 Modulo p

  • Thread starter Palindrom
  • Start date
In summary, It is suggested to show that x^4+1 has a root in some odd extension of Zp, which would then force that root to be in Zp. It is also mentioned that a maple experiment shows that x^4+1 rarely has a root mod p when p is prime. The conversation then goes on to discuss different approaches for proving that x^4+1 is reducible modulo p, including trying to factor it into two quadratics. The idea is then presented to solve a system of equations to find a root mod p, and it is noted that this method relies on whether or not -1 has a square root mod p. The conversation then moves on to discuss Wilson's Theorem and the Legend
  • #1
Palindrom
263
0
Hi!

I need to show that x^4+1 is reducible modulo p for all prime p.

I was thinking to show that it has to have a root in some odd extension of Zp, which would force that root to be in Zp. Am I on the right track?
 
Physics news on Phys.org
  • #2
A quick maple experiment seems to show that x^4+1 rarely has a root mod p where p is prime. You can probably show it factors into two quadratics.
 
  • #3
No squares are reducible modulo p where p==3 Mod 4.

Take [tex]X^4+1 \equiv 0 Mod 3[/tex]
 
Last edited:
  • #4
This problem seems to be equivilant to saying that either -1 has a squareroot or 4 has a 4th root mod p. I seem to recall that -1 has a squareroot iff p is congruent to 1 mod 4. Can it be shown (easily) that if p prime is congruent to 3 mod 4 that 4 has a fourth root mod p?

Steven
 
  • #5
Did you ever figure out how to show that [tex]X^4+1[/tex] factors mod p for any prime p? I finally figured out one way to show it but it is long and complicated. I would love to see a simple way. I will share the complicated way if anyone is really interested.

Steven
 
  • #6
That would be interesting.
 
  • #7
Well, it's already been suggested to try factoring into two quadratics. The obvious "simple" thing to try is:

x^4 + 1 = (x^2 + a) (x^2 + b) = x^4 + (a + b) x^2 + ab

So all you need to do is solve the system:

a+b = 0
ab = 1

modulo p. Can you do that? Guess only if -1 has a square root.


So, try the generic case:

(x^2 + ax + b) (x^2 + cx + d) = x^4 + (a + c) x^3 + (b + d + ac) x^2 + (ad + bc) x + bd

So,

a + c = 0
b + d + ac = 0
ad + bc = 0
bd = 1

If a is not zero, solving this comes down to whether one of m and -m have a square root mod p (For a particular m). That is guaranteed to be true if, *drumroll*, -1 does not have a square root!
 
  • #8
Well yeah... the m you're looking for in this case is m=2. And if [tex]p\equiv 3 (mod\,4)[/tex] then either 2 or -2 has a square root (in fact for every m, either [tex]\pm m[/tex] has a square root). And if [tex] p\equiv 1(mod\, 4)[/tex] then -1 has a square root. But showing this is basically the same as proving Wilson's theorem (well not quite) and isn't that trivial. I was hoping there would be something simpler like some trick that shows that [tex]\mathbb{Z}_p[x]/<x^4+1>[/tex] can't be a field.
 
  • #9
The proof doesn't actually care when -1 has a square root mod p -- just that one method works when it does, and the other when it does not.

In any case, Wilson's theorem has been proven, so it's fair game to use. :smile: (And I'm using Quadratic Recipricosity! heaven forbid!)


Well, I have a proof that Zp[x] / <x4 + 1> can't be a field... it starts off by assuming x4 + 1 factors as (x2 + a) (x2 + b) (modulo p) ... :biggrin:
 
  • #10
I'm clearly a little dense today (and I should clearly be trying to sleep and not reading physicsforums) but why is it clear that either -1 has a square root or [tex]\pm m[/tex] has a square root for each prime. I'm sure it's something simple that I'm missing but I'm just not seeing it.

Steven
 
  • #11
If -1 is present as a quadratic residue, then so is -A, since there is an X present such that [tex]X^2*A \equiv -A \equiv -u^2 \equiv (Xu)^2 Mod p[/tex]

In the other case, if both A and -A are present as quadratic residues, then (X/Y)^2 == A/-A ==-1 Mod p.

Wilson's Theorem (Wilson became a lawyer and never proved his theorem so I have been told) is not hard to prove if we assume that the integers Modulo p form a group. Then every element has its inverse in the group, but the only cases of X^2 ==1 Mod p are X=1 and X=-1.

So the product (p-1)! Modulo p, links every element with its inverse except 1 and -1, so the product comes out: [tex] (p-1)! \equiv -1 Mod p[/tex]

Now if we go on with that, if we split the group into (p-1)/2 successive groups of integers, then we have: [tex](p-1)! \equiv {((p-1)/2)!}^2 *(-1)^_(p-1)/2 [/tex] Consequently if p is congruent to 1 Mod 4, then there is an X such that X^2==(p-1)! ==-1 Mod p.
 
Last edited:
  • #12
Use the Legendre symbol:

If -1 does not have a square root, then (-1/p) = -1.
Since the symbol is multiplicative, we have (-m/p) = (-1/p)(m/p) = -(m/p), so that one of the two must be 1.
 

1. How do you show the reducibility of x^4+1 modulo p?

To show the reducibility of x^4+1 modulo p, we need to factor the polynomial into two non-constant polynomials with coefficients in the field modulo p. This means finding two polynomials f(x) and g(x) such that x^4+1 = f(x)g(x) (mod p).

2. Why is it important to show the reducibility of x^4+1 modulo p?

Showing the reducibility of x^4+1 modulo p helps us understand the structure of the field modulo p. It also allows us to find roots of the polynomial and use them in various computations.

3. What is the relationship between the reducibility of x^4+1 modulo p and the roots of the polynomial?

If x^4+1 is reducible modulo p, it means that the polynomial has at least one root in the field modulo p. On the other hand, if x^4+1 is irreducible modulo p, it means that the polynomial has no roots in the field modulo p.

4. Can you use any method to show the reducibility of x^4+1 modulo p?

There are various methods to show the reducibility of x^4+1 modulo p, such as trial and error, using the quadratic formula, or applying the Eisenstein criterion. The most efficient method may vary depending on the value of p.

5. How can you prove that x^4+1 is irreducible modulo p?

To prove that x^4+1 is irreducible modulo p, we can use techniques such as the rational root theorem, the Eisenstein criterion, or the irreducibility of a polynomial over a larger field. If none of these methods work, it is possible that x^4+1 is actually reducible modulo p, but we have not found the correct factorization yet.

Similar threads

  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
11
Views
1K
Replies
4
Views
5K
  • Linear and Abstract Algebra
Replies
2
Views
761
  • Linear and Abstract Algebra
Replies
1
Views
730
  • Linear and Abstract Algebra
Replies
12
Views
8K
  • Linear and Abstract Algebra
Replies
2
Views
842
  • Linear and Abstract Algebra
Replies
2
Views
916
  • Linear and Abstract Algebra
Replies
2
Views
6K
Back
Top