Какие целые числа дают остаток r1 при делении на m и остаток r2 при делении на n, если m=15, n=24, r1=8, r2=9?

Добрый_Убийца

70

Чтобы найти целые числа, которые дают остаток \(r_1\) при делении на \(m\) и остаток \(r_2\) при делении на \(n\) для заданных значений \(m=15\), \(n=24\), \(r_1=8\) и \(r_2=9\), мы можем воспользоваться китайской теоремой об остатках.

Китайская теорема об остатках гласит, что если \(x\) — искомое целое число и \(x\) удовлетворяет следующей системе конгруэнтностей:

\[x \equiv r_1 \pmod m \\
x \equiv r_2 \pmod n\]

где символ \(\equiv\) означает "конгруэнтно по модулю", то мы можем найти \(x\) с помощью следующего алгоритма:

1. Рассчитываем взаимно простые целые числа \(a\) и \(b\) такие, что \(am + bn = 1\). Это можно сделать с помощью расширенного алгоритма Евклида.
2. Умножаем \(r_1\) на \(bn\) и \(r_2\) на \(am\).
3. Складываем полученные произведения: \(x = r_1 \cdot bn + r_2 \cdot am\).
4. Находим минимальное положительное целое число \(x\), удовлетворяющее первому условию конгруэнтности.

Давайте выполним эти шаги для наших заданных значений \(m=15\), \(n=24\), \(r_1=8\) и \(r_2=9\).

1. Найдем взаимно простые числа \(a\) и \(b\) с помощью расширенного алгоритма Евклида. Получаем \(a = -11\) и \(b = 7\), так как \(7 \cdot 15 + (-11) \cdot 24 = 1\).
2. Умножим \(r_1\) на \(bn\) и \(r_2\) на \(am\). Получаем \(8 \cdot 7 \cdot 15 = 840\) и \(9 \cdot (-11) \cdot 24 = -2376\).
3. Сложим произведения: \(x = 840 + (-2376) = -1536\).
4. Найдем минимальное положительное целое число \(x\), удовлетворяющее первому условию конгруэнтности. Для этого прибавим \(mn = 15 \cdot 24 = 360\) к \(x\) до тех пор, пока \(x\) не станет положительным. Получаем \(x = 360 - 1536 = -1176\).

Таким образом, целые числа, которые дают остаток 8 при делении на 15 и остаток 9 при делении на 24, это числа из класса эквивалентности \([-1176]_{360}\), где \(360\) — наименьшее общее кратное чисел \(m\) и \(n\).