Cojunto y Modulo

Question

Para cualquier entero n mayor que 1, psi(n) indica el número de enteros positivos menos que n y relativamente privilegiada para n. demuestran eso si una es cualquier número entero relativamente privilegiada a n, luego un ^ modn psi (n) = 1

Yo estaba pensando usar pequeño Teorema de Fermats o alguna manipulación de U(n), pero no puedo poner juntos una prueba adecuada. ¿Puedo tener algún consejo o explicación paso a paso?

Answer 1

Si una es relativamente privilegiada a n, entonces existe en U(n). Phi(n)=Order(U(n)) y orden de un U(n) en deben dividir el orden de U(n). Por lo tanto, el phi (n) = k orden de una en U(n). un ^ phi (n) = a ^ (orden de una U(n) en) k = e ^ k = 1.

Answer 2

Si $\phi(m) = n$

$(a_1m)(a_2m)...(a_nm) \equiv a_1a_2...a_n \pmod m$

Donde $a_1, a_2, ... a_n$ son todos los números menos de m que son coprimos m.

Ahora puede cancelar $a_1a_2...a_n$ en ambos lados como coprimos m, dejando $m^n \equiv 1 \pmod m \Rightarrow m^{\phi(m)} \equiv 1 \pmod m$