Найдите наименьшее натуральное число, которое при делении на 7 даёт остаток 1, а при делении на 8 - остаток 2.

Предыдущий
вопрос Следующий
вопрос

Для этого нужно найти число, которое удовлетворяет условиям:

x ≡ 1 (mod 7)
x ≡ 2 (mod 8)

Подсказка: можно использовать китайскую теорему об остатках (КТО).

Решение:

По КТО:

x ≡ a1 (mod n1)
x ≡ a2 (mod n2)

x = a1 + n1 m1
x = a2 + n2 m2

a1 + n1 m1 ≡ a2 (mod n2)
n1 m1 ≡ a2 - a1 (mod n2)

Таким образом, для нашей задачи:

x ≡ 1 (mod 7)
x ≡ 2 (mod 8)

1 + 7m ≡ 2 (mod 8)
7m ≡ 1 (mod 8)

Тогда m = 7^(-1) mod 8 = 7.

Подставляем найденное значение m обратно:

x = 1 + 7 * 7 = 50.

Ответ: наименьшее натуральное число, которое при делении на 7 даёт остаток 1, а при делении на 8 - остаток 2, равно 50.