Calculateur de l'indicatrice d'Euler (fonction φ)

Saisissez un entier N (1 à 1 000 000) pour calculer instantanément combien d'entiers entre 1 et N sont premiers avec N (indicatrice d'Euler φ(N)), avec la décomposition en facteurs premiers et la formule utilisée. Comprend un tableau de référence de φ(n) de 1 à 100.

Tableau de référence de φ(n) de 1 à 100

Un tableau récapitulant la décomposition en facteurs premiers et la valeur de l'indicatrice d'Euler pour chaque entier de 1 à 100.

N	Décomposition	φ(n)
1	1	1
2	2	1
3	3	2
4	2²	2
5	5	4
6	2 × 3	2
7	7	6
8	2³	4
9	3²	6
10	2 × 5	4
11	11	10
12	2² × 3	4
13	13	12
14	2 × 7	6
15	3 × 5	8
16	2⁴	8
17	17	16
18	2 × 3²	6
19	19	18
20	2² × 5	8
21	3 × 7	12
22	2 × 11	10
23	23	22
24	2³ × 3	8
25	5²	20
26	2 × 13	12
27	3³	18
28	2² × 7	12
29	29	28
30	2 × 3 × 5	8
31	31	30
32	2⁵	16
33	3 × 11	20
34	2 × 17	16
35	5 × 7	24
36	2² × 3²	12
37	37	36
38	2 × 19	18
39	3 × 13	24
40	2³ × 5	16
41	41	40
42	2 × 3 × 7	12
43	43	42
44	2² × 11	20
45	3² × 5	24
46	2 × 23	22
47	47	46
48	2⁴ × 3	16
49	7²	42
50	2 × 5²	20
51	3 × 17	32
52	2² × 13	24
53	53	52
54	2 × 3³	18
55	5 × 11	40
56	2³ × 7	24
57	3 × 19	36
58	2 × 29	28
59	59	58
60	2² × 3 × 5	16
61	61	60
62	2 × 31	30
63	3² × 7	36
64	2⁶	32
65	5 × 13	48
66	2 × 3 × 11	20
67	67	66
68	2² × 17	32
69	3 × 23	44
70	2 × 5 × 7	24
71	71	70
72	2³ × 3²	24
73	73	72
74	2 × 37	36
75	3 × 5²	40
76	2² × 19	36
77	7 × 11	60
78	2 × 3 × 13	24
79	79	78
80	2⁴ × 5	32
81	3⁴	54
82	2 × 41	40
83	83	82
84	2² × 3 × 7	24
85	5 × 17	64
86	2 × 43	42
87	3 × 29	56
88	2³ × 11	40
89	89	88
90	2 × 3² × 5	24
91	7 × 13	72
92	2² × 23	44
93	3 × 31	60
94	2 × 47	46
95	5 × 19	72
96	2⁵ × 3	32
97	97	96
98	2 × 7²	42
99	3² × 11	60
100	2² × 5²	40

Astuces

L'indicatrice d'Euler φ(n) compte les entiers entre 1 et n qui sont premiers avec n. Par exemple, φ(9) = 6 (1, 2, 4, 5, 7 et 8 sont premiers avec 9).
Lorsque n est un nombre premier p, φ(p) = p − 1, car tous les nombres de 1 à p sauf p lui-même sont premiers avec un nombre premier.
Lorsque n est le produit de deux nombres premiers distincts p et q, φ(pq) = (p−1)(q−1) — une propriété utilisée directement dans la génération des clés RSA.
La formule φ(n) = n × Π(1 − 1/p) est un produit sur les facteurs premiers distincts p de n ; l'exposant de chaque facteur premier n'affecte pas le résultat.
Cet outil couvre la plage de 1 à 1 000 000 et calcule φ(n) instantanément par décomposition en facteurs premiers par division d'essai.

Questions fréquentes

Au-delà de son rôle fondamental en théorie des nombres, elle est centrale en cryptographie, en particulier pour la génération des clés RSA. La clé privée RSA est obtenue à l'aide de φ(n) = (p−1)(q−1).

Par convention, on définit φ(1) = 1. Bien que le seul entier jusqu'à 1 pouvant être considéré soit 1 lui-même, définir φ(1) = 1 permet de conserver la cohérence des propriétés multiplicatives de la fonction, ce qui est la convention mathématique standard.

Oui. Un nombre premier p n'ayant pas d'autres diviseurs que 1 et lui-même, tous les entiers de 1 à p sauf p sont premiers avec lui, donc φ(p) = p − 1.

RSA utilise un nombre composé n = pq, produit de deux grands nombres premiers, comme partie de la clé publique. Le calcul de la clé privée nécessite φ(n) = (p−1)(q−1), mais φ(n) ne peut être trouvé sans factoriser n — cette difficulté de factorisation des grands nombres est le fondement de la sécurité de RSA.

Anecdote — La fonction du XVIIIe siècle qui compte ce qui est premier entre soi

L'indicatrice d'Euler a été introduite vers 1763 par le mathématicien suisse Leonhard Euler, initialement dans le cadre de la généralisation du petit théorème de Fermat aux nombres composés. Le symbole φ (phi), aujourd'hui standard, n'a été adopté que plus tard par d'autres mathématiciens ayant systématisé la notation.

Compter les nombres premiers entre eux peut sembler simple, mais φ(n) possède plusieurs propriétés élégantes. Par exemple, en additionnant φ(d) pour chaque diviseur d de n, on obtient toujours n lui-même (Σφ(d) = n) — l'une des identités fondamentales de la théorie élémentaire des nombres.

Aujourd'hui, φ(n) joue un rôle essentiel dans la cryptographie RSA. RSA utilise le produit de deux grands nombres premiers n = pq comme partie de la clé publique, et le calcul de la clé privée nécessite φ(n) = (p−1)(q−1). Le fait que φ(n) ne puisse pas être calculé sans factoriser n (du moins avec les algorithmes actuellement connus) constitue l'un des piliers de la sécurité de RSA.

Voir toutes les anecdotes

Calculateur de l'indicatrice d'Euler (fonction φ)

Tableau de référence de φ(n) de 1 à 100

Astuces

Questions fréquentes

À quoi sert l'indicatrice d'Euler ?

Pourquoi φ(1) est-il égal à 1 ?

Est-il facile de calculer φ(p) pour un nombre premier p ?

Quel est le lien entre φ(n) et le chiffrement RSA ?

Anecdote — La fonction du XVIIIe siècle qui compte ce qui est premier entre soi