Сравнения по модулю

• Два числа, а и b сравнимы по модулю t, и пишут: $𝑎\equiv 𝑏\left(\mathrm{m}\mathrm{o}\mathrm{d} 𝑡\right)$, если разность $(𝑎-𝑏)$ делится на t.

• Малая теорема Ферма. Если p – это простое число, a – целое число, не делящееся на p, то ${𝑎}^{𝑝-1}-1$ делится на p:

${𝑎}^{𝑝-1}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d} 𝑝\right)$.

• Пример: $𝑎=2$, $𝑝=5$.

${𝑎}^{𝑝-1}-1=2^{5-1}-1=$ $2^4-1=16-1=15$.

$16\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d} 5\right)$.

Число 15 делится на 5 без остатка.

• Следствие. Если натуральное число а не делится на простое число p, то

${𝑎}^{𝑝}\equiv 𝑎\left(\mathrm{m}\mathrm{o}\mathrm{d} 𝑝\right)$.