This one requires the use of the Chinese Remainder Theorem T

This one requires the use of the Chinese Remainder Theorem

The number 119 factors as 7.17. Use the Chinese remainder theorem to find a solution to the congruence x^2 = 1 mod 119 besides plusminus1 mod 119 by combining solutions to x^2 = 1 mod 7 and x^2 = 1 mod 17. Then use the same method to find a solution to the congruence x^2 = 2 mod 119 using the Chinese remainder theorem. How can yon tell qnickly (using your brain and a pencil, not using Wolfram Alpha) that there are no solutions to x^2 = 3 mod 119?

Solution

X^2=1 mod 119

Hence,

x^2=1 mod 7 and x^2=1 mod 17

1 gives remainder 1 mod 7

2 gives ................. 4 mod 7

3 gives....................2 mod 7

4 gives....................2 mod 7

5 gives ................... 4 mod 7

6 gives .......................1 mod 7

So, x=+-1 mod 7

Now lets look at squares modulo 17

1 gives        1 mod 17

2 gives         4 mod 17

3 gives        9 mod 17

4 gives       16 mod 17

5 gives         8 mod 17

6 gives       2 mod 17

7 gives      -2 mod 17

8 gives       -4 mod 17

So, only +-1 gives 1 mod 17

And same for squares mod 7 so no solutions to :

x^2=1 mod 119 other than\"x=+-1

Now consider:x^2=2 mod 119

As we saw before:x=+-3 mod 7 gives x^2=1 mod 7

x=+-6 mod 17 gives x^2=2 mod 17

So, x=7m+-3

x=17n+-6

So four cases.

Case 1:x=3 mod 7,6 mod 17

x=6,23,40,57,74,91,108

108 =3 mod 7

So, x=108 is one solution

Case 2:x=3 mod 7,-6 mod 17

x=-6,11,28,45,62,79,96

45 =3 mod 7

So, x=45 is one solution

Case 3:x=-3 mod 7,6 mod 17

x=6,23,40,57,74,91,108

74 =-3 mod 7

So, x=74 is one solution

Case 4:x=-3 mod 7,-6 mod 17

x=-6,11,28,45,62,79,96

11 =3 mod 7

So, x=11 is one solution

So all solutions are:

x=11,45,74,108

As we saw in remainders of squares modulo 7 there are no solutions to :

x^2=3 mod 7

Hence no solutions to x^2=3 mod 119