Este es uno de los problemas que más disfruté resolver, ¡ya que me hizo aprender bastantes cosas!
Primero, permítanme mencionar que no tengo un fondo adecuado de teoría de números. Lo que sé proviene de una clase básica de matemáticas discretas y de autoaprendizaje. Entonces, mi solución puede ser más compleja de lo necesario.
Problema
Dados tres enteros abn , [matemática] 1 \ le a, b, n \ leq 10 ^ 5 [/ matemática], calcula [matemática] a ^ {(b ^ {f (n)})} \ mod 1 \, 000 \, 000 \, 007 [/ math], donde [math] f (n) = \ binom {n} {0} ^ 2 + \ binom {n} {1} ^ 2 + \ dots + \ binom {n} {n} ^ 2 [/ matemáticas].
- ¿Qué es [math] -12 \ bmod 5 [/ math]?
- ¿Qué son los enteros [math] p [/ math] -adic? ¿Cómo funcionan y qué problemas podemos resolver usándolos?
- ¿Cómo debo entender la definición de números de repunidad?
- Si tomo un número que no es divisible por 7, y sigo agregando 7 como un dígito al final, ¿terminaré necesariamente encontrando un primo?
- ¿Cuántas soluciones enteras no triviales existen para [matemáticas] x ^ 3 – y ^ 2 = z ^ 5 [/ matemáticas]?
Tratar con f (n)
La función f complica la expresión, pero podemos notar que [math] f (n) = \ binom {2n} {n} [/ math]. Es fácil encontrar pruebas en línea, por ejemplo, aquí, así que me saltearé eso. Esto simplifica nuestra expresión a [matemáticas] a ^ {(b ^ {\ binom {2n} {n}})} [/ matemáticas].
Reduciendo los exponentes
[math] b ^ {\ binom {2n} {n}} [/ math] es un número enorme y debemos reducirlo a un número más manejable.
El teorema de Euler establece que si a y m son números coprimos , entonces [math] a ^ {\ phi (m)} = 1 \ mod m [/ math], donde [math] \ phi (m) [/ math] es el totient de Euler función. Esto es útil porque [matemática] a ^ y \ equiv a ^ {(y \ mod \ phi (m))} (\ mod m) [/ math] (la repetida [math] \ phi (m) [/ math] factores en el exponente producirán un montón de 1s).
[matemática] m = 10 ^ 9 + 7 [/ matemática] que es un número primo, entonces [matemática] \ phi (m) = m-1 = 10 ^ 9 + 6 = 2 \ por 500 \, 000 \, 003 [/matemáticas].
Entonces, tenemos [math] a ^ {y \ mod 1 \, 000 \, 000 \, 006} \ mod 1 \, 000 \, 000 \, 007 [/ math].
La principal dificultad de este problema es que nuestra y también es exponencial, [matemática] y = b ^ {\ binom {2n} {n}} [/ matemática]. Para encontrar el resultado, primero necesitamos calcular [matemáticas] b ^ {\ binom {2n} {n}} \ mod 1 \, 000 \, 000 \, 006 [/ matemáticas].
Encontrar [matemáticas] b ^ {\ binom {2n} {n}} \ mod 1 \, 000 \, 000 \, 006 [/ matemáticas] cuando b es impar
Supongamos que b es impar. Entonces, podemos aplicar el teorema de Euler porque b y 1,000,000,006 son números coprimos (recuerde que [math] b \ leq 10 ^ 5 [/ math] por lo que el factor [math] 500 \, 000 \, 003 [/ math] siempre será coprime con b ).
[matemáticas] b ^ {\ binom {2n} {n}} \ equiv b ^ {\ binom {2n} {n} \ mod \ phi (1 \, 000 \, 000 \, 006)} \ mod 1 \, 000 \, 000 \, 006 [/ matemáticas].
[matemáticas] \ phi (1 \, 000 \, 000 \, 006) = \ phi (2) \ times \ phi (500 \, 000 \, 003) = (2 – 1) \ times (500 \, 000 \ , 003 – 1) = 500 \, 000 \, 002 [/ matemáticas].
[matemáticas] 500 \, 000 \, 002 = 2 \ veces 41 ^ 2 \ veces 148721 [/ matemáticas].
Entonces, necesitamos encontrar [math] \ binom {2n} {n} \ mod 500 \, 000 \, 002 [/ math] que no es primo. Por lo tanto, necesitamos usar otra herramienta: el Teorema del resto chino (CRT). Podemos calcular
[matemáticas] \ begin {cases} \ binom {2n} {n} \ mod 2 \\ \ binom {2n} {n} \ mod 41 ^ 2 \\ \ binom {2n} {n} \ mod 148721 \ end { casos} [/ matemáticas]
y use CRT para obtener el módulo de resultado [math] 500 \, 000 \, 002 [/ math].
Encontrar [matemáticas] b ^ {\ binom {2n} {n}} \ mod 1 \, 000 \, 000 \, 006 [/ matemáticas] cuando b es par
Lamentablemente, si b es par, by [matemáticas] 1 \, 000 \, 000 \, 006 [/ matemáticas] no son números coprimos.
Por lo tanto, necesitamos CRT nuevamente. Nuestro módulo es el producto de dos números primos: 2 y 500,000,003. Entonces, encontraremos [math] b ^ {\ binom {2n} {n}} [/ math] módulo 2 y 500,000,003 y usaremos CRT para obtener el módulo de resultado 1,000,000,006.
Tenga en cuenta que cuando b es par el resultado, el módulo 2 siempre es 0. Entonces, solo necesitamos calcular el módulo de resultado [math] 500 \, 000 \, 003 [/ math] y [math] \ phi (500 \, 000 \ , 003) = \ phi (1 \, 000 \, 000 \, 006) [/ math], por lo que esta parte es igual al caso cuando b es impar. La única diferencia es usar CRT.
Agregando todo junto
Después de encontrar [matemáticas] y = b ^ {\ binom {2n} {n}} \ mod 1 \, 000 \, 000 \, 006 [/ matemáticas], podemos calcular [matemáticas] a ^ y \ mod 1 \, 000 \, 000 \, 007 [/ math] normalmente para obtener el resultado final.