Ответ:

Чтобы число солдат делилось и на 72, и на 126, найдём их наименьшее общее кратное.

Разложим числа на простые множители: \(72=2^3\cdot3^2\), \(126=2\cdot3^2\cdot7\).

Берём максимальную степень каждого простого множителя: \(\text{НОК}(72,126)=2^3\cdot3^2\cdot7=504\).

Ответ: 504 солдата.