Modular Root II

$x^2 + 3x - 7 \equiv x^2 +3x-71x -7 \equiv x^2 - 68x -7 \equiv 0 \pmod{71}$

Thus, $x^2 -68x + 34^2 \equiv (x-34)^2 \equiv 34^2 + 7 \equiv 68\cdot 17 + 7 \equiv (-3)\cdot 17+7 \equiv 27 \pmod{71}$ .

According to Tonelli-Shanks Algorithm , if the prime modulus $p \equiv 3 \pmod{4}$ , then the solution $x-34 \equiv \pm 27^{\frac{71+1}{4}} \equiv \pm 27^{18} \equiv \pm 3^{54} \pmod{71}$ .

Then according to Fermat's Little Theorem , $3^{71-1} \equiv 3^70 \equiv (3^{16})(3^{54}) \equiv 1 \pmod{71}$ .

Then $3^4 \equiv 81 \equiv 10 \pmod{71}$ . $3^8 \equiv 100 \equiv 29 \pmod{71}$ . $3^{16} \equiv 29^2 \equiv 60 \equiv -11 \pmod{71}$ .

Since $11\cdot 13 \equiv 143 \equiv 1 \pmod{71}$ , then $(3^{16})(3^{54}) \equiv (-11)(-13) \equiv 1 \pmod{71}$ .

Thus, $3^{54} \equiv -13 \pmod{71}$ . Then $x \equiv 34 \pm 13 \pmod{17}$ .

Hence, $x \equiv 47 \pmod{71}$ , or $x \equiv 21 \pmod{71}$ .

$$

For the latter congruence, $x^2 - 5x +89x - 16 \equiv x^2 + 84x -16 \equiv 0 \pmod{89}$ .

Similarly, $x^2 +84x +42^2 \equiv 42^2 +16 \equiv 4(21^2 + 4) \equiv 4\cdot 445 \equiv 0 \pmod{89}$ .

Hence, $x + 42 \equiv 0 \pmod{89}$ . $x \equiv -42 \equiv 47 \pmod{89}$ .

As a result, the least possible value of $x = \boxed{47}$ .

It may seem to be different method , but it's virtually same. Nevertheless for sake of variety:

See the second congruence,

Let $x^{2} -5x -16= 89n$

Discriminant $D$ of this quadratic equation

= $89 \times (1+ 4n)$

For $x$ to be integer (+ve)

$D$ is to be a perfect square $4n+1$ is to be like $89 \times p^{2}$ . As 89 is prime .

For smallest we take $p$ = 1 .

We get $x= 47$

To check its smallest , we find it to be satisfying first congruence.

Assumptions : $n$ and $p$ are natural numbers.