Calculateur du théorème d’Euler

Q: Comment appliquer le théorème d’Euler à la main ?

Vérifiez d’abord que gcd(a, n) = 1. Comptez ensuite les entiers de 1 à n qui n’ont aucun facteur commun avec n : ce nombre est phi(n). Enfin, calculez a^phi(n) et divisez-le par n ; le reste sera 1. Par exemple, pour a = 5 et n = 12, les entiers premiers avec 12 sont 1, 5, 7 et 11. Ainsi, phi(12) = 4 et 5^4 = 625 = 52 × 12 + 1.

Q: Comment calculer rapidement l’indicatrice d’Euler φ(n) pour de grands nombres ?

Compter les entiers premiers avec n un par un ne convient qu’aux petits n. Si vous connaissez sa décomposition en facteurs premiers, utilisez la formule phi(n) = n prod_p mid n (1 - tfrac1p). Par exemple, n = 36 = 2^2 · 3^2, donc phi(36) = 36 · tfrac12 · tfrac23 = 12. Si n est premier, phi(n) = n - 1, sans avoir besoin de le factoriser.

Q: Le résultat peut-il être différent de 1 ?

Non : dès lors que gcd(a, n) = 1 et n > 1, le résultat est nécessairement égal à 1. C’est précisément ce qu’affirme le théorème. Si vous obtenez une autre valeur, les nombres saisis ne respectent pas les conditions, le plus souvent parce qu’ils ont un facteur commun non détecté. Si vous souhaitez calculer a^k bmod n pour un exposant k de votre choix, réduisez d’abord k modulo phi(n), puis utilisez un outil d’exponentiation modulaire.

Q: Quel est le plus petit exposant qui donne 1, et quel est son lien avec φ(n) ?

Le plus petit exposant positif k tel que a^k equiv 1 ±odn s’appelle l’ordre multiplicatif de a modulo n. Le théorème d’Euler garantit que cet ordre existe et qu’il divise toujours phi(n), mais il est souvent plus petit. Par exemple, phi(7) = 6, alors que l’ordre de 2 modulo 7 n’est que de 3, puisque 2^3 = 8 equiv 1 ±od7.

Mis à jour : 03.10.2026

Appliquez le théorème d’Euler en ligne : saisissez une base a et un module n premiers entre eux. Le calculateur détermine l’indicatrice d’Euler φ(n) et a^φ(n) mod n, qui vaut toujours 1 lorsque les conditions du théorème sont remplies.

Calculer des puissances modulaires avec le théorème d’Euler

Formule du théorème d’Euler

Formule

\[ \text{Si } \gcd(a, n) = 1, \quad \text{alors } a^{\phi(n)} \equiv 1 \pmod{n} \]

Où :

\(a\) — la base, un entier premier avec \(n\)
\(n\) — le module, un entier positif
\(\phi(n)\) — l’indicatrice d’Euler : le nombre d’entiers de \(1\) à \(n\) qui sont premiers avec \(n\)
\(\equiv 1 \pmod{n}\) — les deux membres donnent le même reste, \(1\), lorsqu’on les divise par \(n\)

Le théorème affirme que, lorsque \(a\) et \(n\) n’ont aucun facteur commun autre que 1, élever \(a\) à la puissance \(\phi(n)\) donne toujours \(1\) modulo \(n\). Il permet ainsi de ramener de très grands exposants à des exposants beaucoup plus petits en arithmétique modulaire.

Théorème d’Euler : exemple de calcul

Exemple : vérifions le théorème d’Euler pour \(a = 3\) et \(n = 7\) (les valeurs par défaut du calculateur).

Étape 1 : vérifier que \(a\) et \(n\) sont premiers entre eux :

\[ \gcd(3, 7) = 1 \quad \checkmark \]

Étape 2 : calculer l’indicatrice de \(n\). Les nombres premiers avec \(7\) parmi \(1, 2, \dots, 6\) sont au nombre de six, donc :

\[ \phi(7) = 6 \]

Étape 3 : élever la base à cette puissance, puis calculer le reste :

\[ 3^{6} = 729 \equiv 1 \pmod{7} \]

