# Thread: need help by tonight PLEASE!!!

1. ## need help by tonight PLEASE!!!

How do I solve these kind of quadratic congruence problems?!

x^2 is congruent to 53 mod 143

I said 143=11x13

so x^2 is congruent to 53 mod 11 AND x^2 is congruent to 53 mod 13

where do i go from there?! Please any help would be great..My final is tomorrow and this is the only thing that is confusing me!!

2. Originally Posted by kel1487
How do I solve these kind of quadratic congruence problems?!

x^2 is congruent to 53 mod 143

I said 143=11x13

so x^2 is congruent to 53 mod 11 AND x^2 is congruent to 53 mod 13

where do i go from there?! Please any help would be great..My final is tomorrow and this is the only thing that is confusing me!!
That's the right way to start. Then $53\equiv 9\pmod{11}$, and the equation $x^2\equiv9\pmod{11}$ has solutions $x\equiv\pm3\pmod{11}$. Also, $53\equiv 1\pmod{13}$, and the equation $x^2\equiv1\pmod{13}$ has solutions $x\equiv\pm1\pmod{13}$.

So we are looking for numbers of the form (multiple of 11) ±3, that are also of the form (multiple of 13) ±1. The easiest way to find such numbers is simply to go through the multiples of 11, looking at the numbers ±3 from these, and seeing if they are within ±1 of a multiple of 13.

The first one we find is 14 (=11+3=13+1).

Then 25 (=22+3=26-1); 118 (=121-3=117+1); and 129 (=132-3=130-1).

So there are four solutions, $x\equiv 14, 25, 118, 119\pmod{143}$.