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

Решение 1 (ручками)

Рассмотрим формулу:

Нам нужно найти наибольшее , при котором формула всегда истинна для любого .

Формула утверждает, что если не делится на , то если делится на 6, то не должно делиться на 9. Чтобы формула была истинной, необходимо, чтобы было таким, что при делении на 6 не делится на 9. Это возможно, если — наименьшее общее кратное чисел 6 и 9:

Таким образом, наибольшее .

Ответ: .

Решение 2 (прогой)

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

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

# функция проверяет выполнение выражения для конкретного x и A
def f(x, A):
    return (x % A != 0) <= ((x % 6 == 0) <= (x % 9 != 0))

# перебор возможных значений A от 10000 до 1
for A in range(10000, 0, -1):
    flag = True  # флаг: True - формула выполняется для всех x, False - хотя бы один x нарушает
    for x in range(1000):  # перебор натуральных x
        # если формула ложна для текущего x, отмечаем нарушение
        if not f(x, A):
            flag = False
    # если формула выполняется для всех x, выводим A и завершаем поиск
    if flag:
        print(A)
        break