Pequeño teorema de Fermat

Si \(p\) es primo y \(p\nmid a\), el conjunto \(\{a, 2a, \dots, (p-1)a\}\) es un sistema de residuos no nulos módulo \(p\), por lo que su producto es congruente con \((p-1)!\). De ahí se deduce \(a^{p-1}\equiv 1 \pmod{p}\), y como \((p-1)!\equiv -1\) por el teorema de Wilson, se obtiene también la forma \(a^p\equiv a \pmod{p}\) válida para todo entero \(a\).

Por ejemplo, para calcular \(7^{222}\bmod 11\), como \(11\) es primo y \(11\nmid 7\), se tiene \(7^{10}\equiv 1 \pmod{11}\). Como \(222=10\cdot 22+2\), resulta \(7^{222}\equiv 7^2=49\equiv 5 \pmod{11}\).

Un error típico es aplicar el teorema sin comprobar que \(p\) sea primo, o usarlo con \(a\) divisible por \(p\). Por ejemplo, con \(p=9\) no primo, \(2^{8}=256\equiv 4 \pmod{9}\), no \(1\), así que la conclusión no vale.