7.4: Pequeño teorema de Fermat

NOTACIÓN. \(\mathbb{Z}_{n}^{*}\)Vamos\(n \in \mathbb{N}, n \geq 2\). Después\[\mathbb{Z}_{n}^{*}=\mathbb{Z}_{n} \backslash\{[0]\} .\] LEMA 7.14. Que\(a, n \in \mathbb{Z}, n \geq 2\), sea tal que\(\operatorname{gcd}(a, n)=1\). Definir\(\phi_{a}: \mathbb{Z}_{n}^{*} \rightarrow \mathbb{Z}_{n}^{*}\) por\[\phi_{a}([b])=[a b] .\] Entonces\(\phi_{a}\) es una permutación de\(\mathbb{Z}_{n}^{*}\). Prueba. Mostramos que\([a],[2 a], \ldots,[(n-1) a]\) son elementos distintos de\(\mathbb{Z}_{n}^{*}\). Dejemos\(0<i \leq j<n\) y supongamos eso\(i a \equiv j a \bmod n\). Entonces\[n \mid j a-i a\] y\[n \mid(j-i) a .\] asumimos eso\(\operatorname{gcd}(n, a)=1\), así por Proposición\(7.3, n \mid(j-i)\). Sin embargo\(0 \leq j-i<n\), así\(j-i=0\) y\(i=j\). De ahí, si\(0<i<j<n\), De\[[i a] \neq[j a] .\] ello se deduce que\(\phi_{a}\) es una inyección de\(\mathbb{Z}_{n}^{*}\) a\(\mathbb{Z}_{n}^{*}\). Cualquier inyección de un conjunto finito a sí mismo es una sobreyección, así\(\phi_{a}\) es una permutación de\(\mathbb{Z}_{n}^{*}\).

Definición. Orden,\(o_{p}(a)\) Let\(p\) Ser un número primo y\(a \in \mathbb{Z}\) no un múltiplo de\(p\). El orden de\(a\) in\(\mathbb{Z}_{p}\) es el menos\(k \in \mathbb{N}^{+}\) tal que\(a^{k} \equiv 1 \bmod p\). Escribimos el orden de\(a\) en\(\mathbb{Z}_{p}\) como\(o_{p}(a)\).

Si\(a\) es un múltiplo de\(p\), entonces el orden de\(a\) in\(\mathbb{Z}_{p}\) es indefinido, ya que\(a \equiv 0 \bmod p\), y para todos\(k \in \mathbb{N}^{+}\),\[a^{k} \equiv 0 \quad \bmod p .\] La siguiente proposición muestra en particular que si \(a\)no es un múltiplo de\(p\), entonces el orden está bien definido (es decir, que hay algunos\(k\) con\(a^{k} \equiv 1\)\(\bmod p)\).

PROPOSICIÓN 7.15. Dejar\(a \in \mathbb{Z}\), y\(p\) ser un número primo tal que\(p \nmid a\). Entonces\(o_{p}(a)<p\).

Prueba. Dejar\(p\) ser un número primo y\(a \in \mathbb{Z}\) ser tal que no\(a\) sea un múltiplo de\(p\). Por Lema 7.5, como\(p \nmid a\), entonces\(p \nmid a^{n}\), y por lo tanto\(\left[a^{n}\right] \in \mathbb{Z}_{p}^{*}\) para cualquier\(n \in \mathbb{N}\). Ya que\(\left|\mathbb{Z}_{p}^{*}\right|=p-1\), la secuencia finita\[\left\langle\left[a^{n}\right] \mid 1 \leq n \leq p\right\rangle\] debe tener una repetición. \(1 \leq n<k \leq p\)Sea tal que\[a^{n} \equiv a^{k} \quad \bmod p .\] Entonces\[p \mid a^{k}-a^{n} .\] De ahí\[p \mid a^{n}\left(a^{k-n}-1\right) .\] Sin embargo\(p \nmid a^{n}\) y así por la Proposición 7.3,\[p \mid a^{k-n}-1 .\] Así\[a^{k-n} \equiv 1 \quad \bmod p .\] Por tanto\[o_{p}(a) \leq k-n<p .\] la Proposición 7.16. Dejar\(a \in \mathbb{Z}\) y\(p\) ser un número primo tal que no\(a\) sea un múltiplo de\(p\). Entonces las clases restantes\([1],[a],\left[a^{2}\right], \ldots,\left[a^{o_{p}(a)-1}\right]\) en\(\mathbb{Z}_{p}\) son distintas.

