Вопрос школьника
Старинная китайская задача. Имеются вещи. Если считать их тройками, то останется 2; если считать пятерками, то останется 3; если считать семерками, то останется 2. Сколько вещей?
Ответ от учителя
Для решения этой задачи необходимо использовать китайскую теорему об остатках.
Пусть x — искомое количество вещей. Тогда по условию задачи:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
Решим систему уравнений методом китайской теоремы об остатках.
1. Найдем N — произведение модулей:
N = 3 * 5 * 7 = 105
2. Найдем N1, N2, N3 — модули, соответствующие каждому уравнению:
N1 = 5 * 7 = 35
N2 = 3 * 7 = 21
N3 = 3 * 5 = 15
3. Найдем обратные элементы по модулям N1, N2, N3:
35 ≡ 2 (mod 3), поэтому 2 * 35 ≡ 1 (mod 3), т.е. обратный элемент по модулю 3 равен 23.
21 ≡ 1 (mod 5), поэтому обратный элемент по модулю 5 равен 1.
15 ≡ 1 (mod 7), поэтому обратный элемент по модулю 7 равен 1.
4. Найдем сумму произведений остатков и обратных элементов:
x = (2 * 35 * 2) + (3 * 21 * 1) + (2 * 15 * 1) ≡ 233 (mod 105)
Ответ: искомое количество вещей равно 233.
