Пусть — простое число, , где .
Если , то , и сам остаток является простым числом — утверждение верно.
Пусть , тогда . Так как простое и , число не делится ни на , ни на , ни на . Если бы делилось на , то и делилось бы на (ведь делится на ) — противоречие; аналогично не может делиться на или на . Значит, не делится ни на , ни на , ни на , то есть взаимно просто с .
Среди чисел от до взаимно просты с (не делятся на , и ) только числа
(остальные делятся на , или ). Каждое из них, кроме , — простое число.
Значит, остаток равен либо , либо одному из простых чисел , , , , , , — то есть остаток от деления простого числа на всегда есть простое число или единица.
