Среди чисел вида 7m + 3 найти наименьшее положительное число, кратное 23

Предмет: Математика
Раздел: Теория чисел, арифметика (делимость, сравнения по модулю)

Задание:
Среди чисел вида 7m + 3 найти наименьшее положительное число, кратное 23.

Решение:

Нам нужно найти такое наименьшее положительное число вида 7m + 3, которое делится на 23, то есть:

7m + 3 \equiv 0 \pmod{23}

Перенесем 3 направо:

7m \equiv -3 \pmod{23}

Так как -3 \equiv 20 \pmod{23}, получаем:

7m \equiv 20 \pmod{23}

Теперь найдём такое число m, при котором это сравнение выполняется. Для этого найдём обратный элемент к 7 по модулю 23.

Найдем такое число x, что:

7x \equiv 1 \pmod{23}

Подбором:

• 7 \cdot 10 = 70 \Rightarrow 70 \mod 23 = 1

Значит, обратный элемент к 7 по модулю 23 — это 10.

Умножим обе части сравнения 7m \equiv 20 \pmod{23} на 10:

m \equiv 10 \cdot 20 = 200 \equiv 16 \pmod{23}

Значит, наименьшее значение m = 16.

Теперь подставим в выражение:

7m + 3 = 7 \cdot 16 + 3 = 112 + 3 = 115

Проверим:
115 \div 23 = 5 — делится нацело.

Ответ:
Наименьшее положительное число вида 7m + 3, кратное 23 — это
115. ✅