Algoritmo

´ ESCUELA POLITECNICA NACIONAL ´ MATEMATICAS DISCRETAS 25 de Diciembre del 2018

Integrantes: • Manchay Romero Nubia • Simba˜ na Danny

Docente • Dr. Felipe Urquiza 2018 - B

1

1

Totient de Euler

En la teor´ıa num´erica, totient de Euler o funci´on de phi, f (n), es una funci´on aritm´etica que cuenta el totatives de n, es decir los n´ umeros enteros positivos menos que o igual a n que son relativamente principales a n. As´ı, si n es un n´ umero entero positivo, entonces f (n) es el n´ umero de n´ umeros enteros k en la variedad 1 = k = n para cual el mayor com´ un divisor gcd (n, k) = 1. La funci´on de totient es una funci´on de multiplicative, significando esto si dos n´ umeros m y n son relativamente principales (el uno al otro), entonces f (mill´on) = f (m) f (n). Por ejemplo deje a n = 9. Entonces gcd (9, 3) = gcd (9, 6) = 3 y gcd (9, 9) = 9. Los otros seis n´ umeros en la variedad 1 = k = 9, que es 1, 2, 4, 5, 7 y 8 son relativamente principales a 9. Por lo tanto, f (9) = 6. Como otro ejemplo, f (1) = 1 desde gcd (1, 1) = 1. La funci´ on de totient es importante principalmente porque da el pedido del grupo multiplicative de n´ umeros enteros modulo n (el grupo de unidades del anillo). Ver el teorema de Euler. La funci´on de totient tambi´en desempe˜ na un papel fundamental en la definici´on del sistema de la codificaci´on RSA. La funci´ on Totient de Euler se define como el n´ umero de enteros positivos <= n que son primos relativos con n, donde 1 se encuentra relativamente primo a todos los n´ umeros. Dado que un n´ umero menor o igual y relativamente primo a un n´ umero dado se denomina totativo, la funci´on titiente φ(n) se puede definir simplemente como el n´ umero de totativos de n. Por ejemplo, hay ocho totativos de 24 (1, 5, 7, 11, 13, 17, 19 y 23), entonces φ(24) = 8. El n´ umero n − φ(n) se denomina cototiente de n y da el n´ umero de enteros positivos <= n que tienen al menos un factor primo en com´ un con n φ(n) siempre es par para n >= 3. Por convenci´on, φ(0) = 1. Los primeros valores de φ(n) para n = 1, 2, ... son 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, .... La funci´on totiente est´a dada por la transformada de M¨ obius de 1, 2, 3, 4, .... φ(n) se representa arriba para n peque˜ na. Para un primer p: φ(p) = p − 1.

Ya que todos los n´ umeros menores que p son relativamente primos a p. Si m = pα es la potencia de un primo, entonces los n´ umeros que tienen un factor com´ un con m son los m´ ultiplos de p : p, 2p, ..., (pα−1 )p. Hay α−1 p de estos m´ ultiplos, por lo que el n´ umero de factores relativamente primos a pα es.

φ(pα ) = pα − pα−1 φ(pα ) = pα−1 (p − 1) 1 φ(pα ) = pα (1 − ). p

Ahora toma una general divisible por p. Sea φp (m) el n´ umero de enteros positivos <= m no divisible por p. Como antes, p, 2p, ..., (m / p) p tienen factores comunes, por lo que:

2

m p 1 φp (m) = m(1 − ). p φp (m) = m −

Ahora sea q alguna otra prima primitiva m. Los enteros divisibles por q son q, 2q, ..., (m / q) q. Pero estos pq duplicados, 2pq, ..., (m / (pq)) pq. Entonces, el n´ umero de t´erminos que se deben restar de φp para obtenerφpq es:

∆φq (m) = mq − mpq 1 m (1 − ) q p

= y

φpq (m) = φp (m) − ∆φq (m) 1 m 1 φpq (m) = m(1 − ) − (1 − ) p q p 1 1 φpq (m) = m(1 − )(1 − ). p p

Por inducci´ on, el caso general es entonces. φ(n) = n

Y 1 (1 − ) p p|n

φ(n) = n(1 −

1 1 1 )(1 − )...(1 − ), p1 p2 pr

donde el producto se ejecuta sobre todos los n´ umeros primos p dividiendo n. Una identidad interesante que relaciona φ(nk ) con φ(n) viene dada por φ(nk ) = nk−1 φ(n)

Otra identidad relaciona los divisores d de n con n via X φ(d) = n. d|n

La funci´ on totient est´ a conectada a la funci´ on M¨obius µ(n) a trav´es de la suma X d

n dµ( ) = φ(n), d

donde la suma est´ a sobre los divisores de n, lo que puede comprobarse por inducci´on en n y el hecho de que µ(n) y φ(n) son multiplicativos. La funci´ on totient tiene la funci´ on de generaci´on de Dirichlet. ∞ X φ(n) ζ(s − 1) = s n ζ(s) n=1

3

La funci´ on totiente satisface la desigualdad.φ(n) ≥

√

n

F uente : https : //www.wolf ramalpha.com/widgets/view.jsp?id = c98e7eb508ad306c40cc4d7773a3a69a

4