# Find all solutions of $x^2 \equiv 9 \pmod{85}$

I am asked to solve this problem, and I know how to solve congruences of degree $$2$$ modulo a prime $$p$$, but note that $$85=5\cdot 17$$ is a product of two primes.

On the fly I managed to rewrite the expression as $$(x-3)(x+3)\equiv 0 \pmod{85}$$, and then since $$(5,17)=1$$, $$5\cdot 17 | (x-3)(x+3)$$ implies $$5|(x-3)(x+3)$$ and $$17|(x-3)(x+3)$$.

Thus I tried expanding to two simultaneous congruences where the moduli are prime:

$$x^2 \equiv 9 \equiv 4 \pmod{5}$$ $$x^2 \equiv 9 \pmod{17}$$

which I now know how to solve, for instance, the first congruence can be done by inspection as $$x\equiv 2,3$$ are the only such solutions (there are only four to check). I further conclude that $$x=2+5k,3+5k'$$ for $$k,k' \in \mathbb{Z}$$, and plug these values into the second equation:

$$(2+5k)^2 \equiv 4+10k+10k+25k^2 \equiv 4+20k+25k^2 \equiv 4+3k+8k^2 \equiv 9 \pmod{17}$$ $$(3+5k')^2 \equiv 9+15k'+15k'+25k'^2 \equiv 9+30k'+25k'^2 \equiv 9+13k'+8k'^2 \equiv 9 \pmod{17}$$

thus $$8k^2+3k-5\equiv 0 \pmod{17}$$ and $$8k'^2+13k' \equiv 0 \pmod{17}$$ where $$d=b^2-4ac = (3)^2-4(8)(-5)=13^2$$ and $$d'=b^2-4ac = 13^2-4(8)(0)=13^2$$ thus from my book it states that both are solvable and with solutions:

$$k = \frac{-3\pm 13}{16}$$ $$k'=\frac{-13 \pm 13}{16}$$

where $$\frac{1}{16}=16$$ is the inverse of $$16$$ modulo $$17$$ thus we get:

$$k\equiv (-3+13)\cdot 16 \equiv 10\cdot 16 \equiv 160 \equiv 7 \pmod{17}$$

$$k \equiv (-3-13)\cdot 16 \equiv -16\cdot 16 \equiv -(16)^2 \equiv -1 \equiv 16 \pmod{17}$$

$$k'\equiv (-13+13)\cdot 16 \equiv 0\cdot 16 \equiv 0 \pmod{17}$$

$$k' \equiv (-13-13)\cdot 16 \equiv -26\cdot 16 \equiv -8 \equiv 9 \pmod{17}$$

and finally $$2+5(7+17\ell) =37 +85\ell, \:\:2+5(16+17\ell) =82 +85\ell,\:\:3+5(0+17\ell) =3 +85\ell,\:\:3+5(9+17\ell) =48 +85\ell$$ for $$\ell \in\mathbb{Z}$$.

$$x \equiv 3,37,48,82\pmod{85}$$. I ran a computer check and it gave me the same four numbers so I guess it's correct.

Is my approach correct?

Maybe I was lucky with this method for this particular problem, but I'm wondering when would my approach break down?

Because I've never seen congruences of degree $$2$$ where the modulus is not prime, let alone powers or multiples of primes.

• I've reopened the question. In the future: could we maybe at least explain to the user how to find the information they are looking for in the "duplicate" that is not an exact duplicate? If we're more experienced this may seem an easy task, but usually OPs are learning the ropes and making the connection is not immediate!
– Pedro
Apr 7, 2021 at 10:08
• Here you can find the generic method to solve your problem.
– Pedro
Apr 7, 2021 at 10:09

Your method is absolutely correct, and it works generically under the name of "Chinese Remainder Theorem". Essentially, the result says that if $$m_1,\ldots,m_t$$ are pairwise coprime then a system of equations of the form

$$\begin{cases} x= a_1 \mod m_1 \\ \hphantom{W}\vdots \\ x= a_t \mod m_t \end{cases}$$

has a unique solution modulo $$m = m_1\cdots m_t$$. The algorithm you followed to find solutions is indeed correct, and is one way of approaching your problem.

Another quicker way goes as follows:

1. from $$x^2=9\mod 17$$ you get that $$x=3$$ or that $$x=-3=14 \mod 17$$, since $$17$$ is prime.
2. from $$x^2=4\mod 5$$ you get that $$x=2$$ or that $$x=-2=3\mod 5$$, since again $$5$$ is prime.

Now you need to find $$x$$ such that $$(x\mod 5,x\mod 17) = (a,b)$$ where $$(a,b)$$ runs through the four possible pairs you have obtained. To do this, you can note that the inverse of $$5$$ modulo $$17$$ is $$7$$, and hence all answers are obtained by computing

$$a+5\cdot 7\cdot(b-a) \mod 85.$$

This indeed what you obtained.