1

So I am preparing for a weekly test at my uni and I have a problem like this:

Find the solutions of the equations in fields $Z_7, Z_{11}, Z_{13}$.

And I'm thinking about the approach for solving such things. Never did that before and what I'd like to know is what methods I should apply.

Say i have $5x^2 + 5x + 1$. If I wanted to do it the "regular" way, I'd do $\Delta = 25(\mod7) - 20(\mod7) = 4 - 6 = 5$. The problem arises later, when I'd have to use $\frac{-b-\sqrt{\Delta}}{2a}$ for example - how do I take a square root then? And is it even a good path I'm treading?

Gerry Myerson
  • 179,216
Straightfw
  • 1,558
  • Five has a square root in $\Bbb{Z}_{11}$ given that $$4^2=16\equiv 5\pmod{11}.$$ Check the other fields (by brute force testing if necessary). – Jyrki Lahtonen Mar 19 '14 at 16:43
  • @JyrkiLahtonen - Thank you. But in a case like $Z_7$, there is no square root of five, right? It'd have to be some $k^2 \equiv 5 (\mod 7)$ but then we'd need $7r+5$ being a square of some integer and there is none. Does this mean there are no solutions to the $Z_7$ case? – Straightfw Mar 19 '14 at 17:02
  • Correct. If you have $\Delta<0$, the conclusion is that there are no roots in the field of real numbers, because there is no $\sqrt{\Delta}$ there. It's the same here. – Jyrki Lahtonen Mar 19 '14 at 17:07
  • @JyrkiLahtonen - I see, thank you. One last question: is there a way to do it other than brute force? In the $Z_7$ case, what I wrote above is true but it was only my guess and I wasn't sure of it until I made Wolfram check if there is no $k$ such that $k^2 \equiv 5 (\mod 7)$ and I guess such guesses won't be treated too nicely on the test. Is there a better way or I'd just have to prove that there is no such k in some fancy way on the test? – Straightfw Mar 19 '14 at 17:13
  • Do you know about Legendre symbols and quadratic residues? A nonzero integer $a$ is a square in $\mathbb{F}_p \Leftrightarrow a^{\frac{p-1}{2}} \equiv 1 , (\textrm{mod}, p)$.

    If not, in a test it would be fairly easily to calculate ${x^2 : x \in \mathbb{F}_p}$ for small $p$.

     – ah11950 Mar 21 '14 at 12:34

1 Answers1

0

Since $\mathbb{Z}_{i}$ where $i=7,11,13$ are fields so you can use the fact that if $p(x)=f(x).g(x)$ then atleast one of them should be zero. In cases when $i$ is small the best strategy is to find a root say $a$ thus observing that $(x-a)$ is a factor and then follow long division to reduce the given polynomial into polynomials of smaller degree.

wanderer
  • 2,928