Find four square roots of 2833 modulo 4189. (The modulus factors as 4189 = 59 · 71. Note that your four square roots should be distinct modulo 4189.)Hoffstein, Jeffrey. An Introduction to Mathematical Cryptography (Undergraduate Texts in Mathematics) (p. 112). Springer New York. Kindle Edition.

Step-by-step explanation:

Let us proceed to find square roots of modulo 59 and 71:

 ≡  2833  mod  59  ≡  1  mod 59                             (1)

 ≡  2833  mod  71  ≡  64  mod 71                            (2)

By inspection, we find that = ± 1 and = ± 8 works

Now, using Chinese remainder to solve the simultaneous congruence,

≡

The first congruence yields

Then putting this back into the second equation, we get

≡ ⇒ ≡ ⇒ ≡

But

≡ ;

Hence,

≡ ⇒ ≡

This shows that  is a third square root. From this, we immediately get the fourth square root, namely ≡ .

Note that the square roots:

are all distinct modulo 4189.