Question

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

Answer 1

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

Explanation:

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

1)
`x^(2) =53(mod11)\\x^(2) =9(mod11)`

And

2)
`x^(2) =53(mod7)\\x^(2) =4(mod7)`

We will work with 1) first

`x^(2) =9(mod11)\\x^(2) -9=0(mod11)\\(x+3)(x-3)=0(mod11)`

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

Now we will solve 2)

`x^(2) =4(mod7)\\x^(2) -4=0(mod7)\\(x+2)(x-2)=0(mod7)`

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)
`x=8(mod11)\\x=5(mod7)\\`

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)
`x=8(mod 11)\\x=2(mod7)`

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=3(mod11)\\x=5(mod7)`

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=3(mod11)\\x=2(mod7)`

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)