Mathematical Puzzle: Applying the Chinese Remainder Theorem to a Book Grouping Problem

Question

There are some books on the table. If you group them by 3, you get some number of full groups and 2 books remain; if you group them by 4, you get some number of full groups and 3 books remain; if you group them by 5, you get some number of full groups and 4 books remain. What is the number of books on the table, if it is less than 100?

---

Solution

Using the Chinese Remainder Theorem:

1. N (Product of moduli): 60 (= 3*4*5)
2. Ni values (N divided by each modulus):
   • N1 = 20 (for modulus 3)
   • N2 = 15 (for modulus 4)
   • N3 = 12 (for modulus 5)
3. Multiplicative Inverses:
   • Inverse of N1​ modulo 3 is 2
   • Inverse of N2​ modulo 4 is 3
   • Inverse of N3​ modulo 5 is 3
4. Remainders: [2, 3, 4]
5. Individual Terms (Remainder ×× Ni ×× Inverse):
   • 2×20×2 = 80
   • 3×15×3 = 135
   • 4×12×3 = 144
6. Sum of Terms: 359
7. Final Solution (Sum of Terms mod N): 59

The final solution is the sum of the individual terms, 359, taken modulo N, which is 60, resulting in 59.

---

Inverse of N3=12 modulo 5 is 3

What It Means: Here, we are looking for a number that, when multiplied with 12, yields a result that is equivalent to 1 when divided by 5. We need an integer x such that:

12×x ≡ 1 mod  5

Finding the Inverse:

• Again, we check integers starting from 1.
• We find that 12×3=36.
• When you divide 36 by 5, the remainder is 1 (since 36=5×7+1).
• Thus, 3 is the multiplicative inverse of 12 modulo 5.