Пример 2. Доказать, что среди трёхзначных чисел нет числа, делящегося одновременно на 7, 11 и 13.

Школьник младших классов, знакомый лишь с делением, может справиться с этой задачей, перебрав и испробовав все 900 трёхзначных чисел. Школьник старших классов знает (точнее, должен знать), что среди натуральных чисел выделяются простые числа и что простым называется всякое натуральное число, которое, во-первых, больше единицы и, во-вторых, делится только на 1 и на само себя. Так что числа 7, 11 и 13 – простые. А ежели школьник ещё более образован, то он знает, что число, делящееся на каждое из нескольких простых чисел, обязано делиться и на их произведение. Произведение 7 × 11 × 13 равно 1001. Но никакое трёхзначное число не может делиться на 1001.

Пример 3. Представим себе, что мы выдвинули такую гипотезу: уравнение x⁴ + y⁴ = z² не имеет решения в области целых положительных чисел, не превосходящих числа 100.

В действительности указанное уравнение не имеет решения ни в каких целых положительных числах, так что наша гипотеза верна. Доказательство теоремы о неразрешимости нашего уравнения в целых положительных числах вполне элементарно (это не значит, что до него легко додуматься). Так что в принципе читатель может доказывать гипотезу одним из двух способов.

Первый способ. Перебрать все десять тысяч пар 〈x, y〉, таких что 1 ≤ x ≤ 100, 1 ≤ y ≤ 100; возвести для каждой такой пары её члены в четвёртую степень, сложить и убедиться, что сумма не является полным квадратом.

Второй способ. Попытаться самостоятельно получить доказательство теоремы о неразрешимости уравнения.

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

Сейчас мы приведём реальный пример перебора, с которым не в состоянии справиться современные компьютеры.