Which one of the following congruences have solutions If so

Which one of the following congruences have solutions? If so how many?

Solution

Only (d) has a solution. To figure out (d),

split the congruence into the two congruences x 2 2 mod 59 x 2 2 0 mod 2 The second one just say that x must be even, so we’ll be done if we can find a solution to the first one that is even. You can use Euler’s criterion to find that there are exactly two solutions to the first one. Let x0 be one of them, and by reducing mod 59 we can assume 0 < x0 < 59. Now if x is a solution, then so is x (mod 59), and by reducing x0 so it’s in the range (0, 59), we can write x0 = 59 x0. Therefore if x0 is even, then x0 is odd, and vice versa, so exactly one of the two solutions is even, and this even solution solves