L'indicatrice d'Euler expliquée
Écrivez les nombres de 1 à 10 et barrez tous ceux qui ont un facteur commun avec 10. Il en reste quatre : 1, 3, 7 et 9. Ce nombre, φ(10) = 4, est l'indicatrice d'Euler, l'une des fonctions les plus utilisées de la théorie des nombres, des fractions et des horloges jusqu'au chiffrement qui protège les paiements en ligne.
Compter les nombres premiers avec n
Deux nombres sont premiers entre eux lorsque leur plus grand commun diviseur vaut 1. φ(n) compte les k de 1 à n tels que PGCD(k, n) = 1 : φ(9) = 6, φ(10) = 4, φ(12) = 4 et φ(1) = 1. Ce même nombre apparaît à bien des endroits. C'est le nombre de fractions k/n entre 0 et 1 déjà irréductibles, le nombre de pas qui font passer une aiguille par toutes les heures d'une horloge à n heures, et le nombre de k qui ont un inverse modulo n, de sorte que k × x ≡ 1 (mod n) a une solution.
La formule du produit
Si les nombres premiers qui divisent n sont p₁, p₂…, alors φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. La raison est un crible. La moitié des nombres sont pairs, donc retirer les multiples de 2 laisse la fraction 1 − 1/2 ; parmi les nombres restants, un sur trois est un multiple de 3, et ainsi de suite. D'après le théorème des restes chinois, les conditions pour des nombres premiers différents sont indépendantes, si bien que les fractions se multiplient simplement. Pour 100 = 2² × 5², cela donne 100 × 1/2 × 4/5 = 40. Deux propriétés donnent le même résultat sous une autre forme : φ(p^k) = p^(k−1)(p − 1), et φ(mn) = φ(m) φ(n) quand m et n sont premiers entre eux, donc φ(100) = φ(4) × φ(25) = 2 × 20 = 40.
Le théorème d'Euler
Fermat a remarqué en 1640 que a^(p−1) ≡ 1 (mod p) pour un nombre premier p et tout a non divisible par p. Euler a démontré la version générale, publiée en 1763 : a^φ(n) ≡ 1 (mod n) dès que PGCD(a, n) = 1. La preuve est courte. Multipliez par a les φ(n) nombres premiers avec n ; les produits sont encore premiers avec n et tous différents modulo n, ce sont donc les mêmes nombres dans un autre ordre, et en comparant les deux produits il reste a^φ(n) ≡ 1. Le plus petit exposant qui convient pour un a donné est son ordre, qui divise toujours φ(n) ; le plus petit qui convient pour tous les a à la fois est la fonction de Carmichael λ(n). Pour 561 = 3 × 11 × 17, λ(561) = 80 divise 560, donc a^560 ≡ 1 (mod 561) pour tout a premier avec 561, bien que 561 ne soit pas premier. C'est le plus petit nombre de Carmichael, et la raison pour laquelle le test de Fermat seul ne peut pas prouver qu'un nombre est premier.
La somme de Gauss sur les diviseurs et la moyenne
Additionnez φ(d) sur les diviseurs d de n et vous retrouvez toujours n : pour 12, φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss l'a démontré dans ses Disquisitiones Arithmeticae de 1801 ; on le voit en rendant irréductibles les fractions 1/12, 2/12 … 12/12 et en les classant par dénominateur. En moyenne, φ(k) vaut environ 0,61 k : la moyenne de φ(k)/k tend vers 6/π² ≈ 0,6079, qui est aussi la probabilité que deux entiers pris au hasard soient premiers entre eux, et φ(1) + … + φ(N) est proche de 3N²/π². Pour N = 1 000, la somme vaut 304 192, contre 3N²/π² ≈ 303 964.
Des valeurs jamais atteintes
φ(n) est pair pour tout n à partir de 3, car les nombres premiers avec n vont par paires k et n − k. Tous les nombres pairs ne sont pas non plus des valeurs : 14, 26, 34, 38 et 50 sont les premiers qui ne sont jamais atteints, tandis que 24 est la valeur de dix nombres différents, de 35 à 90. Les trouver est une recherche finie, car pour chaque nombre premier p qui divise n, p − 1 doit diviser φ(n). En 1907, Robert Carmichael a affirmé qu'aucune valeur n'est prise exactement une fois. Sa preuve était fausse, la question reste ouverte, et toute exception devrait être plus grande que 10^(10^10). D. H. Lehmer a demandé en 1932 si φ(n) peut diviser n − 1 pour un n composé ; aucun exemple n'est connu.
L'indicatrice dans RSA
RSA choisit deux grands nombres premiers p et q et publie n = pq et un exposant e. Comme φ(n) = (p − 1)(q − 1), quiconque sait factoriser n peut calculer φ(n), et de là l'exposant privé d tel que e × d ≡ 1 (mod φ(n)) ; le théorème d'Euler garantit alors que (m^e)^d ≡ m (mod n). Dans l'exemple classique n = 3233 = 61 × 53, φ(n) = 3 120, e = 17 et d = 2 753. Beaucoup d'implémentations utilisent plutôt λ(n) = PPCM(p − 1, q − 1), ici 780, ce qui donne le d plus petit 413. Calculer φ(n) pour un module RSA de 600 chiffres est aussi difficile que de le factoriser : à partir de n et de φ(n), les deux nombres premiers s'obtiennent avec une seule racine carrée.
À vous d'explorer
Ouvrez le calculateur et saisissez n'importe quel n jusqu'à 10^18 pour voir φ(n) avec ses facteurs premiers et la formule. Jusqu'à 500, les nombres de 1 à n sont dessinés, ceux qui sont premiers avec n en plein et les autres colorés selon le plus petit nombre premier qu'ils partagent avec n, si bien que la formule du produit devient un crible que l'on peut compter. Choisissez un nombre a pour vérifier le théorème d'Euler, passez à Graphique pour voir φ(k) jusqu'à 100 000 avec les nombres premiers sur la droite φ(p) = p − 1, ou à Inverse pour trouver tous les n tels que φ(n) = m.
Questions fréquemment posées
Pourquoi φ(1) = 1 ?
Parce que PGCD(1, 1) = 1 : le seul nombre de 1 à 1 est premier avec 1. Cette convention garde aussi les formules valables, par exemple la somme de Gauss sur les diviseurs de n, qui pour n = 1 se réduit à φ(1) = 1.
φ est-elle la même chose que la fonction de compte des nombres premiers ?
Non. π(n) compte les nombres premiers jusqu'à n, φ(n) les nombres jusqu'à n qui sont premiers avec n. φ(10) = 4 compte 1, 3, 7 et 9, tandis que π(10) = 4 compte 2, 3, 5 et 7. Elles coïncident ici par hasard : φ(12) = 4, mais π(12) = 5.
À quelle vitesse peut-on calculer φ(n) ?
Aussi vite que l'on peut factoriser n. Les facteurs premiers connus, il suffit de quelques multiplications ; sans eux, aucune méthode rapide n'est connue, et c'est sur cela que repose RSA. Pour des nombres jusqu'à 10^18, la factorisation prend quelques millisecondes dans un navigateur ; pour des nombres de plusieurs centaines de chiffres, elle peut prendre des années.
Quels nombres ont le plus petit φ(n) par rapport à n ?
Les nombres qui ont beaucoup de petits facteurs premiers. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… ne dépend que des nombres premiers qui divisent n, pas de leurs puissances : pour toute puissance de 2, il vaut exactement 1/2, et pour 30 = 2 × 3 × 5, il vaut 8/30, environ 27 %. Le produit des 15 premiers nombres premiers, 614 889 782 588 491 410, a φ(n)/n ≈ 14 %, la plus petite valeur parmi tous les nombres jusqu'à 10^18.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Ouvrir le calculateur