ArithmétiqueThéorème · Glossaire
théorème d'Euler - arithmétique -
Le théorème d'Euler en arithmétique, parfois appelé théorème de Fermat-Euler, est un résultat d'arithmétique modulaire publié par Euler en 1761 qui généralise le petit théorème de Fermat. Il énonce que si n est un entier naturel positif et a un entier premier avec n, alors : a^(φ(n)) ≡ 1 (mod n), où φ désigne la fonction indicatrice d'Euler (ou fonction phi d'Euler), qui compte le nombre d'entiers entre 1 et n premiers avec n. Lorsque n est un nombre premier p, on a φ(p) = p − 1, ce qui redonne le petit théorème de Fermat : a^(p − 1) ≡ 1 (mod p). Ce théorème est notamment utilisé en cryptographie. Il est lui-même généralisé par le théorème de Carmichael.
Sommaire
Ce que vous allez apprendre
- Formuler l’énoncé avec la condition de coprimalité et le rôle de la fonction φ.
- Calculer φ(10), vérifier que 3 puissance 4 laisse le reste 1, puis réduire 3 puissance 202 au reste 9 modulo 10.
- Détecter avec 2 modulo 10 un cas où l’hypothèse indispensable échoue.
- Distinguer le théorème d’Euler du petit théorème de Fermat.
- Comprendre pourquoi φ(n) est un exposant garanti sans être toujours minimal.
En clair
Prenons les puissances de 3 et ne gardons que leur reste après division par 10. Elles donnent successivement 3, 9, 7, puis 1. Ensuite, le même cycle recommence.
Le théorème d’Euler garantit ce retour à 1 parce que 3 et 10 n’ont aucun diviseur commun autre que 1. Pour savoir après combien de multiplications ce retour est assuré, on compte les entiers premiers avec 10 : 1, 3, 7 et 9. Il y en a quatre, donc la quatrième puissance de 3 laisse un reste égal à 1 modulo 10.
Définition
Le théorème d’Euler, aussi appelé théorème de Fermat-Euler, est un résultat d’arithmétique modulaire publié par Euler en 1761. Deux entiers a et n sont premiers entre eux lorsque leur plus grand diviseur commun vaut 1. La fonction indicatrice d’Euler, notée φ, associe à l’entier naturel positif n le nombre d’entiers compris entre 1 et n qui sont premiers avec n.
Sous la condition que a et n soient premiers entre eux, le théorème affirme que . Pour n ≥ 2, la congruence signifie que la division de aφ(n) par n laisse le reste 1 ; de façon équivalente dans tous les cas, n divise aφ(n) − 1.
Si n est un nombre premier p, tous les entiers de 1 à p − 1 sont premiers avec p, donc φ(p) = p − 1. L’énoncé devient alors le petit théorème de Fermat. Le théorème d’Euler est notamment utilisé en cryptographie et admet une généralisation par le théorème de Carmichael.
Le principe
Soit n un entier naturel positif et a un entier. Si a est premier avec n, c’est-à-dire si leur plus grand diviseur commun vaut 1, alors . Ici, φ(n) compte les entiers de 1 à n qui sont premiers avec n. Lorsque n est premier, φ(n) vaut n − 1 et l’énoncé se réduit au petit théorème de Fermat.
Quand l'utiliser
Le calcul se déroule dans l’arithmétique modulo un entier naturel positif n. Il faut connaître l’entier a, calculer φ(n), puis vérifier que le plus grand diviseur commun de a et n vaut 1. La conclusion est alors que aφ(n) est congru à 1 modulo n.
La condition de coprimalité ne peut pas être omise. Avec a = 2 et n = 10, le plus grand diviseur commun vaut 2. Bien que φ(10) = 4, on obtient 24 = 16, donc un reste de 6 et non de 1 modulo 10. Dans ce contre-cas, le théorème d’Euler ne s’applique pas ; il faut calculer directement les restes ou employer un résultat adapté.
Un exemple, pas à pas
Données. On cherche le reste de 34 après division par 10. Le module est n = 10 et la base est a = 3.
1. Les entiers de 1 à 10 premiers avec 10 sont 1, 3, 7 et 9. Il y en a quatre, donc φ(10) = 4.
2. Le plus grand diviseur commun de 3 et 10 vaut 1. L’hypothèse du théorème d’Euler est satisfaite.
3. Le théorème donne directement . Le reste recherché est donc 1.
4. Les restes successifs sont 3, 9, 7 et 1. Leur cycle rend visible le retour garanti par l’exposant φ(10).
Contrôle. Le calcul ordinaire confirme que 34 = 81 = 8 × 10 + 1. La division par 10 laisse bien le reste 1.
En pratique
Pour réduire une grande puissance modulo n, on vérifie d’abord que la base est première avec n. Par exemple, le plus grand diviseur commun de 3 et 10 vaut 1, et φ(10) = 4. Comme 202 = 50 × 4 + 2, on obtient 3202 = (34)50 × 32 ≡ 150 × 9 ≡ 9 modulo 10. Le cycle des restes 3, 9, 7, 1 confirme ce résultat : 202 laisse le même reste que 2 après division par 4, donc 3202 laisse le reste 9 modulo 10. Si la coprimalité échoue, il faut étudier directement la suite des restes.
En cryptographie, le théorème relie certaines puissances calculées modulo n à un retour au reste 1. Avant de l’invoquer, le contrôle décisif reste le plus grand diviseur commun entre la base et le module.
Lorsque le module est un nombre premier p, la valeur φ(p) = p − 1 est immédiate : le petit théorème de Fermat fournit alors la forme la plus directe. Pour un module composé comme 10, la version d’Euler est celle qui convient.
À ne pas confondre
Avec le petit théorème de Fermat. Celui-ci suppose que le module p est premier et utilise l’exposant p − 1. Le théorème d’Euler accepte aussi un module composé, mais exige que la base soit première avec lui et utilise φ(n). Pour le module composé 10 et la base 3, c’est donc la version d’Euler qui s’applique.
Limites et pièges
Base non première avec le module. Si le plus grand diviseur commun n’est pas 1, la conclusion peut échouer. Pour 2 et 10, l’exposant φ(10) = 4 donne 24 ≡ 6 modulo 10. Il faut alors abandonner cette application du théorème et calculer les restes autrement.
Exposant garanti, pas forcément minimal. Le nombre φ(n) fournit un exposant qui rend toute base admissible congrue à 1 modulo n, mais cette congruence peut survenir plus tôt. Ainsi, 92 = 81 ≡ 1 modulo 10, alors que φ(10) = 4. Il faut étudier le cycle si l’on cherche le plus petit exposant.
Cas premier. Si le module est premier p, utiliser φ(p) = p − 1 ne constitue pas un autre théorème concurrent : on retrouve exactement le petit théorème de Fermat. Pour un module composé, remplacer φ(n) par n − 1 sans justification donne en général un exposant erroné.
Pour aller plus loin
Indicatrice (fonction) — Détaille le calcul de φ(n), l’exposant central du théorème d’Euler.
congruence modulo n — Précise comment lire et manipuler l’égalité de restes utilisée dans l’énoncé.
petit théorème de Fermat — Approfondit le cas particulier où le module est un nombre premier.
Une histoire de l'arithmétique modulaire — Replace les congruences et leurs usages dans leur développement historique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres