Te recomendamos que pruebes esta respuesta en un ambiente controlado antes de pasarlo a producción, un saludo.
Solución:
Si $a$ es divisible por $p$, es obvio.
Si no, el Pequeño Teorema de Fermat es equivalente a $a^p-1equiv 1bmod p$.
Elevar ambos lados a cualquier potencia muestra que $a^xequiv 1bmod p$ para cualquier $x$ un múltiplo de $p-1$.
$p^k-1$ es múltiplo de $p-1$: $(p-1)(p^k-1+p^k-2+ldots+1)$.
Pista: Toma $k = 2$. Tenemos $$a^p^2 equiv (a^p)^p equiv (a)^p equiv a pmod p$$
Insinuación $ $ Por una inducción obvia, todo conjunto cerrado por multiplicación es cerrado por potencias.
Tenga en cuenta que $ color#c00a^J equiv aequiv color#0a0a^K,Rightarrow, a^color#c00Jcolor #0a0Kequiv (color#c00a^J)^color#0a0Kequiv color#0a0a^Kequiv a,$ entonces el conjunto $,S,$ de $,N,$ con $,a^Nequiv a$
satisface $ color#c00J,color#0a0Kin S Rightarrow color#c00Jcolor#0a0Kin S, $ ie $S ,$ se cierra bajo la multiplicación, por lo que bajo potencias.
En particular $ a^Pequiv a,Rightarrow, pin S,Rightarrow, p^kin S,$ para todo $,kge 1$.
Observación $ $ Nótese cómo poner en primer plano lo innato monoide La estructura (cierre bajo producto) sirve para reducir la inducción a una inducción trivial, que los monoides se cierran bajo alimentación. Tales simplificaciones a menudo son posibles en pruebas inductivas comunes, por lo que vale la pena buscar primero una estructura simplificadora antes de sumergirse de cabeza en las inducciones de fuerza bruta.
Sección de Reseñas y Valoraciones
Recuerda que puedes comentar si te fue útil.