El pequeño teorema de Fermat, también conocido como teorema de Fermat, es un teorema básico en la teoría de números. Significa que si se toma un número entero a que no es múltiplo del número primo módulo de un número primo, su potencia. es p- Cuando 1, el resultado del módulo número primo es siempre 1, es decir: a^(p-1)
≡ 1 (mod p)
Donde, p es un número primo y a es cualquier número entero que satisfaga 1lt = alt;p.
El pequeño teorema de Fermat fue propuesto por primera vez por el matemático francés Fermat en el siglo XVII. Es la base del teorema de Euler y del teorema de Euler-Fermat, y se utiliza ampliamente en criptografía, codificación, informática, etc. campo.
El pequeño teorema de Fermat se puede demostrar mediante inducción matemática. Supongamos que k es un número entero positivo, entonces:
Cuando k=1, a ^0 ≡ 1. (mod p), se establece la conclusión.
Cuando kgt; 1, suponiendo que se cumpla a^(p-1) ≡ 1 (mod p), entonces existe:
a^(kp-k) ≡ (a^ (p-1))^k * a^(-k) ≡ 1^k * a^(-k) ≡ a^(p-1)
* a^(-k) ≡ a ^(p-1-k) (mod p)
Por lo tanto, cuando kgt; 1, a^(kp-k) ≡ a^(p-1-k)
(mod p) se mantiene.
Debido a que p es un número primo y a es un número entero que no es múltiplo de p, a y p son primos relativos, es decir, no tienen factores comunes. Según el teorema de Euler, a^(φ(p)) ≡ 1 (mod p), donde φ(p) representa el número de enteros positivos que son menores que p y relativamente primos con p, por lo que hay φ(p)
≤ p-1.
Según el teorema fundamental de la aritmética, p es un número primo, por lo que φ(p) = p-1, por lo que existe:
a^(p-1) ≡ 1 (mod p)
El pequeño teorema de Fermat se utiliza ampliamente y uno de sus campos de aplicación importantes es la criptografía. En el algoritmo de cifrado, elija dos números primos grandes p y q, multiplique su producto pq como módulo público *** y elija un número entero e como clave pública, de modo que e sea igual a (p-1) *
(q-1) son primos relativos y luego elija un número entero d como clave privada tal que d*e ≡ 1
(mod (p-1) * (q-1 )), para que pueda utilizar el pequeño teorema de Fermat para manejar el cifrado y descifrado de manera eficiente.