miércoles, 6 de junio de 2007

Euler totient

Si mcd(a,m)=1 entonces a^fi(m)=1 mod m

Hallar los dos ultimos digitos de N=17^19^23^29^31^37.

17^19^23^29^31^37 (mod 100) fi(100)=40

19^23^29^31^37 (mod 40) fi(40)=16

23^29^31^37 (mod 16) fi(16)=8

29^31^37 (mod 8) fi(8)=4

31^37 (mod 4) fi(4)=2

37 (mod 2) fi(2)=1 Ahora procedemos al revés:

37=1 (mod 2)

31^37 =31^1=31=3 (mod 4)

29^31^37 =29^3=5^3=5 (mod 8)

23^29^31^37= 23^5=7^5= 7 (mod 16)

19^23^29^31^37 = 19^7=19 (mod 40)

17^19^23^29^31^37 =17^19= 53 (mod 100) que son los dos ultimos digitos

León-Sotelo





No hay comentarios: