CAT 2022 Slot 3 · Quant · Question 19

Leaving exactly 4 over in each case means the student count is 4 more than a common multiple of 9, 10, 12 and 25.

Find that common multiple: 9={3}^{2}, 10=2\times 5, 12={2}^{2}\times 3 and 25={5}^{2}.

Taking the highest power of each prime, the LCM is {2}^{2}\times{3}^{2}\times{5}^{2}=4\times 9\times 25=900.

So the number of students is 900k+4 for some whole number k.

It must also be divisible by 11, so 900k+4 is a multiple of 11.

Now 900=81\times 11+9, so 900 leaves remainder 9 on division by 11.

The condition becomes 9k+4\equiv 0, that is 9k\equiv -4\equiv 7 modulo 11.

Multiplying both sides by 5, since 9\times 5=45 leaves remainder 1, gives k\equiv 35\equiv 2 modulo 11.

The smallest such k is 2, giving 900\times 2+4=1804 students.

The next would be k=13, giving 11704 — far beyond the 5000 limit.

So the school has 1804 students, and 1804=12\times 150+4.

The maximum number of teams of 12 is therefore 150.

Shortcut. The four divisors share enough factors that the LCM is a round 900, so the candidates are just 904, 1804, 2704, 3604 and 4504. Testing those five against divisibility by 11 finds 1804 quickly, with no modular arithmetic needed.