Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quadratic formula in Z_n

  1. Sep 3, 2012 #1
    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.
  2. jcsd
  3. Sep 3, 2012 #2
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook