Find the sum of the digits of the smallest number which, when divided by 15,…

We need the smallest number N that leaves remainder 4 when divided by 15, 54, 16, and 12, and is divisible by 19.

Key idea: If N leaves remainder 4 on each division, then N − 4 is divisible by all these moduli, so

N = LCM(15, 54, 16, 12) · k + 4

Compute the LCM: 15 = 3·5, 54 = 2·3^3, 16 = 2^4, 12 = 2^2·3, so take the highest powers: 2^4 · 3^3 · 5 = 16·27·5 = 2160.

Thus N = 2160k + 4. We need the smallest positive integer k such that N is divisible by 19.

Reduce modulo 19: 2160 ≡ 13 (mod 19) because 2160 − 19·113 = 13. So we require

13k + 4 ≡ 0 (mod 19) ⇒ 13k ≡ 15 (mod 19).

The modular inverse of 13 modulo 19 is 3 (since 13·3 = 39 ≡ 1 (mod 19)). Multiply both sides by 3:

k ≡ 3·15 ≡ 45 ≡ 7 (mod 19).

The smallest positive k is 7. Therefore N = 2160·7 + 4 = 15124.

Sum of digits = 1 + 5 + 1 + 2 + 4 = 13.

Answer: 13