Résultat : \(a^{\phi(n)} \bmod n = 1\), exactement comme le prédit le théorème d’Euler.

Comment utiliser le calculateur

Saisissez la base entière \(a\) dans le champ Base (a).
Saisissez le module \(n\) dans le champ Module (n). Choisissez une valeur supérieure à 1 pour obtenir un résultat significatif.
Consultez les deux résultats : Indicatrice d’Euler φ(n) indique combien de nombres inférieurs à \(n\) sont premiers avec lui, et a^φ(n) mod n donne le résultat de l’exponentiation modulaire.
Si le message « a et n doivent être premiers entre eux » apparaît, choisissez une autre paire : le théorème d’Euler ne s’applique pas lorsque \(\gcd(a, n) > 1\).

Qu’est-ce que le théorème d’Euler ?

Le théorème d’Euler, énoncé par Leonhard Euler en 1763, est l’un des résultats fondamentaux de la théorie des nombres. Il affirme que, si un entier \(a\) n’a aucun diviseur commun avec \(n\) autre que 1, alors \(a^{\phi(n)}\) donne un reste de \(1\) lorsqu’on le divise par \(n\). La quantité essentielle ici est l’indicatrice d’Euler \(\phi(n)\), qui compte les entiers entre \(1\) et \(n\) premiers avec \(n\). Si \(p\) est premier, tous les nombres de \(1\) à \(p-1\) remplissent cette condition, donc \(\phi(p) = p - 1\).

Ce théorème généralise le petit théorème de Fermat : en prenant pour module un nombre premier \(n = p\), on obtient \(a^{p-1} \equiv 1 \pmod{p}\), ce qui correspond exactement à l’énoncé de Fermat. La version d’Euler, en revanche, s’applique à tout module, premier ou composé, à condition que la base et le module soient premiers entre eux.

En pratique, ce théorème est un puissant raccourci de calcul. Pour calculer une expression comme \(a^{k} \bmod n\) avec un exposant \(k\) très grand, on peut remplacer \(k\) par \(k \bmod \phi(n)\), car les puissances se répètent avec une période de \(\phi(n)\). Cette réduction permet à l’exponentiation modulaire de rester rapide même avec de très grands nombres, une propriété dont dépend la cryptographie moderne.

Le théorème d’Euler est en effet l’un des fondements du chiffrement RSA. L’exposant de déchiffrement (privé) est choisi de sorte que \(e \cdot d \equiv 1 \pmod{\phi(n)}\), ce qui garantit qu’élever un texte chiffré à la puissance \(d\) permet de retrouver le message original. Sans le théorème d’Euler, on ne pourrait pas démontrer que RSA fonctionne correctement.

Conditions, limites et conseils

Les nombres doivent être premiers entre eux. Le théorème n’est valable que si \(\gcd(a, n) = 1\). Le calculateur vérifie cette condition et affiche un message d’erreur si elle n’est pas remplie. Par exemple, \(a = 4\) et \(n = 6\) ne conviennent pas, car tous deux sont divisibles par 2.
Le module doit être au moins égal à 2. Avec \(n = 1\), tout entier est congru à \(0\), ce qui rend l’énoncé sans intérêt. Saisissez \(n > 1\).
Le résultat est toujours 1. Lorsque les conditions sont remplies, \(a^{\phi(n)} \bmod n = 1\) par définition : le calculateur sert à vérifier le théorème et à le comprendre. Pour simplifier une expression avec un autre exposant, réduisez d’abord celui-ci modulo \(\phi(n)\), puis utilisez l’exponentiation modulaire rapide.
Calcul de \(\phi(n)\). Ce calculateur compte directement les entiers premiers avec \(n\), ce qui convient aux petits modules. Pour un grand \(n\) dont la décomposition en facteurs premiers est connue, utilisez plutôt \(\phi(n) = n \prod_{p \mid n} \left(1 - \tfrac{1}{p}\right)\).
Outils associés. Pour trouver le nombre qui permet d’« annuler » une multiplication par \(a\) modulo \(n\), utilisez le calculateur d’inverse multiplicatif modulo ; pour résoudre des systèmes de congruences, consultez le calculateur du théorème des restes chinois.

Questions fréquentes

