Question

Найти наименьшее натуральное число, дающее при деление на 5,7,11,13 остаток 4.

Answer 1

Чтобы найти наименьшее натуральное число, дающее при делении на 5, 7, 11 и 13 остаток 4, мы можем использовать метод китайской теоремы об остатках.

Предположим, что искомое число - х. Тогда мы можем записать следующую систему уравнений:

х ≡ 4 (mod 5) х ≡ 4 (mod 7) х ≡ 4 (mod 11) х ≡ 4 (mod 13)

Для начала, найдем частное решение этой системы уравнений сразу для всех модулей. Для этого мы можем воспользоваться обратной теоремой Ферма:

- для модуля 5: 4^-1 ≡ 4 (mod 5) - для модуля 7: 4^-1 ≡ 2 (mod 7) - для модуля 11: 4^-1 ≡ 3 (mod 11) - для модуля 13: 4^-1 ≡ 10 (mod 13)

Теперь, умножим все остатки на соответствующие частные решения и сложим:

х = (4 * 5 * 4) + (4 * 7 * 2) + (4 * 11 * 3) + (4 * 13 * 10) = 80 + 56 + 132 + 520 = 788

Таким образом, наименьшее натуральное число, дающее при делении на 5, 7, 11, и 13 остаток 4, равно 788.