ArithmétiqueNotion · Glossaire
indicateur d'Euler
La fonction indicatrice d'Euler, notée φ (phi), est définie sur l'ensemble des entiers strictement positifs. Pour tout entier n ≥ 1, φ(n) désigne le nombre d'entiers compris entre 1 et n qui sont premiers avec n. Par exemple, φ(6) = 2 car seuls 1 et 5 sont premiers avec 6. Les notions plus abstraites qui suivent sont reprises progressivement dans les autres sections. Cette fonction est multiplicative : si a et b sont premiers entre eux, alors φ(ab) = φ(a)φ(b). Elle est également liée à la structure du groupe des inversibles de l'anneau ℤ/nℤ, dont elle donne le cardinal. L'indicateur d'Euler joue un rôle central en théorie des nombres, notamment dans la distribution des nombres premiers et dans le théorème d'Euler, dont le petit théorème de Fermat est un cas particulier.
Sommaire
Ce que vous allez apprendre
- Identifier les entiers comptés par φ(n).
- Calculer et contrôler φ(12).
- Appliquer correctement la multiplicativité sous son hypothèse.
- Relier φ(n) aux inversibles modulo n et au théorème d’Euler.
- Distinguer un entier premier d’un entier premier avec n.
En clair
Écrivez les entiers de 1 à 12. Certains partagent un diviseur avec 12 : 2, 3, 4 ou 6, par exemple. D’autres n’ont avec 12 que le diviseur 1 en commun : 1, 5, 7 et 11.
L’indicateur d’Euler compte précisément les entiers du second groupe. Il se note avec la lettre grecque φ, lue « phi ». Ici, quatre entiers conviennent, donc φ(12) = 4. Ce nombre ne compte pas les nombres premiers : il compte les entiers premiers avec 12.
Définition
La fonction indicatrice d’Euler, aussi appelée fonction phi d’Euler ou totient, s’applique à tout entier strictement positif n. Sa valeur, notée φ(n), est le nombre d’entiers k tels que 1 ≤ k ≤ n et que k soit premier avec n. Deux entiers sont premiers entre eux lorsque leur seul diviseur positif commun est 1. En particulier, φ(1) = 1.
La fonction est multiplicative sous une condition précise. Si les entiers positifs a et b sont premiers entre eux, alors . Cette égalité permet de ramener certains calculs à des facteurs plus simples, mais elle ne s’applique pas automatiquement lorsque a et b ont un diviseur commun.
Dans l’anneau ℤ/nℤ des restes modulo n, les classes qui possèdent un inverse forment un groupe. Son nombre d’éléments est exactement φ(n). Cette interprétation relie le comptage aux puissances en arithmétique modulaire : le théorème d’Euler utilise φ(n), et le petit théorème de Fermat en constitue un cas particulier.
Un exemple, pas à pas
Calculons φ(12), c’est-à-dire le nombre d’entiers de 1 à 12 qui sont premiers avec 12.
Données :
• l’entier étudié est n = 12 ;
• sa décomposition en facteurs premiers est 12 = 2² × 3 ;
• un entier est écarté s’il partage le facteur 2 ou le facteur 3 avec 12.
Données :
• l’entier étudié est n = 12 ;
• sa décomposition en facteurs premiers est 12 = 2² × 3 ;
• un entier est écarté s’il partage le facteur 2 ou le facteur 3 avec 12.
1. Écrire les entiers de 1 à 12.
2. Écarter les multiples de 2 : 2, 4, 6, 8, 10 et 12.
3. Écarter aussi les multiples de 3 encore présents : 3 et 9.
4. Compter les entiers restants : 1, 5, 7 et 11. Ainsi, .
2. Écarter les multiples de 2 : 2, 4, 6, 8, 10 et 12.
3. Écarter aussi les multiples de 3 encore présents : 3 et 9.
4. Compter les entiers restants : 1, 5, 7 et 11. Ainsi, .
Le résultat est donc 4. Un contrôle par inclusion-exclusion retrouve ce total : parmi 12 entiers, 6 sont multiples de 2 et 4 sont multiples de 3, tandis que les 2 multiples de 6 ont été retirés deux fois. On obtient 12 − 6 − 4 + 2 = 4. Pour transposer cette démarche, partez des facteurs premiers de l’entier étudié, comptez leurs multiples, puis corrigez les retraits effectués plusieurs fois avant de compter les entiers conservés. Une ligne numérotée de 1 à 12 rend également visible la séparation entre les quatre entiers retenus et les huit entiers écartés.
En pratique
En arithmétique modulaire, φ(n) indique combien de classes possèdent un inverse modulo n. Pour tester une classe représentée par un entier k, on cherche les diviseurs communs de k et n. Si leur seul diviseur positif commun est 1, la classe est inversible ; sinon, il faut renoncer à chercher cet inverse.
Pour réduire une grande puissance modulo n avec le théorème d’Euler, on vérifie d’abord que la base est première avec n. φ(n) fournit alors l’exposant qui organise la répétition des puissances. Si la condition échoue, le théorème ne s’applique pas tel quel et il faut calculer autrement.
Dans le chiffrement RSA, la fonction intervient dans les relations arithmétiques qui lient les exposants au module. Ce contexte exige la structure multiplicative, pas seulement un comptage brut ; une simple liste des nombres premiers inférieurs au module ne peut donc pas remplacer φ(n).
À ne pas confondre
Un nombre premier et un nombre premier avec n. Un nombre premier n’a que deux diviseurs positifs, tandis qu’un entier premier avec n n’a aucun diviseur commun avec n autre que 1. Ainsi, 1 n’est pas premier, mais il est compté dans φ(12) car il est premier avec 12.
L’indicatrice d’Euler et le théorème d’Euler. La première est une fonction de comptage : à n, elle associe φ(n). Le second est un énoncé sur des puissances modulo n. Pour 12, écrire φ(12) = 4 calcule la fonction ; utiliser cet exposant dans une congruence relève du théorème.
Limites et pièges
Le cas n = 1. La fonction n’est définie ici que pour les entiers strictement positifs. L’unique entier de 1 à 1 est premier avec 1, donc φ(1) = 1. Oublier ce cas charnière conduit à annoncer à tort un comptage vide.
Une multiplicativité conditionnelle. L’égalité multiplicative exige que les deux facteurs soient premiers entre eux. Les entiers 4 et 2 ne le sont pas : φ(8) = 4, alors que φ(4)φ(2) = 2. Si un diviseur commun apparaît, il faut calculer φ du produit sans appliquer cette égalité.
Entiers comptés et classes modulo n. La définition parcourt les entiers de 1 à n, tandis que ℤ/nℤ est souvent représenté par les restes de 0 à n − 1. Ces écritures décrivent pourtant les mêmes classes. Pour n > 1, le reste 0, représenté par n, n’est pas inversible ; il ne contribue donc pas à φ(n).
Pour aller plus loin
Premiers entre eux — Approfondir le critère qui décide quels entiers sont comptés par φ(n).
arithmétique modulaire — Situer les classes inversibles et les calculs de puissances dans leur cadre naturel.
petit théorème de Fermat — Examiner le cas particulier du théorème d’Euler lorsque le module est premier.
Fermat et son « petit » théorème — Relier l’énoncé modulaire à son histoire et à des applications présentées dans l’article.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres