- Nombres premiers, sur la droite φ(p) = p − 1
- Autres nombres
- Votre n
Calculateur de l'indicatrice d'Euler
Parmi les nombres de 1 à 12, seuls 1, 5, 7 et 11 n'ont aucun facteur commun avec 12, donc φ(12) = 4. L'indicatrice d'Euler compte ces nombres premiers avec n pour tout n. Saisissez un nombre jusqu'à 10^18 pour obtenir φ(n) avec ses facteurs premiers et la formule du produit détaillée, voyez les nombres de 1 à n avec ceux qui sont premiers avec n mis en évidence, vérifiez le théorème d'Euler, tracez φ(k) pour jusqu'à 100 000 nombres à la fois, ou trouvez tous les n ayant un φ(n) donné. Saisissez un entier n jusqu'à 10^18, ou choisissez un exemple résolu. Les tuiles montrent φ(n), les facteurs premiers de n, la part des nombres de 1 à n qui sont premiers avec n et le nombre de diviseurs, et les étapes écrivent la formule du produit avec vos nombres. Jusqu'à n = 500, les nombres de 1 à n sont dessinés : ceux qui sont premiers avec n sont pleins, les autres prennent la couleur du plus petit nombre premier qu'ils partagent avec n. Pointez un nombre pour voir son PGCD avec n, et cliquez dessus pour l'utiliser comme a dans le théorème d'Euler. Graphique montre φ(k) pour chaque k jusqu'à une limite ; cliquez sur un point pour ouvrir ce nombre. Inverse liste chaque n tel que φ(n) = m ; cliquez sur l'un d'eux pour l'ouvrir.
Comment ça marche
- Saisissez un entier n jusqu'à 10^18, ou choisissez un exemple résolu comme φ(60), un module RSA ou le nombre de Carmichael 561.
- Lisez φ(n), les facteurs premiers et la formule du produit avec vos nombres. Jusqu'à 500, pointez les nombres de 1 à n pour voir leur PGCD avec n, et cliquez sur l'un d'eux pour vérifier le théorème d'Euler avec.
- Passez à Graphique pour voir φ(k) pour chaque k jusqu'à 100 000, ou à Inverse pour lister tous les n tels que φ(n) = m.
Comment φ(n) se calcule
Décomposez n en facteurs premiers et multipliez n par (1 − 1/p) pour chaque nombre premier p qui le divise. Pour 60 = 2² × 3 × 5, cela donne 60 × 1/2 × 2/3 × 4/5 = 16. Barrer donne le même compte : sur les 60 nombres, 30 sont pairs ; sur les 30 impairs, 10 sont des multiples de 3 ; sur les 20 restants, 4 sont des multiples de 5, ce qui en laisse 16. Pour une puissance d'un nombre premier, la formule est φ(p^k) = p^(k−1)(p − 1), et les valeurs se multiplient : φ(60) = 2 × 2 × 4. Le plus difficile est la factorisation. Le calculateur utilise des divisions successives, un test de primalité de Miller-Rabin et la méthode rho de Pollard, si bien que même un produit de 18 chiffres de deux nombres premiers de 9 chiffres prend une fraction de seconde.
À quoi sert l'indicatrice
φ(n) compte les fractions k/n entre 0 et 1 qui sont déjà irréductibles, les pas qui font passer une aiguille par toutes les heures d'une horloge à n heures (1, 5, 7 et 11 sur une horloge de 12 heures), et les nombres qui ont un inverse modulo n. Euler a démontré que a^φ(n) ≡ 1 (mod n) pour tout a premier avec n, et le chiffrement RSA repose là-dessus : avec n = 3233 = 61 × 53, φ(n) = 60 × 52 = 3 120, et l'exposant public 17 a pour partenaire privé 2 753, car 17 × 2 753 = 15 × 3 120 + 1.
Questions fréquemment posées
Qu'est-ce que l'indicatrice d'Euler ?
φ(n) est le nombre d'entiers de 1 à n qui n'ont aucun facteur commun avec n autre que 1. φ(9) = 6, car 1, 2, 4, 5, 7 et 8 sont premiers avec 9, tandis que 3, 6 et 9 partagent le facteur 3. Par convention, φ(1) = 1. Euler a étudié la fonction dans les années 1760 ; Gauss lui a donné le symbole φ en 1801, et James Joseph Sylvester le nom anglais totient en 1879.
Que vaut φ d'un nombre premier ?
p − 1, car tout nombre de 1 à p − 1 est premier avec un nombre premier p, donc φ(97) = 96. Pour une puissance d'un nombre premier, φ(p^k) = p^k − p^(k−1), car seuls les multiples de p ont un facteur commun avec elle : φ(81) = 81 − 27 = 54.
Que dit le théorème d'Euler ?
Si a et n sont premiers entre eux, alors a^φ(n) laisse le reste 1 dans la division par n. Pour n = 60 et a = 7 : φ(60) = 16, et 7^16 ≡ 1 (mod 60). Le petit théorème de Fermat est le cas où n est premier. Souvent, un exposant plus petit suffit déjà : 7^4 = 2 401 = 40 × 60 + 1. Le plus petit exposant qui convient pour tout a premier avec n est la fonction de Carmichael λ(n), qui vaut 4 pour 60.
Deux nombres peuvent-ils avoir la même indicatrice ?
Oui, et le plus souvent plusieurs : φ(n) = 24 pour n = 35, 39, 45, 52, 56, 70, 72, 78, 84 et 90. Certains nombres pairs ne sont jamais une valeur de φ, 14 étant le plus petit, et aucun nombre impair supérieur à 1 ne l'est, car φ(n) est pair à partir de n = 3. Robert Carmichael a affirmé en 1907 qu'aucune valeur n'est prise exactement une fois. Ce n'est toujours pas démontré, et Kevin Ford a montré en 1998 qu'une exception devrait être plus grande que 10^(10^10).
Quelle taille de nombre puis-je saisir ?
Tout entier jusqu'à 10^18. Le calculateur le factorise en arithmétique entière exacte dans votre navigateur, si bien que φ(10^18) = 4 × 10^17 et φ(999 999 866 000 004 473) = 999 999 864 000 004 608 sont justes jusqu'au dernier chiffre. Les nombres de 1 à n sont dessinés jusqu'à 500, le graphique va jusqu'à 100 000 et l'inverse fonctionne pour des valeurs jusqu'à 10^10.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur