Find all values of x that are simultaneously a solution to the congruences x ≡ 2 (mod 3), x ≡ 1 (mod 5), x ≡ 3 (mod 29).

Let's start by supposing . Modulo 3, we end up with 2 as needed.

But modulo 5, we want to get 1, so we'd need to multiply the first and last terms by 5 and the second term by the inverse of 3 modulo 5. We have , so we multiply by 2:



But now modulo 3, the first term gives a remainder of 1, so simply multiply by 2:



Next, modulo 29, we can force the first two terms to vanish by multiplying them by 29, but the last term still yields 15. We want to get 3 on its own, so we could just multiply the third term by the inverse of 5 modulo 29. We have .



Now, , so we need to multiply the first term by 2 one more time; , so we need to multiply the second term by the inverse of 4 modulo 5, which would be 4 since ; and , so the last term is okay.



We know 1946 is a possible solution because we engineered it that way, but it's not the smallest positive solution. We have



The general solution to the system is then , where .