PRUEBA. Ejercicio.

NOTACIÓN. \(S_{a}(n)\)Arreglar un primo\(p\) para el resto de esta sección. Dejar a ser un entero tal que\(p \nmid a\). Entonces para cualquier número natural positivo\(n\), dejamos\(S_{a}(n)\) denotar el conjunto de clases de equivalencia\(\left\{\left[n \cdot a^{k}\right] \mid k \in \mathbb{N}\right\}\) en\(\mathbb{Z}_{p}\). (Aunque\(S_{a}(n)\) depende de la elección de\(p\), suprimimos esto en la notación y asumimos que\(p\) se entiende).

LEMA 7.17. Que\(a \in \mathbb{Z}\) sea tal que\(p \nmid a\). Si no\(n \in \mathbb{N}^{+}\) es múltiplo de\(p\), entonces\[\left|S_{a}(n)\right|=o_{p}(a) .\] Prueba. Por Proposición 7.15,\(o_{p}(a)<p\). Vamos\(k=o_{p}(a)\). Por Proposición\(7.16\) las clases restantes\([1],[a],\left[a^{2}\right], \ldots,\left[a^{k-1}\right]\) son distintas. Seamos\(\phi_{n}\) definidos como en Lema 7.14. Entonces\(\phi_{n}\) es una permutación de\(\mathbb{Z}_{p}^{*}\). Por lo tanto, las clases restantes\([n],\left[n a^{2}\right], \ldots,\left[n a^{k-1}\right]\) son distintas. Pero\[n a^{k} \equiv n \quad \bmod p,\] SO\[S_{a}(n)=\left\{[n],\left[n a^{2}\right], \ldots,\left[n a^{k-1}\right]\right\}\] (¿Por qué?) Por lo tanto\[\left|S_{a}(n)\right|=o_{p}(a)\] LEMMA 7.18. Que\(a \in \mathbb{Z}\) sea tal que\(p \nmid a\). Entonces para cualquiera\(m, n \in \mathbb{N}^{+}\) que no sean múltiplos de\(p\), los conjuntos\(S_{a}(m)\) y\(S_{a}(n)\) sean iguales o disjuntas.

