15.01 Деление без остатка

Решение руками

Введем обозначения:

Таким образом истиным для всех должно быть выражение .Упростим это выражение, раскрыв импликацию: .

Из этой формулы видно, что множество должно перекрыть множество, которое не перекрыто множеством . Множество – это множество всех чисел, которые не делятся либо на 15 либо на 18. Поэтому чтобы найти наименьшее достаточно выбрать наименьшее из чисел 15 и 18 – это 15.

Решение программой

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до . Для каждого перебираем от до и проверяем истинность формулы. Если хотя бы для одного выражение оказывается ложным, текущее отбрасываем. В конце выводим наименьшее , для которого формула истинна для всех .

for a in range(1, 1500):
    # Переменная-флаг,
    # которой присваивается 1, если хотя бы одно выражение выдаёт ложь
    f = 0
    for x in range(1, 5000):
        # Если выражение ложно(нам нужны только истинные),
        # то приостанавливаем цикл
        if (((x % a == 0) and (x % 15 != 0)) <= ((x % 18 == 0) or (x % 15 == 0))) == False:
        #if (((x % a != 0) or (x % 15 == 0) or (x % 18 == 0))) == False:
            f = 1
            break
    if f == 0:
        print(a)
        break

Получаем ответ: