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

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

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

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

Из этой формулы видно, что множество должно перекрыть множество, которое не перекрыто множеством . Предположим, что , отсюда , значит, множество ложно, когда число делится и на 45, и на 70. Найдем НОК чисел 45 и 70, оно равно 630. Значит 630 должно делиться на А без остатка, тогда наибольшее возможное А это 630.

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

Для нахождения наибольшего целого , при котором выражение

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

# перебор возможных значений A от 1 до 999
for a in range(1, 1000):
    # флаг: 0 - формула выполняется для всех x, 1 - найдено нарушение
    f = 0
    # перебор всех x от 1 до 1499
    for x in range(1, 1500):
        # проверяем выполнение логического выражения при данных x и A
        if (((x % 45 == 0) and (x % 70 == 0)) <= (x % a == 0)) == False:
            # если формула оказалась ложной, фиксируем нарушение и прекращаем проверку
            f = 1
            break
    # если формула выполняется для всех x, выводим найденное A
    if f == 0:
        print(a)

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