Inverso modular mediante Fermat
Divida de forma segura bajo un módulo
Inverso modular mediante Fermat es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
La división falla con el módulo
La suma, la resta y la multiplicación se comportan bien bajo un módulo, pero la división normal no. No puede limitarse a dividir y tomar el resto. ⚠️
Sustituya la división por una multiplicación
La solución es el inverso modular: dividir entre x se convierte en multiplicar por el inverso de x. Por tanto, a / b módulo m se transforma en a multiplicado por el inverso de b.
Qué es un inverso
El inverso de x es el número que, al multiplicarse por x bajo el módulo, produce 1. Desempeña el papel de 1/x en la aritmética ordinaria.
# x * inv(x) % m == 1Los primos lo hacen posible
Existe un inverso únicamente cuando x no comparte ningún factor con m. Usar un módulo primo como 1e9+7 garantiza que todo x distinto de cero tiene uno.
Entra en escena el pequeño teorema de Fermat
El pequeño teorema de Fermat afirma que, para un primo p, x elevado a p menos 1 es congruente con 1, siempre que x no sea múltiplo de p.
# x^(p-1) % p == 1Deduzca el inverso
Separe un factor x y el resto debe ser su inverso. Por tanto, el inverso de x es x elevado a p menos 2, tomando el módulo p.
# inv(x) = x^(p-2) % pCalcúlelo con exponenciación rápida
Ese exponente es enorme, así que use la exponenciación rápida de la lección anterior. En Python, una sola llamada a pow hace todo el trabajo.
inv = pow(x, MOD - 2, MOD)Úselo para dividir
Para calcular a dividido entre b bajo el módulo, multiplique a por el inverso de b. El resto es exactamente el cociente verdadero módulo p.
ans = a * pow(b, MOD - 2, MOD) % MODNunca invierta cero
No existe el inverso de 0, porque ningún número multiplicado por cero da uno. Evite dividir entre un valor que se reduzca a cero bajo el módulo.
Coste de un inverso
Cada inverso mediante Fermat requiere una exponenciación rápida, por lo que cuesta O(log p) tiempo. Es barato para unas pocas divisiones, pero el coste se acumula si realiza millones.
Una pista sobre los inversos por lotes
Cuando necesite muchos inversos, precalcúlelos con un recorrido lineal inteligente en lugar de usar un pow por elemento. Lo necesitará para nCr a continuación.
Comprobación rápida
¿Qué potencia proporciona el inverso modular bajo un primo?
Resumen
Ahora puede dividir bajo un módulo primo multiplicando por el inverso modular, obtenido como x elevado a p menos 2 mediante pow. Solo recuerde no invertir cero. ✅
Preguntas frecuentes
¿La lección «Inverso modular mediante Fermat» es gratis?
Sí — el texto completo de «Inverso modular mediante Fermat» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Inverso modular mediante Fermat»?
Divida de forma segura bajo un módulo Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Inverso modular mediante Fermat»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Trabaje módulo un primo
- Exponenciación modular rápida
- Inverso modular mediante Fermat
- nCr con factoriales precalculados