Comment appliquer le théorème d’Euler à la main ?

Vérifiez d’abord que \(\gcd(a, n) = 1\). Comptez ensuite les entiers de 1 à \(n\) qui n’ont aucun facteur commun avec \(n\) : ce nombre est \(\phi(n)\). Enfin, calculez \(a^{\phi(n)}\) et divisez-le par \(n\) ; le reste sera 1. Par exemple, pour \(a = 5\) et \(n = 12\), les entiers premiers avec 12 sont 1, 5, 7 et 11. Ainsi, \(\phi(12) = 4\) et \(5^4 = 625 = 52 \times 12 + 1\).

Pourquoi le calculateur affiche-t-il une erreur pour certaines valeurs ?

L’erreur apparaît lorsque la base et le module ne sont pas premiers entre eux, c’est-à-dire lorsque \(\gcd(a, n) > 1\). Par exemple, \(a = 6\) et \(n = 9\) sont tous deux divisibles par 3 : le théorème d’Euler ne s’applique donc pas à cette paire. Changez la base ou choisissez un autre module. Vérifiez aussi que \(n > 1\), car avec \(n = 1\), l’énoncé perd son intérêt.

Comment calculer rapidement l’indicatrice d’Euler φ(n) pour de grands nombres ?

Compter les entiers premiers avec \(n\) un par un ne convient qu’aux petits \(n\). Si vous connaissez sa décomposition en facteurs premiers, utilisez la formule \(\phi(n) = n \prod_{p \mid n} \left(1 - \tfrac{1}{p}\right)\). Par exemple, \(n = 36 = 2^2 \cdot 3^2\), donc \(\phi(36) = 36 \cdot \tfrac{1}{2} \cdot \tfrac{2}{3} = 12\). Si \(n\) est premier, \(\phi(n) = n - 1\), sans avoir besoin de le factoriser.

Quelle est la différence entre le théorème d’Euler et le petit théorème de Fermat ?

Le petit théorème de Fermat est le cas particulier du théorème d’Euler où le module est premier : \(a^{p-1} \equiv 1 \pmod{p}\). En 1763, Euler l’a généralisé à tout module \(n\), premier ou composé, en remplaçant l’exposant \(p-1\) par \(\phi(n)\). Sa version couvre donc des cas comme \(n = 15\) ou \(n = 100\), auxquels l’énoncé original de Fermat ne s’applique pas.

Le résultat peut-il être différent de 1 ?

Non : dès lors que \(\gcd(a, n) = 1\) et \(n > 1\), le résultat est nécessairement égal à 1. C’est précisément ce qu’affirme le théorème. Si vous obtenez une autre valeur, les nombres saisis ne respectent pas les conditions, le plus souvent parce qu’ils ont un facteur commun non détecté. Si vous souhaitez calculer \(a^k \bmod n\) pour un exposant \(k\) de votre choix, réduisez d’abord \(k\) modulo \(\phi(n)\), puis utilisez un outil d’exponentiation modulaire.

À quoi sert le théorème d’Euler dans la pratique ?

Son application la plus connue est le chiffrement RSA. Une clé privée RSA \(d\) est choisie de sorte que \(e \cdot d \equiv 1 \pmod{\phi(n)}\), et le théorème d’Euler garantit que le déchiffrement d’un texte chiffré permet de retrouver le message original. La même technique de réduction de l’exposant, \(a^k \equiv a^{k \bmod \phi(n)} \pmod{n}\), permet aussi d’effectuer rapidement des calculs modulaires sur de très grands nombres en cryptographie et en informatique.

Quel est le plus petit exposant qui donne 1, et quel est son lien avec φ(n) ?

Le plus petit exposant positif \(k\) tel que \(a^k \equiv 1 \pmod{n}\) s’appelle l’ordre multiplicatif de \(a\) modulo \(n\). Le théorème d’Euler garantit que cet ordre existe et qu’il divise toujours \(\phi(n)\), mais il est souvent plus petit. Par exemple, \(\phi(7) = 6\), alors que l’ordre de \(2\) modulo 7 n’est que de 3, puisque \(2^3 = 8 \equiv 1 \pmod{7}\).