Funcion Phi de Euler

Función de Euler

Idea.

También conocida como función totiente, cuenta la cantidad de números enteros positivos menores o iguales a un número que son coprimos con él. Recordemos que dos núms. son coprimos si su MCD es igual a .

Definición. (Función Phi de Euler)

La funcíon phi de euler es tal que es la cantidad de elementos en un juego reducido de residuos módulo .

Ejemplo.

Sabemos que es un juego completo de residuos módulo .
Quitando a los elementos que no son primos relativos con tenemos,

Así, es un juego reducido de residuos módulo .
Tenemos entonces que
Como

entonces es otro juego reducido de residuos módulo .

Proposición.

Sean , con .

1. Si es un juego completo de residuos módulo , entonces también es un juego completo de residuos módulo .
2. Si es un juego reducido de residuos módulo , entonces también es un juego reducido de residuos módulo .

Proof.

Ejemplo.

Teorema de Euler.

Teorema (Teorema de Euler para Congruencias)

Sean con . Tenemos que

Proof.

Ejemplo.

Proposición 1.

Sea un número primo. Tenemos que

Proof.

Sea primo.
es un juego completo de residúos módulo . Sabemos que y ya que es primo.
Así, es un juego reducido de residuo módulo . Por lo tanto,

Proposición 2.

Sea un número primo, . Tenemos que,

Proof.

Sea primo,
es un juego completo de residuos módulo , pues observece que . De estos números quitamos que no son primos relativos con para obtener un juego reducido de residuos.

Proposición 3.

Sean con , tenemos que,

Proof.

… esta larga

Ejemplo.

Corolario.

Sean primos distintos, . Si , entonces,

Proof.

Sean primos distintos, con .

Ejemplos.