Find all integer solutions to the pair of congruences (if any) x ≡ 17 (mod 23) 70x ≡ 3 (mod 93).

First, note that , which gives



so in fact we're dealing with the system



Now, 3, 23, and 31 are relatively prime, so we can use the Chinese remainder theorem. But before we do that, we need to rework and ultimately eliminate the coefficients of .

From the second equivalence, it follows immediately is some multiple of 3; this is because is divisible by 3, but 3 doesn't divide 70, so it must divide .

For the third equivalence, we can write . Then modulo 31, we have that , which leaves us with . We want a congruence of the form , and to get that we can multiply and 3 by the inverse of 8 modulo 31.

To find this inverse, we solve for in the relation



by using the Euclidean algorithm, or making just making the observation that , so . Distributing 4 across the third equivalence in our system gives .

So to recap, we now have



and we're ready to use the CRT.

As a starting point, let's take



It's clear that taken modulo 23, the latter two terms vanish and we have a remainder of 17, as desired. 63 is already a multiple of 3, but just to avoid doing more work later, let's multiply each term by 3 anyway to keep getting a remainder of 0:



Now multiply the first two terms by 31 to make sure they vanish when taken modulo 31. Meanwhile, , but we want to get 12, so we would multiply this term by the inverse of 7 mod 31, and again by 12.

We can make a quick observation that , so . Alternatively, you can use the Euclidean algorithm to find this inverse. Either way, we get



So we're told that



is our solution set, where . We can "simplify" this slightly by finding the least positive residue modulo the product of our moduli, which would be



so we end up with



for integers .