Fi-función de Euler y números primos

Sea R={r1, r2, ..., rm} el conjunto de los números coprimos con n tal que 1 <= ri <= n-1

Se cumple m = fi(n)

Ahora creamos el conjunto xR que no es el conjunto R multiplicado por x

xR = {x·r1, x·r2, ..., x·rm}

Como x es coprimo con n, no tiene ningun factor primo común con n, y los ri tampoco, luego se verifica que cada elemento de xR es coprimo con n.

mcd(n, x·ri) = 1 para todo 1<=i <=fi(n)

Restamos a x·ri las veces que sea necesario el valor n para que el resultado esté entre 0 y n-1, ello es posible por el algiritmo de la division, sea c sub i el cociente. Y por el algoritmo del mcd de Euclides tenemos

1 = mcd(n, x·ri) = mcd(n, x·ri - ci·n)

luego

x·ri == (un coprimo con n) (mod n)

Siendo ese coprimo comprendido entre 0 y n-1. El cero no cuenta ya que entonces xri sería multiplo de n y ya habiamos visto que los x·ri eran coprimos con n.

Luego el conjunto de los elementos de xR es congruente con números entre 1 y n-1 que son coprimos con n. Ese conjunto es que hemos llamado R.

Veamos que la aplicación es inyectiva, que dos elementos distintos de xR son congruentes con dos elementos distintos de R

Sean i, j tales que

x·ri == x·rj (mod n)

sin perder generalidad supongamos ri>= rj

eso implica

x·ri = x·rj + kn con k € Z

x(ri-rj) = kn

x no tiene ningún factor primo de n

y también se cumple

0 <= ri-rj <= n-2

luego r--rj no puede tener todos los factores primos de n

entonces la igualdad x(ri-rj) = kn es imposible salvo que kn=0 luego ri-rj=0 luego ri=rj

Resumiendo, la aplicación que relaciona cada elemento de xR con su congruente mod n en R es biyectiva.

Tecnicamente, xR y R son sistemas reducidos de residuos mod n

Hagamos el producto de los elementos de uno y otro conjunto

u = r1·r2···· rm

v = x·r1·x·r2····x·rm = r1·r2····rm· x^[fi(n)]

Como cada elemento de R tiene su congruente mod n en xR, los dos productos son congruentes mod n

u == v (mod n)

u == u·x^[fi(n)] (mod n)

U es un producto de coprimos con n, luego es coprimo con n, ya que no tendrán ningún factor primo común.

La teoría dice que un factor coprimo con n se puede cancelar en la congruencia, cancelaríamos u y ya estaría demostrado. No obstante, por si no conoces esa teoría lo cancelamos por deducción

u·x^[fi(n)] = u + kn

u{x^[fi(n)] - 1} = kn

Como u no tiene ningun factor primo de n será x^[fi(n)] - 1 el que los tenga todos, luego será múltiplo de n y por lo tanto

x^[fi(n)] - 1 == 0 (mod n)

y sumando uno en los dos lados

x^[fi(n)] == 1 (mod n)

Y eso es todo, espero que te sirva y lo hayas entendido. Tal vez conozcas teoremas que hagan más simple la demostración, pero como yo no sé si los sabes he hecho esto que no presupone teoremas poco obvios.