PRUEBA. \(S_{a}(m) \cap S_{a}(n) \neq \emptyset .\)Supongamos Let\(m, n \in \mathbb{N}, \operatorname{gcd}(m, p)=1\)\(\operatorname{gcd}(n, p)=1\) y\[\left[m a^{i}\right] \in S_{a}(n)\] Entonces hay\(j \in \mathbb{N}\) tal que\[\left[m a^{i}\right]=\left[n a^{j}\right]\] Podemos suponer que\(i<j\), ya que hay infinitamente muchos\(j \in \mathbb{N}^{+}\) que satisfacen la ecuación. Entonces\[[m]=\left[n a^{j-i}\right]\] Entonces\[[m] \in S_{a}(n)\] Por lo tanto si\(S_{a}(m)\) y no\(S_{a}(n)\) son disjuntas, tenemos\[S_{a}(m) \subseteq S_{a}(n)\] Por simetría, también tenemos\[S_{a}(n) \subseteq S_{a}(m)\] y así ya sea\[S_{a}(m)=S_{a}(n)\] o\[S_{a}(m) \cap S_{a}(n)=\emptyset\] TEOREMA 7.19 . El pequeño teorema de Fermat Si\(a \in \mathbb{Z}\) y\(p\) es un número primo tal que\(p \nmid a\), entonces\[a^{p-1} \equiv 1 \quad \bmod p .\] Prueba. Vamos\(k=o_{p}(a)\). Eso lo demostramos\(k \mid(p-1)\). Vamos\(n \in \mathbb{N}\), donde no\(n\) es un múltiplo de\(p\). Por Lemma\(7.17\)\[\left|S_{a}(n)\right|=k .\] Por Lemma 7.18, los conjuntos\(\mathbb{Z}_{p}^{*}\) se\[\left\{S_{a}(n) \mid n \in \mathbb{N}^{+}, p \nmid n\right\}\] particionan en conjuntos de cardinalidad\(k\). Por lo tanto\(k\) divide\(\left|Z_{p}^{*}\right|\). Ya que\(\left|Z_{p}^{*}\right|=p-1\), tenemos\[k \mid(p-1) .\] Se deduce que hay\(j \in \mathbb{N}\) tal que\[a^{p-1} \equiv\left(a^{k}\right)^{j} \equiv 1^{j} \equiv 1 \quad \bmod p .\] COROLARIO 7.20. Si\(a \in \mathbb{Z}\) y\(p\) es un número primo tal que\(p \nmid a\), entonces el pequeño teorema de\[a^{p} \equiv a \quad \bmod p .\] Fermat es un resultado importante en el estudio teórico de los números primos, y determinando la primalidad. ¿Cómo podría utilizarse el teorema? Considera el problema de decidir si un número natural en particular\(n\) es primo. Para determinar si\(n\) es primo, puede invocar el Teorema Fundamental de la Aritmética, y comenzar a verificar todos los números primos\(\sqrt{n}\) hasta determinar si alguno son factores no triviales de\(n\). No es necesario verificar primos mayores que\(\sqrt{n}\) ya que la existencia de tal factor conlleva la existencia de un factor menor entonces\(\sqrt{n}\), y por el Teorema Fundamental de la Aritmética, un factor primo menor que\(\sqrt{n}\). Esto puede requerir verificar muchos candidatos, además de requerir que conozca todos los números primos más pequeños que\(\sqrt{n}\), o esté dispuesto a verificar factores que no son primos. Para grandes\(n\) este es un reto formidable. Alternativamente, se puede buscar\(a \in \mathbb{Z}\) tal que\(\left[a^{n}\right] \neq[a]\) para determinar que no\(n\) es primo.\(\mathbb{Z}_{n}\)

Por ejemplo, ¿es 12,871 prime? Suponemos que tienes acceso a una computadora (hacer estos cálculos a mano puede ser tedioso). Un enfoque es verificar los factores entre los números primos menores que\(\sqrt{12,871}\), es decir, los treinta números primos menores que 114. Alternativamente, para\(a \in \mathbb{Z}\), podemos comprobar si\[a^{12,871} \equiv a \quad \bmod 12,871 .\] Si la respuesta es no, entonces 12,871 no es primo. Intentaremos\(a=2\):\[2^{12,871} \equiv 5732 \bmod 12,871 .\] Por lo tanto 12,871 no es primo. Si tuvieras que verificar los primos secuencialmente, tendrías que verificar 18 primos antes de encontrar que 61 es el primo más pequeño que divide 12,871.

Si\(a^{12,871} \equiv a \bmod 12,871\) por una elección dada de\(a\), entonces no podemos sacar ninguna conclusión. De hecho hay números no primos,\(n\), tal que para cualquier elección de\(a\),\[a^{n} \equiv a \bmod n .\] Los números que satisfacen la conclusión del Teorema 7.19, pero que no son primos se llaman números Carmichael. De modo que el pequeño teorema de Fermat se puede utilizar para demostrar que un número no es primo, sino para demostrar que un número es primo.