El pequeño teorema de Fermat y la relación de congruencia polinómica

Question

De acuerdo a este artículo de la Wikipedia, sabemos que un entero $n\; (\geq 2)$ es primo si y solo si el polinomio congruencia relación

$$ (x - a)^n \equiv (x^n - a) \pmod{n} $$

tiene para todos los enteros $a$ coprime a $n$ (o incluso sólo para algunos de estos entero $a$, en particular por $a = 1$).

A continuación, el Fermat Poco Teorema dice, $n$ es probable primer si

$$ a^n \equiv \pmod{n} $$

Dentro del artículo se dice $x$ nunca debe ser sustituido por un número, así que Si lo hacemos, entonces, para las pruebas de primalidad de un número como $211$ tendríamos algo como esto como un ejemplo :

$$ (2 + 3)^{211} \equiv 2^{211} + 3 \pmod{n} $$

Así que no podemos usar la ecuación anterior para una cierta reducción en la exponenciación modular?

Answer 1

Si usted tiene $n=211$, se puede utilizar, pero usted tiene que saber su $n$ es primo. Y entonces usted tendría $$(2+3)^{211} \equiv 2^{211} + 3 \pmod{211}$$

Para un primer $p$ siempre es verdadero que: $$ (x+y)^p \equiv x^p + y^p\pmod{p} $$

Pero si usted está buscando para la explicación de la prueba, usted no debe hacer eso. La parte que dice que usted no debería sustituir a $x$ significa que usted debe buscar en el polinomio $(x-a)^n$, con lo cual será determinado por sus coeficientes, es decir, si $f=(x-a)^n$, entonces se puede escribir también como una suma $f=\sum_{i=0}^{n} a_{i}x^{n}$ (si se expanda el producto), y usted debe comprobar si $a_i \equiv 0 \pmod{n}$ todos los $1<i<n$$a_0\equiv a \pmod{n}$.