Aller au contenu
OneKitly

Un premier est le nombre premier avec presque tout ce qui le précède

Publié le 27/10/2026 · 3 min de lecture · Calculateurs du quotidien

Daniel Okonkwo

Daniel Okonkwo — Développeur front-end et rédacteur Tech chez OneKitly

Performance web · Formats de fichiers

Vérifié à partir de 2 sources

Voir le profil →
En bref

L'indicatrice d'Euler compte combien de nombres sous n ne partagent aucun facteur avec lui. Pour un premier, la réponse est tout : φ(97) = 96, car 97 ne divise rien en dessous. Pour un nombre à petits facteurs répétés, la réponse s'effondre — φ(36) = 12 et φ(100) = 40, puisque 36 vaut 2² × 3² et 100 vaut 2² × 5², et que tout pair comme tout multiple de l'autre premier est disqualifié. La formule multiplie n par un moins l'inverse de chaque facteur premier distinct : les facteurs répétés ne coûtent rien de plus, les nouveaux coûtent cher. C'est toute la raison pour laquelle les constructions cryptographiques préfèrent les premiers : ils maximisent le nombre de partenaires utilisables.

Publicité

φ(97) = 96, la plus grande valeur qu'un nombre sous cent puisse atteindre. φ(36) vaut 12 et φ(100) vaut 40 — plus un nombre a de facteurs premiers distincts, moins il garde de compagnons.

La multiplicité est gratuite, la variété coûte cher

Trente-six et cent sont tous deux des carrés de nombres sans facteur carré et perdent de la même manière, mais cent garde une part plus grande, car cinq retire seulement un cinquième des candidats quand trois en retire un tiers. Ajoute un troisième premier distinct et une autre fraction s'en va : un nombre égal à deux fois trois fois cinq fois sept garde moins du quart de ce qui le précède. Élever l'un de ces premiers à une puissance supérieure ne change rien du tout — 2 × 3 et 2⁵ × 3⁷ gardent exactement la même proportion. C'est pourquoi la fonction se décrit par les premiers qui divisent n et non par la taille de n.

Le théorème qui la rend utile

Le théorème d'Euler dit qu'élever un nombre premier avec n à la puissance φ(n) laisse un reste de un. Ce seul fait permet de réduire un exposant avant même de le calculer — l'exposant ne compte que modulo φ(n) — et c'est la charnière mathématique sur laquelle tourne la construction à clé publique standard. Les exposants public et privé de ce schéma sont choisis pour se multiplier à un modulo φ(n), si bien que les appliquer l'un après l'autre restitue le message d'origine. Tout le reste de la construction relève de l'ingénierie ; ceci est la part qui doit être vraie.

φ(n)
Comment la factorisation commande la réponse
nFactorisationφ(n)Part de n
362² × 3²1233 %
1002² × 5²4040 %
97979699 %

Exemple calculé avec notre outil

Calculateur d'indicatrice d'Euler φ(n)

Données

n (entier positif)
36

Résultat

φ(n)
12
Nombre de coprimes dans 1…n
12

Ces chiffres sont produits par le calculateur ci-dessous, pas saisis à la main — ils sont recalculés à chaque évolution de l'outil.

Refaire ce calcul avec tes chiffres →
Publicité

Questions fréquentes

Pourquoi φ(1) vaut-il un ?
Par convention, et la convention gagne sa place. Un est compté comme premier avec lui-même parce que leur plus grand commun diviseur vaut un, ce qui est la définition employée, et poser φ(1) = 1 garde toutes les formules faisant intervenir la fonction opérationnelles sans cas particulier. Les définitions aux bornes se choisissent d'ordinaire précisément pour cette raison : non parce que la réponse est évidente, mais parce qu'un choix rend les énoncés généraux vrais partout et que l'autre force des exceptions dans le texte.
Peut-on calculer φ(n) sans factoriser n ?
Par aucun moyen connu, et cette ignorance est porteuse. Connaître φ(n) pour un grand produit de deux premiers équivaut à connaître la factorisation — l'un et l'autre se déduisent mutuellement en deux lignes d'algèbre — si bien qu'une méthode efficace pour l'indicatrice serait une méthode efficace de factorisation. La sécurité du schéma à clé publique standard repose sur l'absence des deux. C'est l'un des cas les plus nets où un morceau de théorie des nombres pure soutient quelque chose d'usage quotidien.

Articles qui pourraient t'intéresser

Tous les guides →

Outils similaires

Sources

Tu as repéré une erreur dans cet article ?