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

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

$a^{p-1}\equiv 1\left(\text{mod} p\right).$

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

  $a^p\equiv a\left(\text{mod} p\right).$

  Пример. $a=2$, $p=5.$

  $a^{p-1}-1=2^{5-1}-1=2^4-1=16-1=15,$

  $16\equiv 1\left(\text{mod} 5\right).$

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