# Show reducibility

1. May 25, 2005

### Palindrom

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?

2. May 25, 2005

### snoble

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. May 26, 2005

### robert Ihnot

No squares are reducible modulo p where p==3 Mod 4.

Take $$X^4+1 \equiv 0 Mod 3$$

Last edited: May 26, 2005
4. May 26, 2005

### snoble

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. May 28, 2005

### snoble

Did you ever figure out how to show that $$X^4+1$$ 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. May 28, 2005

### robert Ihnot

That would be interesting.

7. May 28, 2005

### Hurkyl

Staff Emeritus
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
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. May 28, 2005

### snoble

Well yeah... the m you're looking for in this case is m=2. And if $$p\equiv 3 (mod\,4)$$ then either 2 or -2 has a square root (in fact for every m, either $$\pm m$$ has a square root). And if $$p\equiv 1(mod\, 4)$$ 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 $$\mathbb{Z}_p[x]/<x^4+1>$$ can't be a field.

9. May 28, 2005

### Hurkyl

Staff Emeritus
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. (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) ...

10. May 29, 2005

### snoble

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 $$\pm m$$ 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. May 29, 2005

### robert Ihnot

If -1 is present as a quadratic residue, then so is -A, since there is an X present such that $$X^2*A \equiv -A \equiv -u^2 \equiv (Xu)^2 Mod p$$

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: $$(p-1)! \equiv -1 Mod p$$

Now if we go on with that, if we split the group into (p-1)/2 successive groups of integers, then we have: $$(p-1)! \equiv {((p-1)/2)!}^2 *(-1)^_(p-1)/2$$ 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: May 29, 2005
12. May 29, 2005

### Hurkyl

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