El número de enteros positivos menores o iguales a [matemática] n [/ matemática] y relativamente primo a [matemática] n [/ matemática] viene dado por
[matemáticas] \ phi (n) = \ left | \ big \ {a: 1 \ le a \ le n, \ gcd (a, n) = 1 \ big \} \ right | = n \ displaystyle \ prod_ {p \ mid n} \ left (1- \ dfrac {1} {p} \ right) \ ldots (\ star) [/ math]
El producto está sobre todos los divisores primos de [math] n [/ math], y el producto vacío se define como [math] 1 [/ math].
- ¿Cuáles son los mejores libros para aprender estructuras de datos y algoritmos para un principiante con poco lenguaje de programación de C?
- ¿Cuáles son los mini proyectos que se pueden hacer en el algoritmo para el procesamiento de imágenes y videos?
- ¿Cuáles son las condiciones previas de la búsqueda binaria y qué papel desempeñan?
- ¿Cuándo debería mirar la solución de algún problema algorítmico?
- ¿Cuáles son los algoritmos necesarios para resolver div2 500 y div2 1000 fácilmente en topcoder?
Proporciono tres pruebas .
Prueba 1.
Deje [math] [N] = \ {1,2,3, \ ldots, N \} [/ math]. Considere el mapeo
[matemáticas] F: [mn] \ rightarrow [m] \ veces [n] [/ matemáticas]
dado por [math] a \ mapsto (a \ bmod {m}, a \ bmod {n}) [/ math], donde [math] a \ bmod {m} = m [/ math] if [math] m \ mid a [/ math] y [math] a \ bmod {n} = n [/ math] if [math] n \ mid a [/ math].
Ejercicio [matemáticas] F [/ matemáticas] es una biyección .
Afirmamos que la restricción [math] f [/ math] de [math] F [/ math] asigna el conjunto [math] {\ mathcal U} [mn] = \ {a \ in [mn]: \ gcd ( a, mn) = 1 \} [/ math] en el conjunto [math] {\ mathcal U} [m] \ times {\ mathcal U} [n] [/ math]. Esta restricción [matemática] f [/ matemática] es obviamente una por el ejercicio .
Si [math] a \ in {\ mathcal U} [mn] [/ math], entonces [math] \ gcd (a, mn) = 1 [/ math]. Por lo tanto, [math] \ gcd (a, m) = 1 [/ math] y [math] \ gcd (a, n) = 1 [/ math], de modo que [math] a \ in {\ mathcal U} [m ] \ cap {\ mathcal U} [n] [/ math]. Por lo tanto, la restricción [matemáticas] f [/ matemáticas] está bien definida .
El hecho de que [math] f [/ math] también está en el Teorema del resto chino (CRT) para dos módulos:
Dado [math] m, n \ in \ mathbb N [/ math], [math] \ gcd (m, n) = 1 [/ math] y [math] r, s \ in \ mathbb Z [/ math] , hay un número entero único [math] x \ bmod {mn} [/ math] tal que [math] x \ equiv r \ pmod {m} [/ math] y [math] x \ equiv s \ pmod {n} [/matemáticas].
La biyección demuestra que [math] \ phi [/ math] es una función multiplicativa :
[matemáticas] \ phi (mn) = \ big | {\ mathcal U} [mn] \ big | = \ big | {\ mathcal U} [m] \ big | \ cdot \ big | {\ mathcal U} [mn] \ big | = \ phi (m) \ cdot \ phi (n) [/ math]
si [matemática] \ mcd (m, n) = 1 [/ matemática].
Si [math] p [/ math] es primo y [math] \ alpha \ in \ mathbb N [/ math], entonces
[matemáticas] {\ matemáticas U} [p ^ {\ alpha}] = \ {a: 1 \ le a \ le p ^ {\ alpha}, p \ nmid a \} [/ matemáticas]
[math] = \ big [p ^ {\ alpha} \ big] \ setminus \ big \ {kp: 1 \ le k \ le p ^ {\ alpha -1} \ big \} [/ math].
Por lo tanto, [matemáticas] \ phi (p ^ {\ alpha}) = p ^ {\ alpha} – p ^ {\ alpha -1} = p ^ {\ alpha} \ left (1- \ frac {1} {p} \ right) [/ math].
Como [math] \ phi [/ math] es multiplicativo ,
[matemáticas] \ phi (n) = \ phi \ left (\ displaystyle \ prod_ {p \ mid n} p ^ {\ alpha} \ right) [/ math]
[math] = \ displaystyle \ prod_ {p \ mid n} \ phi (p ^ {\ alpha}) [/ math]
[math] = \ displaystyle \ prod_ {p \ mid n} p ^ {\ alpha} \ left (1- \ frac {1} {p} \ right) [/ math]
[matemáticas] = n \ displaystyle \ prod_ {p \ mid n} \ left (1- \ frac {1} {p} \ right). \ blacksquare [/ math]
Prueba 2.
Primero mostramos que
[matemáticas] \ displaystyle \ sum_ {d \ mid n} \ phi (d) = n \ ldots (1) [/ matemáticas]
Coloque el número entero [math] a \ in \ {1,2,3, \ ldots, n \} [/ math] en el cuadro etiquetado [math] d [/ math] provisto [math] \ gcd (a, n) = d [/ matemáticas]. Por lo tanto, cada uno de los enteros [math] n [/ math] se coloca en una casilla etiquetada [math] d [/ math] con [math] 1 \ le d \ le n [/ math] y [math] d \ mid n [/matemáticas]. Para cada uno de [math] d [/ math], [math] a = qd [/ math] se coloca en la casilla [math] d [/ math] si y solo si
[matemáticas] d = \ gcd (a, n) = \ gcd \ big (qd, \ frac {n} {d} d \ big) = d \ gcd \ big (q, \ frac {n} {d} \ grande) [/ matemáticas],
para que [math] \ gcd \ big (q, \ frac {n} {d} \ big) = 1 [/ math]. Dado que [math] 1 \ le a \ le n [/ math] se traduce a [math] 1 \ le q \ le \ frac {n} {d} [/ math], existen precisamente [math] \ phi \ big ( \ frac {n} {d} \ big) [/ math] enteros en el cuadro [math] d [/ math]. Contar el número de enteros sobre todos los cuadros da
[matemáticas] n = \ displaystyle \ sum_ {d \ mid n} \ phi \ big (\ frac {n} {d} \ big) = \ displaystyle \ sum_ {d \ mid n} \ phi (d) [/ math ]
Recuerde la función Mobius [math] \ mu: \ mathbb N \ rightarrow \ {0, \ pm 1 \} [/ math] dada por
[matemáticas] \ mu (n) = \ begin {cases} 1, & n = 1; \\ (-1) ^ k, & n \: \ text {es un producto de k primos distintos}; \\ 0, & \ text {de lo contrario}. \ end {cases} [/ math]
La fórmula de inversión de Mobius es la siguiente. Deje que [math] f: \ mathbb N \ rightarrow \ mathbb Z [/ math] sea cualquier función, y deje que [math] F (n) = \ displaystyle \ sum_ {d \ mid n} f (d) [/ math] . Entonces
[matemáticas] f (n) = \ displaystyle \ sum_ {d \ mid n} \ mu (d) \ cdot F \ left (\ dfrac {n} {d} \ right) [/ math].
Aplicando la fórmula de inversión de Mobius a la identidad en la ecuación. [matemáticas] (1) [/ matemáticas] rendimientos
[matemática] \ phi (n) = \ displaystyle \ sum_ {d \ mid n} \ mu (d) \ cdot \ dfrac {n} {d} [/ math]
[matemáticas] = n \ displaystyle \ sum_ {d \ mid n} \ dfrac {\ mu (d)} {d} [/ matemáticas]
[matemáticas] = n \ left (\ dfrac {\ mu (1)} {1} + \ displaystyle \ sum_i \ dfrac {\ mu (p_i)} {p_i} + \ displaystyle \ sum_ {i, j} \ dfrac { \ mu (p_ip_j)} {p_ip_j} + \ cdots \ right) [/ math]
[math] = n \ left (1 – \ displaystyle \ sum_i \ dfrac {1} {p_i} + \ displaystyle \ sum_ {i, j} \ dfrac {1} {p_ip_j} + \ cdots \ right) [/ math]
[matemáticas] = n \ left (1- \ dfrac {1} {p_1} \ right) \ left (1- \ dfrac {1} {p_2} \ right) \ left (1- \ dfrac {1} {p_3} \ right) \ cdots \ left (1- \ dfrac {1} {p_k} \ right) [/ math], donde [math] p_1, p_2, p_3, \ ldots, p_k [/ math] son los distintos divisores primos de [matemáticas] n [/ matemáticas]
[math] = n \ displaystyle \ prod_ {p \ mid n} \ left (1- \ frac {1} {p} \ right) [/ math]. [matemáticas] \ blacksquare [/ matemáticas]
Prueba 3.
Principio de inclusión y exclusión (PIE) . Si [math] X [/ math] es un conjunto finito y [math] A_1, \ ldots, A_k [/ math] son subconjuntos de [math] X [/ math], entonces
[matemáticas] \ izquierda | X \ setminus \ bigcup_ {i = 1} ^ k A_i \ right | = \ displaystyle \ sum_ {I \ subseteq [n]} (-1) ^ {| I |} \ cdot \ big | A_I \ big | [/ math], [math] \ ldots (\ text {PIE}) [ /matemáticas]
donde la suma está sobre todos los subconjuntos de [math] [n] = \ {1,2,3, \ ldots, n \} [/ math], [math] A_I = \ displaystyle \ bigcap_ {i \ in I} A_i [/ math] cuando [math] I \ ne \ emptyset [/ math] y [math] A _ {\ emptyset}: = X [/ math].
Para aplicar PIE , suponga que [math] p_1, \ ldots, p_k [/ math] son los principales divisores de [math] n [/ math]. Establezca [matemática] X = [n] [/ matemática] y
[matemáticas] A_i = \ left \ {mp_i: 1 \ le m \ le \ dfrac {n} {p_i} \ right \}, \: \: 1 \ le i \ le k [/ math].
Observe que [math] X \ setminus \ bigcup_ {i = 1} ^ k A_i [/ math] es el conjunto de enteros positivos menores o iguales a [math] n [/ math] que no son divisibles por ninguno de los primos [matemáticas] p_1, \ ldots, p_k [/ matemáticas] que dividen [matemáticas] n [/ matemáticas]. Por lo tanto, este conjunto consiste precisamente en aquellos enteros menores o iguales a n que son coprimos a [matemática] n [/ matemática], y por lo tanto el LHS de la ecuación. [matemáticas] (\ text {PIE}) [/ matemáticas] es igual a [matemáticas] \ phi (n) [/ matemáticas].
Suponga que [matemáticas] | I | = r [/ matemáticas]; para mayor claridad, dejemos [math] I = \ {1,2,3, \ ldots, r \} [/ math]. Entonces
[matemáticas] A_I = A_1 \ cap A_2 \ cap A_3 \ cap \ ldots \ cap A_r [/ math]
es el conjunto de todos los múltiplos comunes [math] p_1, \ ldots, p_r [/ math], y dado que estos son primos distintos, también son múltiplos de su producto. Como hay [matemática] n / (p_1 \ cdots p_r) [/ matemática] tales múltiplos en [matemática] X [/ matemática], tenemos [matemática] \ big | A_I \ big | = n / (p_1 \ cdots p_r )[/matemáticas]. Por un razonamiento similar, de la ec. [matemáticas] (\ text {PIE}) [/ matemáticas] tenemos
[matemáticas] \ phi (n) = n – \ displaystyle \ sum_i \ dfrac {n} {p_i} + \ displaystyle \ sum_ {i, j} \ dfrac {n} {p_i \, p_j} + \ cdots + (- 1) ^ k \ dfrac {n} {p_1p_2 \ cdots p_k} [/ math]
[matemáticas] = n \ displaystyle \ prod_ {p \ mid n} \ left (1- \ frac {1} {p} \ right). \ blacksquare [/ math]
