Maths WorkshopMaths problems with full solutions
Exercise 2112Number theory › CongruencesOlympiadAdded 3 Nov 2026

Square roots modulo $p$

#square roots#mod p#Tonelli-Shanks

Statement

Find all square roots of 22 modulo 1717.

Hint

Test residues 1,…,161,\ldots,16.

Show solutionHide solution

Solution

Squares mod 17.
- 12=11^2=1, 22=42^2=4, 32=93^2=9, 42=16≡−14^2=16\equiv-1, 52=25≡85^2=25\equiv8
- 62=36≡26^2=36\equiv2 ✓, 72=49≡157^2=49\equiv15, 82=64≡138^2=64\equiv13
- 92≡139^2\equiv13, 102≡1510^2\equiv15, 112≡211^2\equiv2 ✓, 122≡812^2\equiv8
- Symmetry from 13213^2 onwards.

Solutions. 66 and 1111 (since 6+11=176+11=17, symmetric roots).

Check. 62=36≡26^2=36\equiv2, 112=121≡2(mod17)11^2=121\equiv2\pmod{17}. Correct.

Conclusion. x2≡2(mod17)x^2\equiv2\pmod{17} has solutions x≡6x\equiv6 or 11(mod17)11\pmod{17}.