Inverse modulaire par Fermat
Effectuer une division sûre sous un modulo
Inverse modulaire par Fermat est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
La division échoue avec un modulo
L’addition, la soustraction et la multiplication se comportent correctement avec un modulo, mais la division ordinaire ne fonctionne pas ainsi. Vous ne pouvez pas simplement diviser puis prendre le reste. ⚠️
Remplacer la division par une multiplication
La solution est l’inverse modulaire : diviser par x revient à multiplier par l’inverse de x. Ainsi, a / b modulo m devient a multiplié par l’inverse de b.
Qu’est-ce qu’un inverse ?
L’inverse de x est le nombre qui donne 1 lorsqu’il est multiplié par x avec le modulo. Il joue le rôle de 1/x dans l’arithmétique ordinaire.
# x * inv(x) % m == 1Les nombres premiers rendent cela possible
Un inverse existe uniquement si x ne partage aucun facteur avec m. Utiliser un modulo premier comme 1e9+7 garantit que tout x non nul en possède un.
Le petit théorème de Fermat
Le petit théorème de Fermat affirme que, pour un nombre premier p, x élevé à la puissance p - 1 est congru à 1, tant que x n’est pas un multiple de p.
# x^(p-1) % p == 1Déduire l’inverse
En isolant un facteur x, le reste doit être son inverse. Ainsi, l’inverse de x est x élevé à la puissance p - 2, le tout modulo p.
# inv(x) = x^(p-2) % pLe calculer avec l’exponentiation rapide
Cet exposant est très grand : utilisez donc l’exponentiation rapide de la leçon précédente. En Python, un seul appel à pow effectue tout le calcul pour vous.
inv = pow(x, MOD - 2, MOD)L’utiliser pour diviser
Pour calculer a divisé par b avec un modulo, multipliez a par l’inverse de b. Le reste est exactement le vrai quotient modulo p.
ans = a * pow(b, MOD - 2, MOD) % MODNe jamais inverser zéro
0 n’a pas d’inverse, car aucun nombre multiplié par zéro ne donne un. Empêchez toute division par une valeur qui se réduit à zéro avec le modulo.
Coût d’un inverse
Chaque inverse de Fermat est une exponentiation rapide : son coût est donc de O(log p). C’est peu coûteux pour quelques divisions, mais cela finit par compter si vous en effectuez des millions.
Astuce pour les inverses par lots
Lorsque vous avez besoin de nombreux inverses, précalculez-les en un seul passage linéaire astucieux au lieu d’appeler pow pour chaque élément. Vous vous appuierez sur cette méthode pour calculer nCr ensuite.
Vérification rapide
Quelle puissance donne l’inverse modulaire avec un nombre premier ?
Récapitulatif
Vous savez maintenant effectuer une division avec un modulo premier en multipliant par l’inverse modulaire, obtenu sous la forme x élevé à la puissance p - 2 grâce à pow. N’inversez simplement jamais zéro. ✅
Questions Fréquemment Posées
La leçon « Inverse modulaire par Fermat » est-elle gratuite ?
Oui — le texte complet de « Inverse modulaire par Fermat » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Inverse modulaire par Fermat » ?
Effectuer une division sûre sous un modulo Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Inverse modulaire par Fermat » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Calculer modulo un nombre premier
- Exponentiation modulaire rapide
- Inverse modulaire par Fermat
- nCr avec des factorielles précalculées