Делимость

Чем ДЕЛ(x, 15) отличается от ДЕЛ(15, x)?

В ДЕЛ(n, m) первое число делится на второе. ДЕЛ(x, 15) — x кратно 15: 15, 30, 45, … ДЕЛ(15, x) — x делитель 15: 1, 3, 5, 15. Кратных бесконечно много, а делителей — всегда несколько.

Пример: при каком наименьшем x > 1 истинно ДЕЛ(x, 30) ∨ ДЕЛ(15, x)? Первая часть требует кратного 30 — это 30, 60, … Вторая — делителя 15 — это 1, 3, 5, 15. Хватит одной истинной части, поэтому ответ — 3.

На Python ДЕЛ(n, m) записывают остатком: n % m == 0. Порядок тот же: ДЕЛ(15, x) — это 15 % x == 0.

Когда x делится и на 21, и на 35?

Если число делится на два числа, оно делится и на их наименьшее общее кратное — НОК. И наоборот. НОК находят по разложению на простые множители: каждый множитель берут столько раз, сколько он встречается в том числе, где его больше.

21 = 3 · 7, 35 = 5 · 7. В НОК нужны 3, 5 и одна 7: НОК(21, 35) = 3 · 5 · 7 = 105. Значит, ДЕЛ(x, 21) ∧ ДЕЛ(x, 35) — то же, что ДЕЛ(x, 105).

Теперь задача: наибольшее натуральное A, при котором ДЕЛ(x, A) ∨ ¬ДЕЛ(x, 21) ∨ ¬ДЕЛ(x, 35) тождественно истинна. Части без A ложны, когда x делится и на 21, и на 35, — это x = 105, 210, 315, … Каждое из этих чисел должно делиться на A.

Если A делит 105, оно делит и все кратные 105. А A больше 105 не делит само 105. Наибольшее A = 105.

В задаче темы на отрезке было одно кратное 15. А если их несколько? Возьмём ту же формулу с отрезком [50; 100]: ДЕЛ(x, A) ∨ ((x ∈ [50; 100]) → ¬ДЕЛ(x, 15)).

Если A должно делить несколько чисел, наибольшее такое A — их наибольший общий делитель, НОД.

Всё решает A при кратных 15 на отрезке: 60, 75 и 90. A должно делить каждое из них.

НОД тоже находят по разложению — теперь берут только общие множители: 60 = 2² · 3 · 5, 75 = 3 · 5², 90 = 2 · 3² · 5. Общие — одна 3 и одна 5: НОД = 15. Ответ — 15.

Как быть, если A с x сравнивают, а не делят? Пример: наименьшее натуральное A, при котором (x ∈ [10; 40]) → (ДЕЛ(x, 3) ∨ (x < A)) тождественно истинна.

Всё решает A при числах отрезка, которые не делятся на 3. Каждое из них должно быть меньше A — значит, A больше самого большого из них.

Стрелка: ¬(x ∈ [10; 40]) ∨ ДЕЛ(x, 3) ∨ (x < A). Части без A ложны, когда x на отрезке и не кратно 3: 10, 11, 13, 14, …, 40.

40 = 3 · 13 + 1 на 3 не делится. Нужно 40 < A — наименьшее A = 41. Проверяй конец отрезка: если бы он делился на 3, граница была бы на число раньше.

Бывает, что A — набор чисел, как в подтеме об отрезках и множествах. Пример: A — конечное множество натуральных чисел, и формула (x ∈ [10; 40]) → (ДЕЛ(x, 5) ∨ (x ∈ A)) тождественно истинна. Какое наименьшее количество чисел в A?

Всё решает A при числах отрезка, не кратных 5: каждое из них обязано лежать в A. Наименьшее A — ровно эти числа.

Всего на отрезке [10; 40] 40 − 10 + 1 = 31 число. Кратных 5 среди них 7: 10, 15, 20, 25, 30, 35, 40. Остальные 31 − 7 = 24 числа и есть наименьшее A. Ответ — 24.

Как проверить ответ 105 программой?

Шаблон тот же, что для задачи темы: ДЕЛ записывают через %, а диапазон x берут таким, чтобы в него попало несколько чисел, где всё решает A.

def f(x, A):    return x % A == 0 or x % 21 != 0 or x % 35 != 0

answer = 0for A in range(1, 1000):    if all(f(x, A) for x in range(1, 10000)):        answer = Aprint(answer)

Всё решает A при x = 105, 210, …, поэтому x до 9999 — с большим запасом: в диапазоне 95 таких чисел. A до 999 хватает: A больше 105 не делит 105.

• ДЕЛ(x, m)x кратно m
• ДЕЛ(m, x)x — делитель m
• Делится на обаделится на их НОК
• A делит несколько чиселнаибольшее A — их НОД
• A — границабольше самого большого числа
• A — наборвсе числа, где решает A
• Pythonn % m == 0, x — с запасом