Teoremas de Fermat y Euler

Es exactamente la condición de tener inverso, por Bézout. Sus productos e inversos también son unidades: forman un grupo finito U(m), con neutro [1].

φ(m), totiente de Euler, cuenta cuántas unidades hay. No cuenta cuántos representantes son primos ni cuántos son distintos de cero. Para módulos compuestos, algunas clases no nulas no pertenecen a ese grupo.

Si m=pᵏ con p primo y k≥1, no ser coprimo equivale a ser múltiplo de p. Entre cero y pᵏ−1 hay p^(k−1) de esos múltiplos.

La cuenta se hace sobre representantes canónicos, una vez por clase, aunque cada clase tenga infinitos enteros.

Si los primos distintos que dividen m son p₁,…,pᵣ, las unidades evitan todos sus múltiplos. Quitamos los múltiplos de cada primo y reponemos los de intersecciones que se quitaron varias veces. Como esos productos de primos dividen m, sus cantidades son exactas.

La expresión queda φ(m)=m∏ sobre p|m de (1−1/p), usando cada primo una sola vez. También φ(mn)=φ(m)φ(n) cuando m,n son coprimos; el teorema chino del resto explicará la correspondencia por componentes. Sin coprimalidad esa multiplicatividad puede fallar.

Cada arᵢ es unidad; si arᵢ≡arⱼ, cancelamos a y obtenemos rᵢ≡rⱼ. Los h productos son distintos y recorren la misma lista en otro orden.

P es invertible porque sus factores lo son, y cancelarlo da a^φ(m)≡1. La prueba muestra exactamente dónde se utiliza mcd(a,m)=1.

Es el pequeño teorema de Fermat. No se refiere al último teorema de Fermat sobre ecuaciones de potencias.

Multiplicar por a da aᵖ≡a. Esta segunda forma vale para todo entero a: cuando p|a ambos lados son cero, y cuando no, se deduce de la primera. En cambio no afirmamos a^(p−1)≡1 si la base es múltiplo del primo.

Para una unidad a, su orden t es el menor exponente positivo con aᵗ≡1.

La minimalidad obliga a r=0; t divide todo exponente de regreso, en particular φ(m).

Así φ(m) da un período garantizado, no necesariamente el más corto. Calcular el orden puede reducir aún más el trabajo. Esta es una noción multiplicativa; el orden de una clase en el grupo aditivo sería otra pregunta.

El exponente se reduce módulo φ(m), mientras el resultado sigue calculándose módulo m.

La elevación por cuadrados, en cambio, solo necesita reglas de producto: calcula a,a²,a⁴,… con reducción en cada paso y combina los exponentes de la escritura binaria de e. Funciona también con no unidades; lo que exige coprimalidad es la reducción por Euler.

Euler da a·a^(φ(m)−1)≡1, así el inverso de una unidad se puede calcular como esa potencia. En módulo primo p, a⁻¹≡a^(p−2). Si p=2, el exponente es cero y la única clase no nula es uno, por lo que la fórmula sigue funcionando.

Euclides extendido suele dar el inverso sin conocer φ(m), y puede ser más corto. Las fórmulas por potencias son útiles cuando ya conocemos el módulo primo o tenemos exponenciación eficaz. En cualquiera de las dos vías, multiplicar debe devolver uno.

Si mcd(a,n)=1 y a^(n−1) no es uno módulo n, n no puede ser primo por Fermat. Pero si da uno, puede ser primo o compuesto. Pasar una sola base no invierte lógicamente un teorema con hipótesis de primalidad.

También mantenemos la hipótesis de Euler: una base no unidad puede tener potencias que repiten sin volver a uno. No confundimos repetición eventual con un ciclo del grupo de unidades.