For some reason, I can't follow how this works. I think I can understand how to find an x congruent to two different values modulo two different primes, but applying this iteratively somehow eludes me. Anyway, the problem from the sheet is: Find a value for x that satifies \( x \equiv 2\; (mod 3),\; x \equiv 3\; (mod 5),\; x \equiv 4\; (mod 11),\; x \equiv 5\; (mod 16) \) So, we want a number such that \( x \equiv a\; mod ( 3 \cdot 5 \cdot 11 \cdot 16) \), for some integer a. One way to find solutions is to substitute equivalences, which for the first congruence is x = 3s + 2, so we have \(3s + 2 \equiv 3\; (mod 5) \)which is the same as \(3s \equiv 1\; (mod 5) \)so \(3^{-1}3s \equiv 3^{-1} 1\; (mod 5) \)the inverse of 3 modulo 5 is 2, so \(s \equiv 2\; (mod 5) \)
We have x = 3s + 2 and s = 5t + 2, so x = 3(5t + 2) + 2. Then x = 15t + 8. So we iterate: \( 15t + 8 \equiv 4 (mod 11) \) and solve for t.
Just some trivia, the person who first published this and the person who wrote The Art of War share the same name. It would be cool if they had been the same person, we could learn about applying mathematical analysis to battlefield strategy. Please Register or Log in to view the hidden image!
