Canteen Snack Count: Remainders, Pack Sizes and a Check-Digit Condition
The school canteen receives a delivery of wrapped snack bars. When the staff count them into bags of 5, 3 bars are left over; into boxes of 7, 4 are left over; into trays of 9, 6 are left over. The invoice states the delivery is between 100 and 200 bars, and the supplier will only accept a claim if the staff can name the exact number and show the method. A second supplier delivers the same total in packs of 8 and 13 only, and the canteen wants to know whether the total can be split exactly into those pack sizes without opening any pack. Finally, the school's stock system uses a check condition: the total must leave remainder 1 when divided by 4. The canteen manager suspects that no number between 100 and 200 satisfies all four conditions and wants the smallest total that would satisfy them all.
1. Find the exact number of bars in the delivery using the first three remainder conditions and the stated range.
Read the worked answer
We need N ≡ 3 (mod 5), N ≡ 4 (mod 7), N ≡ 6 (mod 9). Write N = 5a + 3. Modulo 7: 5a + 3 ≡ 4, so 5a ≡ 1 (mod 7). Since 5 × 3 = 15 ≡ 1 (mod 7), a ≡ 3 (mod 7), so a = 3 + 7b and N = 5(3 + 7b) + 3 = 18 + 35b. Modulo 9: 18 + 35b ≡ 6, so 35b ≡ −12 ≡ 6 (mod 9). As 35 ≡ 8 (mod 9) and 8 × 8 = 64 ≡ 1, b ≡ 8 × 6 = 48 ≡ 3 (mod 9). Thus b = 3 + 9c and N = 18 + 105 + 315c = 123 + 315c. The solutions repeat with period lcm(5, 7, 9) = 315. The only value in the invoice range 100 to 200 is c = 0, giving N = 123. Check: 123 = 5(24) + 3, 123 = 7(17) + 4, 123 = 9(13) + 6.
2. Decide whether 123 bars can be packed exactly in packs of 8 and 13, and give the packing.
Read the worked answer
We need non-negative integers x, y with 8x + 13y = 123. Reduce modulo 8: 13y ≡ 123 (mod 8). Since 13 ≡ 5 and 123 ≡ 3, we get 5y ≡ 3 (mod 8). The inverse of 5 modulo 8 is 5 because 5 × 5 = 25 ≡ 1, so y ≡ 5 × 3 = 15 ≡ 7 (mod 8). The only non-negative possibility is y = 7, since y = 15 would already give 13 × 15 = 195 > 123. Then 8x = 123 − 91 = 32, so x = 4. Check: 8(4) + 13(7) = 32 + 91 = 123. So the total splits exactly into 4 packs of 8 and 7 packs of 13, with no pack opened. Because the congruence fixes y modulo 8 and the size bound limits y to a single value, the solution is unique.
3. Add the condition N ≡ 1 (mod 4) and find the smallest total satisfying all four conditions; explain the period.
Read the worked answer
From the first three conditions, N = 123 + 315c, where 315 = lcm(5, 7, 9). Reduce modulo 4: 123 = 4(30) + 3, so 123 ≡ 3; and 315 = 4(78) + 3, so 315 ≡ 3. The new condition is 3 + 3c ≡ 1 (mod 4), i.e. 3c ≡ −2 ≡ 2 (mod 4). Since 3 × 3 = 9 ≡ 1, the inverse of 3 modulo 4 is 3, so c ≡ 3 × 2 = 6 ≡ 2 (mod 4). The smallest non-negative choice is c = 2, giving N = 123 + 630 = 753. Check: 753 = 5(150) + 3, 753 = 7(107) + 4, 753 = 9(83) + 6, and 753 = 4(188) + 1. So the manager is right that no number from 100 to 200 works; the smallest solution is 753. The solutions recur with period lcm(5, 7, 9, 4) = 1260, because each added coprime modulus multiplies the period by that modulus.