Цитата:
|
Сообщение от Одиссей
Я тоже пытался через МТФ выдумать решение. Если бы получилось - наверняка получилось бы красиво: доказали бы что число составное без предъявления делителей. Но выдумать такое доказательство не смог.
|
Вот вам доказательство через малую теорему Ферма. Проверяйте.
Рассомтрим число (5^125 - 1) / (5^25 - 1). Это число можно выразить как 5^100+5^75+5^50+5^25+1.
Допустим, что это число простое и обозначим его через p.
Заметим, что 5^125 сравнимо с единицей по модулю p. Действительно, (5^125-1)/(5^25-1)=p -> 5^125-1 = (5^25-1)*p -> 5^125=(5^25-1)*p + 1.
Далее, если k — наименьшее число, такое что 5^k сравнимо с единицей по модулю p, то k делит 125. В самом деле, 125=km + r, где 0 <= r < k. Тогда, т.к. 5^125 сравнимо с 1 и 5^k сравнимо с 1, то необходимо 5^r сравнимо с 1. Но r<k, что противоречит предположению о том, что k — это наименьшее такое число, для которого 5^k сравнимо с 1. Значит r = 0 и k делит 125.
Таким образом, k может равняться лишь 1, 5, 25 или 125. Далее вспоминаем, что p = 5^100+5^75+5^50+5^25+1. Если k=1, получаем что p сравнимо с 1. И если k = 5 или 25, то p сравнимо с 5. Но c другой стороны в рассматриваемом поле классов вычетов p должно быть сравнимо с нулем, т.е. p должно делить 1, если k = 1 и p должно делить 5, если k = 5 или 25. Т.е. p должно равняться 1 или 5, что, очевидно, не так. Тогда необходимо k=125.
Мы получили, что в рассматриваемом поле классов вычетов наименьшее число k, для которого 5^k сравнимо с 1, должно равняться 125. С другой стороны, из малой теоремы Ферма 5^(p-1) сравнимо с 1. А значит, p-1 кратно 125. С другой стороны p-1=5^100+5^75+5^50+5^25 и указанное условие кратности, очевидно, не выполнено. Полученное противоречие доказывает, что наше исходное предположение неверно и p не может быть простым числом.
