Правило, дошедшее вместе с задачей, — рецепт, а не перебор. Возьмите три остатка 2, 3, 2 и умножьте их на 70, 21 и 15 — числа, выбранные так, что 70 ≡ 1 (mod 3) и 0 для остальных, 21 ≡ 1 (mod 5), 15 ≡ 1 (mod 7). Калькулятор складывает 70·2 + 21·3 + 15·2 в 233; вычтите дважды 3·5·7 = 105, и останется 23, наименьший ответ. Проверьте наоборот: 23 mod 3 равно 2, 23 mod 5 равно 3, 23 mod 7 равно 2.
Теорема говорит, что у системы ровно одно решение по модулю произведения попарно взаимно простых модулей, так что 23 — единственный ответ между 0 и 104, а любое другое решение имеет вид 23 + 105k. Построение обобщается на любое число сравнений, и та же алгебра возникает далеко от арифметики: это изоморфизм китайской теоремы об остатках Z/105 → Z/3 × Z/5 × Z/7, причина, по которой число можно хешировать сразу по нескольким малым модулям, и основа явного шага восстановления в арифметике систем остаточных классов, которую используют для точного суммирования.
Ответ
23
Как его читать
233 mod 105 на калькуляторе. Первая ссылка строит 233 из коэффициентов 70, 21 и 15 стихотворного правила; третья показывает первый из трёх остатков, 2.
Источник
Sunzi suanjing (Master Sun's Mathematical Manual, c. 400 CE) poses the problem 'there is an unknown number, divided by 3 it leaves 2, divided by 5 it leaves 3, divided by 7 it leaves 2'; the general constructive rule appears in Qin Jiushao's Shushu Jiuzhang of 1247, and the theorem in its modern form belongs to Euler's work on congruences before Gauss put it in the Disquisitiones Arithmeticae of 1801 — which is why the theorem is called Chinese in the West
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.