Доказательство. Рассмотрим остатки по модулю $6$: они равны $0,1,2,3,4,5$. Если целое число $n>3$ простое, то оно не делится на $2$ и не делится на $3$. Значит его остаток при делении на $6$ не может быть $0,2,3,4$ (эти остатки соответствуют делимости на $2$ или $3$). Остаются только остатки $1$ и $5$. Следовательно любое простое число $p>3$ представимо как
$$p=6k\pm 1.$$
Почему обратное неверно. Число вида $6k\pm 1$ не обязано быть простым: например
$$25=6\cdot 4+1,35=6\cdot 6-1,49=6\cdot 8+1$$ — все они имеют вид $6k\pm 1$, но составные. То есть условие «быть вида $6k\pm 1$» необходимо для простоты при $p>3$, но не достаточно.
Обобщения для других модулей. Общая заметка: если $m$ — фиксированный целый модуль, то любое простое $p$, не делящееся на $m$, имеет остаток, взаимно простой с $m$; иначе $p$ делило бы некоторый простой делитель $q$ модуля $m$. Формально,
$$p\mathrm{mod}m\in (\mathbb{Z}/m\mathbb{Z}{)}^{\times },$$ то есть среди $\phi (m)$ классов, взаимно простых с $m$.
Конкретные примеры:
- Модуль $3$: для простых $p>3$ имеем $p\equiv \pm 1(\mathrm{mod}3)$.
- Модуль $4$: для простых $p>2$ имеем $p\equiv 1$ или $3(\mathrm{mod}4)$ (то есть просто нечётность).
- Модуль $30=2\cdot 3\cdot 5$: для простых $p>5$ возможны только остатки, взаимно простые с $30$, а именно
$$p\equiv 1,7,11,13,17,19,23,29(\mathrm{mod}30).$$ (Это даёт более жёсткую «сетку» кандидатов на простоту, но опять же не гарантирует простоту.)
Замечание о плотности: для модуля $m$ доля возможных остаточных классов равна $\phi (m)/m$; теорема Дирихле утверждает, что в каждом таком классе, взаимно простом с $m$, содержится бесконечно много простых (на уровне утверждения — дополнительный факт, не требующий здесь доказательства).