1

So, we were tasked to solve the following equation in $\mathbb{Z}_8$: $[2]x^2+[7]x+[1]=0$. Is there any way to approach these problems other than trying every possible value? (I mean, using ring properties or something like that) Because if the problem was about $\mathbb{Z}_{56}$ then it would be a very hard task. Any help is appreciated.

Pedro García
  • 232
  • 2
  • 9
  • Even $\pmod {56}$, trial and error is very rapid. You can simplify your life by factoring your modulus and using [Tonelli-Shanks](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) for primes. Note that extracting square roots modulo composite numbers is equivalent to factoring, which makes this quite a hard problem in general. – lulu Jan 01 '22 at 21:09

2 Answers2

0

A general method: lift (easy) roots $\!\bmod 2\,$ to $\!\bmod 2^3$ by Hensel's Lemma (Newton's method). Here we have $\,f(x)\equiv 2x^2\!-\!x\!+\!1\pmod{\!8}\,$ so

$\!\!\bmod 2\!:\,\ 0\equiv f(x)\equiv 2x^2\!-\!x\!+\!1\equiv -x\!+\!1$ $\iff x\equiv 1,\,$ so $\,\color{#c00}{x = 1\!+\!2y}$

$\!\!\bmod 8\!:\,\ 0 \equiv f(\color{#c00}x)\equiv 2(\color{#c00}{1\!+\!2y})^2\!-\!(\color{#c00}{1\!+\!2y})\!+\!1\equiv -2y\!+\!2$ $\overset{\div\ 2}\iff \bmod 4\!:\ 0\equiv -y\!+\!1$ $\iff y = 1\!+\!4n\iff x = 1\!+\!2y = 3\!+\!8n\equiv 3\pmod{\!8}$

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
  • We implicitly used $\, y\equiv a\pmod{\!4}\!\iff\! 2y\equiv 2a\pmod{\!8},\,$ by $\,4\mid y-a\!\iff\! 8\mid 2(y-a).\,$ More generally see [here](https://math.stackexchange.com/q/1883921/242) for scaling and cancellation of congruences. – Bill Dubuque Jan 02 '22 at 07:53
-2

First observe that in $Z_8$, $7 = - 9, 1 = 9$. This allows you to factor it as $(2x-3)(x-3) = 0$. Thus $x - 3 = 0 \implies x = 3$ or $2x - 3 = 0$ which yields no solution in $Z_8$. All the other possibilities are ruled out. For example: $x-3 = 2, 2x-3 = 4$ simmulatneously leads to no solution. Thus the only answer is $x = 3$.

Wang YeFei
  • 5,830
  • 1
  • 5
  • 19
  • 1
    Guessing the correct factors is almost the same as guessing the correct zeroes. This is not a method that can be used for a larger modulus. – miracle173 Jan 02 '22 at 07:12