Calculateur d’ordre multiplicatif modulo n

Saisissez une base entière a et un module n : le résultat indique la base réduite, l’indicatrice d’Euler, l’ordre et une vérification modulaire directe. Le calcul n’est défini que si a et n sont premiers entre eux ; une paire non valide produit donc un message d’erreur clair plutôt qu’un nombre trompeur. Cet outil convient aux exercices d’arithmétique modulaire, à l’étude des sous-groupes cycliques, aux motifs périodiques et à la théorie élémentaire des nombres.

Comprendre l’ordre multiplicatif

Pour deux entiers a et n, l’ordre multiplicatif de a modulo n est le plus petit entier positif k tel que a^k laisse un reste égal à 1 lors de la division par n. La précision « plus petit positif » est essentielle : des exposants ultérieurs peuvent eux aussi donner 1, mais l’ordre désigne le premier retour à l’élément neutre de la multiplication modulaire. Ainsi, les puissances de 2 modulo 9 donnent successivement les restes 2, 4, 8, 7, 5, puis 1 ; l’ordre vaut donc 6. Cette notion décrit la taille du sous-groupe cyclique engendré par a parmi les classes inversibles modulo n. Avant tout calcul, l’outil ramène a à son représentant non négatif usuel. Les bases négatives ou supérieures à n sont ainsi traitées de manière cohérente. Il fournit également une valeur de contrôle calculée à partir de l’ordre annoncé. Une valeur égale à 1 confirme la congruence recherchée, tandis que la réduction du candidat garantit qu’aucun diviseur propre restant de l’exposant ne peut encore la vérifier.

Pourquoi les deux entiers doivent être premiers entre eux

L’ordre multiplicatif modulo n n’existe que lorsque gcd(a, n) vaut 1. Il ne s’agit pas d’une simple convention de saisie. Un élément doit posséder un inverse multiplicatif modulo n pour que ses puissances appartiennent au groupe fini des unités et puissent revenir à 1. Si a et n ont un facteur commun, toute puissance positive de a conserve une obstruction de divisibilité compatible et ne peut pas être congrue à 1 modulo n. Le calculateur vérifie immédiatement cette condition et affiche le plus grand commun diviseur effectif lorsqu’elle n’est pas satisfaite. Le module doit également être au moins égal à 2, car le problème usuel de l’ordre se pose dans un système de résidus non trivial. La base peut être nulle, négative ou positive dans la limite publiée ; toutefois, zéro échoue pour tout module autorisé puisqu’il n’est jamais premier avec n. Pour préparer la saisie, utilisez des entiers exacts et non des décimaux ou des approximations scientifiques. Vous préservez ainsi l’arithmétique discrète dont dépendent le pgcd, la factorisation et les puissances modulaires.

Comment le plus petit exposant est déterminé

Le calculateur ne parcourt pas tous les exposants l’un après l’autre. Il factorise d’abord n autant que nécessaire pour calculer l’indicatrice d’Euler phi(n). Le théorème d’Euler garantit que a élevé à phi(n) est congru à 1 dès que gcd(a, n) vaut 1 ; l’ordre recherché divise donc nécessairement phi(n). L’algorithme factorise ensuite phi(n), puis vérifie de façon répétée si la division du candidat courant par l’un de ses facteurs premiers donne encore une puissance modulaire égale à 1. Dans ce cas, le candidat réduit remplace le précédent. Dès qu’aucun facteur premier ne peut plus être retiré, le candidat restant est l’ordre multiplicatif. L’exponentiation modulaire repose sur les carrés successifs et maintient les valeurs intermédiaires réduites modulo n ; tous les calculs entiers restent exacts. Cette méthode est nettement plus rapide qu’un examen de chaque exposant positif, surtout lorsque l’ordre est élevé. Les entrées sont plafonnées à mille milliards afin que la division d’essai conserve une limite déterministe claire, adaptée aussi bien à l’outil dans le navigateur qu’aux appels API automatisés.