Вопрос школьника
Приведите пример трёхзначного натурального числа, которое при делении на 3, на 5 и на 7 даёт в остатке 2 и в записи которого есть только две различные цифры. В ответе укажите ровно одно такое число.
Ответ от учителя
Для решения этой задачи можно воспользоваться китайской теоремой об остатках.
Пусть искомое число равно $N$. Тогда по условию задачи:
$$N equiv 2 pmod{3}$$
$$N equiv 2 pmod{5}$$
$$N equiv 2 pmod{7}$$
Обозначим через $a_1, a_2, a_3$ соответствующие модули, а через $m_1, m_2, m_3$ — их произведение, то есть $m_1 = 3 cdot 5 cdot 7 = 105$, $m_2 = 5 cdot 7 cdot 3 = 105$, $m_3 = 7 cdot 3 cdot 5 = 105$. Тогда система уравнений примет вид:
$$N equiv 2 pmod{3} Rightarrow N_1 = 2 + 3k_1$$
$$N equiv 2 pmod{5} Rightarrow N_2 = 2 + 5k_2$$
$$N equiv 2 pmod{7} Rightarrow N_3 = 2 + 7k_3$$
где $k_1, k_2, k_3$ — целые числа.
Так как $105$ — общее произведение модулей, то по китайской теореме об остатках существует единственное решение системы уравнений вида $N equiv N_i pmod{m_i}$, которое можно найти следующим образом:
$$N = sum_{i=1}^{3} N_i cdot M_i cdot y_i,$$
где $M_i = frac{m}{m_i}$, а $y_i$ — обратный элемент $M_i$ по модулю $m_i$.
Вычислим $M_i$ и $y_i$ для каждого $i$:
$$M_1 = frac{105}{3} = 35, quad y_1 = 2^{-1} pmod{3} = 2$$
$$M_2 = frac{105}{5} = 21, quad y_2 = 1^{-1} pmod{5} = 1$$
$$M_3 = frac{105}{7} = 15, quad y_3 = 4^{-1} pmod{7} = 2$$
Тогда:
$$N = 2 cdot 35 cdot 2 + 2 cdot 21 cdot 1 + 2 cdot 15 cdot 2 = 210 + 42 + 60 = 312$$
Таким образом, искомое число равно 312. Проверим, что оно удовлетворяет всем условиям задачи:
$$312 equiv 2 pmod{3}$$
$$312 equiv 2 pmod{5}$$
$$312 equiv 2 pmod{7}$$
Также заметим, что в записи числа 312 есть только две различные цифры — 1 и 2.
Ответ: 312.
