Малая теорема Ферма

Ясно, что остатки степеней пятерки по модулю зацикливаются (потому что количество остатков при делении на конечно), притом в цикле точно встретится остаток так как по МТФ (очевидно, что не походит к условию). Значит, существует наименьшее натуральное такое, что (нетрудно понять, что является последней степенью пятёрки в самом первом цикле остатков по модулю ). Значит, если то делит

Следовательно, делит Если то кратно то есть Если или то но очевидно, что в силу МТФ.