Editar: Trabajando en mi látex 🙂
Hay varias cosas que entender aquí. ¡Vamos paso a paso!
Hecho 1:
P. ¿Qué es el inverso multiplicativo modular?
- ¿Cuáles son algunas ideas interesantes para proyectos en teoría de números computacional?
- ¿Cuáles son algunos buenos recursos para la teoría de números computacionales?
- ¿Cuántos divisores de 20 ^ 14 son cuadrados perfectos?
- ¿Qué trucos / teoremas de matemáticas hay para ayudarme a resolver problemas avanzados de la Olimpiada de Matemáticas (por ejemplo, el pequeño teorema de Fermat)?
- Cómo encontrar el valor de m de tal manera que las raíces de la ecuación [matemáticas] x ^ 4 – (3m + 2) x ^ 2 + m ^ 2 = 0 [/ matemáticas] estén en progresión aritmética
escribimos [matemáticas] A * A ^ {- 1} \ equiv 1 (mod \ m) [/ matemáticas] para significar A multiplicado por el inverso multiplicativo modular de A módulo m da un resto 1 cuando se divide por m.
parece mucha jerga, ¿no?
Vamos a desglosarlo aún más. El inverso multiplicativo modular de A módulo m es un número que depende de 2 cantidades: A y m. Entonces, podemos preguntar cuál es el inverso multiplicativo modular de 5 módulo 7.
Llamémoslo x. Entonces x es el número que cuando se multiplica por A, da un resto de 1, cuando se divide por m.
entonces el número 3 puede ser un inverso multiplicativo modular de 5 módulo 7, porque 5 * 3 = 15 da el resto 1 cuando se divide por 7.
De hecho, aparte de solo 3, todos los números 3 + 7, 3 + 7 * 2, 3 + 7 * k … son también inversos multiplicativos modulares de 5 módulo 7.
Ahora que obtenemos lo que entendemos por inversa multiplicativa modular, pasemos al hecho 2.
Hecho 2:
En aritmética modular, la siguiente identidad es válida
if [matemáticas] A \ equiv r [/ matemáticas] (mod m)
y [matemáticas] B \ equiv q [/ matemáticas] (mod m)
entonces tenemos [matemáticas] A * B \ equiv r * q [/ matemáticas] (mod m)
Armados con los dos hechos anteriores, ahora podemos ver cómo el inverso multiplicativo modular ayuda a calcular [matemáticas] \ binom {N} {r} [/ matemáticas] (mod m).
Necesitamos encontrar x en la siguiente ecuación.
[matemáticas] \ binom {N} {r} \ equiv [/ matemáticas] x (mod m)
o x en la siguiente ecuación.
[matemáticas] \ frac {n * (n-1) *… (n-r + 1)} {r * (r-1) *… * 1} \ equiv [/ matemáticas] x (mod m) (ecuación 1 )
sabemos que las siguientes ecuaciones son válidas a partir de la definición del inverso multiplicativo modular.
[matemáticas] r * (r) ^ {- 1} \ equiv [/ matemáticas] 1 (mod m)
[matemáticas] (r-1) * (r-1) ^ {- 1} \ equiv [/ matemáticas] 1 (mod m)
.
.
[matemáticas] 2 * (2) ^ {- 1} \ equiv [/ matemáticas] 1 (mod m)
Multiplicando todo lo anterior y usando el hecho 2, tenemos
[matemáticas] r * (r) ^ {- 1} * (r-1) * (r-1) ^ {- 1} *… * 2 * 2 ^ {- 1} \ equiv [/ matemáticas] 1 (mod m) (ecuación 2)
Nuevamente multiplicando (ecuación 1) y (ecuación 2) y usando el hecho 2, tenemos
[matemáticas] \ frac {n * .. * (n-r + 1) * r * (r) ^ {- 1} * .. 2 * 2 ^ {- 1}} {r * (r-1) * … * 1} \ equiv [/ matemáticas] x * 1 (mod m)
Podemos cancelar el denominador del LHS y lo que queda es solo
[matemáticas] n *. * (n-r + 1) * (r) ^ {- 1} * (r-1) ^ {- 1} *. * 2 ^ {- 1} \ equiv [/ matemáticas] x (mod m)
Espero que ahora puedan ver exactamente cómo la inversa multiplicativa modular ayuda a calcular [matemáticas] \ binom {n} {r} [/ matemáticas] (mod m)
Si quedan dudas, por favor pregunte! 🙂