2

I have the following congruence: $$x^2 \equiv 106234249 \bmod{12^2}$$

When I tried to solve it, the equation becames in 2 equations:

$x^2 \equiv 4 \bmod{9}$

$x^2 \equiv 9 \bmod{16}$

Because $12^2 = 9 \times 16$ and, 9 and 16 are coprimes.

Then I applied the method of this video, but I obtained 4 results instead of 8.

The following page give me 8 results: https://www.alpertron.com.ar/QUADMOD.HTM

The results that I obtained are:

$x \equiv 83 \bmod{12^2}$

$x \equiv 29 \bmod{12^2}$

$x \equiv 115 \bmod{12^2}$

$x \equiv 61 \bmod{12^2}$

There are 4 results missing.

Where am I wrong? How to solve it?

Blue
  • 75,673
Pedro Urday
  • 91

1 Answers1

2

When you solved $x^2 \equiv 4 \pmod 9$, the only solutions are $x \equiv ±2 \pmod 9$. This is because if $x = 3k ± 2, x^2 = 9k^2 ± 12k + 4$ and $±3k + 4$ is never a multiple of $9$.

However, solving $x^2 \equiv 9 \pmod {16}$ is different. When $x = 16k ± 3$, $x^2 \equiv ±(2 \cdot 16k \cdot 3) + 9 \equiv 9 \pmod {16}$. This leads to the fact that $x = 8k ± 3$ is also a solution as $2 \cdot 8k \cdot 3$ is still divisible by $16$.

Each possible combination gives a distinct solution using CRT, hence there are $8$ solutions in total.

Toby Mak
  • 16,827
  • A precondition is that the two numbers must be coprime, which is true in this case as $\text{gcd} (4,9) = \text{gcd} (9,16) = 1$. – Toby Mak Dec 22 '21 at 01:33