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

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

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

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

  ${𝑎}^{𝑝}\equiv 𝑎\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 без остатка.