Chinese remainder theorem
General · Mathematics
Study notes
Q: Find x with x ≡ 2 (mod 3) and x ≡ 3 (mod 5). M = 15. For mod 3: M₁ = 5, inverse of 5 mod 3 is 2 (5≡2, 2×2=4≡1). Term: 2×5×2 = 20. For mod 5: M₂ = 3, inverse of 3 mod 5 is 2. Term: 3×3×2 = 18. x = 20+18 = 38 ≡ 8 (mod 15). Check: 8 mod 3 = 2 ✓, 8 mod 5 = 3 ✓!