Find all the square roots of x^2 = 53 (mod 77) by hand. 2 marks

The four answers to this problem are: x = 19, 30, 47, 58 (mod 77)

Step-by-step explanation:

Note that 77 = (11)(7), so we can rewrite the equation as it follows

1)

And

2)

We will work with 1) first

From this last equation we have that x= 8 (mod 11) and x=3 (mod 11)

Now we will solve 2)

From this last equation we have that x=5 (mod 7) and x=2 (mod7)

Now we have 2 different pair of solutions, we're going to work with one equation modulo 11 and one modulo 7 at a time: because of  the Chinese Remainder Theorem we know that each pair of equations has an answer mod 77.

Pair 1)

We rewrite the second equation as x = 7y +5, we substitute x in the first equation and we have:

7y + 5 = 8 (mod 11)

y = 2 (mod 11)

Now we rewrite this last equation as y = 11z + 2 and we will substitute this in x = 7y + 5

x = 7(11z + 2) + 5

x = 77z +14 + 5

x = 77 z + 19

x= 19 (mod 77)

Pair 2)

We will follow the same procedure:

x = 7y +2

7y + 2 = 8 (mod 11)

y = 4 (mod 11)

⇒y = 11z + 4

x = 7(11z + 4) + 2

x = 77z +28 + 2

x= 77z + 30

x = 30 (mod 77)

Pair 3)

x = 7y + 5

7y + 5 = 3 (mod 11)

y = 6 (mod 11)

⇒y =11z + 6

x = 7 (11z + 6) + 5

x = 77z + 42 + 5

x = 47 (mod 77)

Pair 4)

x = 7y + 2

7y + 2= 3 (mod 11)

y = 8 (mod 11)

⇒y = 11z + 8

x = 7 (11z + 8) + 2

x = 77z + 56 + 2

x = 58 (mod 77)