Para [math] n \ in \ mathbb {N} [/ math], la función totient de Euler es [math] \ varphi (n) = | \ mathbb {Z} _n ^ * | [/ math], el orden de la Multiplicativa grupo de enteros módulo n, que está compuesto por las clases de residuos mod-n de enteros que son coprimos a n, que pueden representarse por enteros de 1 a n: [matemáticas] \ varphi (n) = | \ {i \ in (1..n): (i, n) = 1 \} | [/ math].
Dada una secuencia infinita [matemáticas] (m_i = \ varphi (m_ {i + 1})) [/ matemáticas], llamamos al primer miembro “infinitamente Euler”. Los miembros posteriores también son infinitamente Euler como primer miembro de una subsecuencia que comienza allí.
[math] \ varphi [/ math] es multiplicativo para argumentos coprime:
[matemática] \ varphi (2 ^ {k_2} \ cdot 3 ^ {k_3} \ cdot .. \ cdot p ^ {k_p} \ cdot q ^ {k_q}) = [/ matemática] [matemática] \ varphi (2 ^ {k_2}) \ varphi (3 ^ {k_3}) .. \ varphi (p ^ {k_p}) \ varphi (q ^ {k_q}) [/ math]
así que primero considera [math] \ varphi [/ math] en los poderes primarios, donde
[math] \ mathbb {Z} _ {p ^ i} ^ * = \ mathbb {Z} _ {p ^ i} \ setminus p \ mathbb {Z} _ {p ^ i} [/ math] implica [math] \ varphi (p ^ i) = [/ matemática] [matemática] p ^ i – p ^ {i-1} = (p-1) p ^ {i-1} [/ matemática]
La firma prima es la lista de exponentes en la factorización prima de un número.
Examinemos cómo cambia de [matemáticas] p ^ i [/ matemáticas] a [matemáticas] \ varphi (p ^ i) [/ matemáticas]. Por un lado, el exponente de p, [math] k_p [/ math] disminuye en 1. Por otro lado, excepto por los valores más pequeños de p, la factorización de (p-1) introducirá primos adicionales a la firma .
- Some Airways ofrece tres tipos de boletos en sus vuelos de Boston a Nueva York. Los boletos de primera clase son 70, los boletos de segunda clase son 55 y los boletos de reserva son 39. Si 69 pasajeros pagan un total de 3274 por sus boletos en un vuelo en particular, ¿cuántos de cada tipo de boletos se vendieron?
- Supongamos que byc son enteros positivos de modo que las ecuaciones polinómicas [matemáticas] x ^ 2 + bx + c = 0 [/ matemáticas] y [matemáticas] x ^ 2 + bx-c = 0 [/ matemáticas] ambas tienen soluciones enteras. Determine la suma de todos los valores de [math] b \ leq50 [/ math] para los que existen polinomios de esta forma.
- ¿Por qué el producto de tres enteros consecutivos es divisible por 6?
- ¿Cómo puedes explicar los números catalanes en el término de laico?
- ¿Qué es una explicación intuitiva de la aritmética modular?
[matemáticas] \ varphi (2 ^ {k_2}) = (2-1) \ cdot 2 ^ {k_2-1} = 2 ^ {k_2-1} [/ matemáticas]
[matemáticas] \ varphi (3 ^ {k_3}) = (3-1) \ cdot 3 ^ {k_3-1} = (2) \ cdot 3 ^ {k_3-1} [/ matemáticas]
[matemáticas] \ varphi (5 ^ {k_5}) = (5-1) \ cdot 5 ^ {k_5-1} = (2 ^ 2) \ cdot 5 ^ {k_5-1} [/ math]
[matemáticas] \ varphi (7 ^ {k_7}) = (7-1) \ cdot 7 ^ {k_7-1} = (2 \ cdot 3) \ cdot 7 ^ {k_7-1} [/ math]
[matemáticas] \ varphi (11 ^ {k_ {11}}) = (11-1) \ cdot 11 ^ {k_ {11} -1} = (2 \ cdot 5) \ cdot 11 ^ {k_ {11} – 1} [/ matemáticas]
[matemáticas] \ varphi (13 ^ {k_ {13}}) = (13-1) \ cdot 13 ^ {k_ {13} -1} = (2 ^ 2 \ cdot 3) \ cdot 13 ^ {k_ {13 } -1} [/ matemáticas]
[matemáticas] \ varphi (17 ^ {k_ {17}}) = (17-1) \ cdot 17 ^ {k_ {17} -1} = (2 ^ 4) \ cdot 17 ^ {k_ {17} -1 }[/matemáticas]
[matemáticas] \ varphi (19 ^ {k_ {19}}) = (19-1) \ cdot 19 ^ {k_ {19} -1} = (2 ^ 2 \ cdot 3) \ cdot 19 ^ {k_ {19 } -1} [/ matemáticas]
[matemáticas] \ varphi (23 ^ {k_ {23}}) = (23-1) \ cdot 23 ^ {k_ {23} -1} = (2 \ cdot 11) \ cdot 23 ^ {k_ {23} – 1} [/ matemáticas]
[matemáticas] \ varphi (29 ^ {k_ {29}}) = (29-1) \ cdot 29 ^ {k_ {29} -1} = (2 ^ 2 \ cdot 7) \ cdot 29 ^ {k_ {29 } -1} [/ matemáticas]
[matemáticas] \ varphi (31 ^ {k_ {31}}) = (31-1) \ cdot 31 ^ {k_ {31} -1} [/ matemáticas] [matemáticas] = (2 \ cdot 3 \ cdot 5) \ cdot 31 ^ {k_ {31} -1} [/ matemáticas]
[matemáticas] \ varphi (37 ^ {k_ {37}}) = (37-1) \ cdot 37 ^ {k_ {37} -1} = (2 ^ 2 \ cdot 3 ^ 2) \ cdot 37 ^ {k_ {37} -1} [/ matemáticas]
[matemáticas] \ varphi (41 ^ {k_ {41}}) = (41-1) \ cdot 41 ^ {k_ {41} -1} = (2 ^ 3 \ cdot 5) \ cdot 41 ^ {k_ {41 } -1} [/ matemáticas]
[matemáticas] \ varphi (43 ^ {k_ {43}}) = (43-1) \ cdot 43 ^ {k_ {43} -1} [/ matemáticas] [matemáticas] = (2 \ cdot 3 \ cdot 7) \ cdot 43 ^ {k_ {43} -1} [/ matemáticas]
[matemáticas] \ varphi (47 ^ {k_ {47}}) = (47-1) \ cdot 47 ^ {k_ {47} -1} = (2 \ cdot 23) \ cdot 47 ^ {k_ {47} – 1} [/ matemáticas]
[matemáticas] \ varphi (53 ^ {k_ {53}}) = (53-1) \ cdot 53 ^ {k_ {53} -1} [/ matemáticas] [matemáticas] = (2 ^ 2 \ cdot 13) \ cdot 53 ^ {k_ {53} -1} [/ matemáticas]
Si p> 2, entonces (p-1) es par y aumenta [math] k_2 [/ math], y si p> 3, entonces (p-1) es compuesto y se factoriza en al menos dos primos más pequeños, sumando al menos 2 a la firma:
- p-1 tiene un factor de 2 si p> 2, porque un primo impar menos 1 es par
- p-1 tiene factores primos impares a menos que todos sus factores primos sean 2s, lo que implicaría que p es un número de Fermat [matemática] p = 2 ^ n + 1 [/ matemática]
- Los únicos primos Fermat conocidos son 3, 5, 17, 257, 65537, que aumentan [matemática] i_2 [/ matemática] en 1, 2, 4, 8 y 16 respectivamente.
Resumiendo la disminución en [math] k_p [/ math] y el aumento en primos más pequeños:
[matemáticas] \ Omega (\ varphi (2 ^ {k_2})) – \ Omega (2 ^ {k_2}) = -1 [/ matemáticas]
[matemáticas] \ Omega (\ varphi (3 ^ {k_3})) – \ Omega (3 ^ {k_3}) = 0 [/ matemáticas]
[matemáticas] \ Omega (\ varphi (p ^ {k_p})) – \ Omega (p ^ {k_p}) \ geq 1, p \ geq 5 [/ matemáticas]
[matemáticas] \ Omega (\ varphi (p ^ {k_p})) – \ Omega (p ^ {k_p}) \ geq 1, p \ geq 13, (p-1) [/ math] no Semiprime. (23-1, 47-1, 59-1 son semiprime).
Por lo tanto [matemáticas] \ Omega (\ varphi (2 ^ {k_2} \ cdot 3 ^ {k_3} \ cdot .. \ cdot p ^ {k_p})) – [/ matemáticas] [matemáticas] \ Omega (2 ^ {k_2 } \ cdot 3 ^ {k_3} \ cdot .. \ cdot p ^ {k_p}) [/ math] [math] \ geq 0 [/ math] a menos que solo [math] k_2> 0, k_3 \ geq 0, k_p = 0 [/ math] para todos los demás p
La tendencia de [math] \ phi [/ math] a introducir factores de 2 significa que a medida que i aumenta la multiplicidad de 2 en la factorización de [math] m_i [/ math] sucesivas tiende a disminuir; pero, por supuesto, no puede disminuir más allá de cero, lo que impone fuertes restricciones sobre qué secuencias pueden ser infinitamente Euler.
Poderes de 2: infinitamente Euler
[matemáticas] \ varphi (2 ^ i) = (2-1) \ cdot 2 ^ {i-1} = 2 ^ {i-1} [/ matemáticas]
Para [matemática] m_i = 2 ^ i, m_i = \ phi (m_ {i + 1}) [/ matemática], entonces las potencias de 2 son infinitamente Euler, incluidas las diez menores de 1000: [matemática] (1,2,4 , 8,16,32,64,128,256,512) [/ matemáticas].
Números impares: no
Como p-1 es par, [math] \ phi (p ^ i) [/ math] siempre contiene un factor de 2. Por ejemplo:
[matemáticas] \ varphi (3 ^ i) = (3-1) \ cdot 3 ^ {i-1} = 2 \ cdot 3 ^ {i-1} [/ math]
[matemáticas] \ varphi (5 ^ i) = (5-1) \ cdot 5 ^ {i-1} = 2 ^ 2 \ cdot 5 ^ {i-1} [/ math]
Por lo tanto, ninguna potencia de un primo impar (o cualquier número impar) puede ser un valor de [math] \ varphi [/ math], ya que no tiene un factor de 2. Si no puede ser Euler ni una sola vez, ciertamente no es infinitamente Euler
Productos de 2s y 3s: infinitamente Euler
[math] \ varphi [/ math] es multiplicativo, y calculamos [math] \ varphi [/ math] de cualquier número a través de su factorización prima, por ejemplo:
[matemáticas] \ varphi (2 ^ i \ cdot 3 ^ j) = 2 ^ {i-1} \ cdot 2 \ cdot 3 ^ {j-1} [/ matemáticas] [matemáticas] = 2 ^ i \ cdot 3 ^ {j-1} = (2 ^ i \ cdot 3 ^ j) / 3 [/ math]
Entonces, para cualquier [matemática] i \ geq 1 [/ matemática] fija, la secuencia [matemática] (m_j = 2 ^ i \ cdot 3 ^ j), m_j = \ varphi (m_ {j + 1}) [/ matemática] muestra que los productos de potencias positivas de 2 y 3 son infinitamente Euler, aunque las potencias puras de 3 no lo son.
Las primeras 8 de estas secuencias suman 24 números infinitamente más de Euler <1000, además de las 10 potencias de 2, que también encabezan las secuencias 2 × 3:
[matemáticas] 2 ^ 1 \ cdot 3 ^ j: (2,6,18,54,162,486, …) [/ matemáticas]
[matemáticas] 2 ^ 2 \ cdot 3 ^ j: (4,12,36,108,324,972, …) [/ matemáticas]
[matemáticas] 2 ^ 3 \ cdot 3 ^ j: (8.24,72,216,648, …) [/ matemáticas]
[matemáticas] 2 ^ 4 \ cdot 3 ^ j: (16,48,144,432, …) [/ matemáticas]
[matemáticas] 2 ^ 5 \ cdot 3 ^ j: (32,96,288,864, …) [/ matemáticas]
[matemáticas] 2 ^ 6 \ cdot 3 ^ j: (64,192,576, …) [/ matemáticas]
[matemáticas] 2 ^ 7 \ cdot 3 ^ j: (128,384, …) [/ matemáticas]
[matemáticas] 2 ^ 8 \ cdot 3 ^ j: (256,768, …) [/ matemáticas]
[matemáticas] 2 ^ 9 \ cdot 3 ^ j: (512, …) [/ matemáticas]
De hecho, estos 34 números son los únicos números de Euler infinitamente menores que 1000.
Productos de 2s y 5s: No, el exponente de 2 no puede disminuir indefinidamente
[matemáticas] \ varphi (2 ^ i \ cdot 5 ^ k) = 2 ^ {i-1} \ cdot 2 ^ 2 \ cdot 5 ^ {k-1} [/ matemáticas] [matemáticas] = 2 ^ {i + 1} \ cdot 5 ^ {k-1} = (2 ^ i \ cdot 5 ^ k) \ cdot 2/5 [/ matemática]
Entonces [math] \ varphi [/ math] disminuye el exponente de 5, pero incrementa el exponente de 2. Esto significa que aumentar m_i debe tener exponentes crecientes de 5, pero exponentes decrecientes de 2; sin embargo, el exponente de 2 solo puede disminuir un número finito de veces antes de llegar a cero. En este punto, [math] m_i [/ math] es una potencia pura de 5, que no puede ser [math] \ varphi [/ math] de ningún número como se muestra al principio, por lo que la secuencia termina y las secuencias de potencias de 2 y 5 no son infinitamente Euler.
Múltiples factores primos impares: no
Cada primo impar contribuye a un aumento de al menos un factor de 2. Dado que el exponente de 2 en sí mismo solo disminuye en 1, el número de factores de 2 también debe aumentar en este caso.
Nota: Más tarde encontré este problema enumerado en Problema de teoría de números, pero aún no he mirado las soluciones.