Quadratic formula in Z_n

  • Thread starter lol_nl
  • Start date
  • #1
41
0
Working through A Book of Abstract Algebra, I encountered several exercises on roots of polynomials in [itex]Z_{n}[/itex] I was just wondering whether there exists something like a quadratic equation for polynomials of degree 2. If the solutions of the usual quadratic formula happen to be integers, can one simply take these modulo n to find solutions of the quadratic in [itex]Z_{n}[/itex]? What if they are not integers? Clearly a field extension is needed to find solutions, but how does this precisely work?

As an example, consider the equation [itex]x^{2} + x + 1 = 0[/itex] in [itex]Z_{2}[/itex]. The quadratic equation gives [itex]x = -\frac{1}{2} \pm \frac{1}{2} i[/itex]. Suppose you name the positive root as c. Then [itex]Z_{2}(c) = {0,1,c,1+c}[/itex] is the field extension. Now can one work with c in the same way as with [itex]x = -\frac{1}{2} \pm \frac{1}{2} i[/itex]? Clearly, you easily get contradictions like [itex]1 = -1 = 2c-1 = 3i = i[/itex] and so on.
 

Answers and Replies

  • #2
22,089
3,296
Maybe it's a good first step to identify a good field extensions that allows you to have roots.

If we have the polynomial [itex]X^2+X+1[/itex] in [itex]\mathbb{Z}_2[/itex], then we can look at the polynomial ring [itex]\mathbb{Z}_2[c][/itex].
Now, we let [itex]F=\mathbb{Z}_2[c]/(c^2+c+1)[/itex] the quotient of the polynomial ring with the ideal [itex](X^2+X+1)[/itex]. This is again a field, as is easily checked.

The elements of F are [itex]\{0,1,c,c+1\}[/itex] as you suspected.
Now, an important feature of this field is that [itex]c^2=-c-1[/itex]. This allows you to multiply all numbers in the field.

Now, you can not work with c as you can work with [itex]-\frac{1}{2}\pm \frac{1}{2}i[/itex]. One reason for that is already that [itex]\frac{1}{2}[/itex] doesn't make any sense in [itex]\mathbb{Z}_2[/itex]

If you want to work with an analogous things as i then you will have to look for solutions to the equation [itex]X^2+1=0[/itex]. Clearly, X=1 is the only solution to this equation. So in this case, there is no need to make an element i such that [itex]i^2=-1[/itex]. We already have such an element. That is: i=1. So if you work in F or in [itex]\mathbb{Z}_2[/itex], then you can safely say i=1. Even better: you don't need to talk about i.
 

Related Threads on Quadratic formula in Z_n

  • Last Post
Replies
1
Views
2K
Replies
3
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
7
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
15
Views
5K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
4
Views
2K
Top