find a solution of each of the following congruences

Question

a. x²≡ -1 (mod 13)

b. x² ≡-1 (mod 17)

Answer 1

Keep making subsequent additions of 13 or 17 (i.e. congruences) until you reach a square term

 

a)

-1 (mod 13) ≡ 12 (mod 13) ≡ 25 (mod 13)

Thus x² ≡ 25 (mod 13) so you can square root both sides to get:

x ≡ 5 (mod 13)

 

b)

-1(mod 17) ≡ 16 (mod 17)

x² ≡ 16 (mod 17)

x ≡ 4 (mod 17)