indicatrice d'Euler

NOMBRES – Curiosités, Théorie et Usages Accueil DicoNombre Rubriques Nouveautés Édition du: 29/01/2023 Orientation générale DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	Nombres – Caractéristiques
Débutants Nombres	Indicatrice d'EULER (Phi)				Glossaire Nombres
INDEX Euler Nombre et leurs représentations	Phi – Débutant	Phi – Approche	Phi – Opérations	Phi – Propriétés
		Table 1 à 500
		Sommaire de cette page >>> Fonction phi d'Euler *>>>* Nombre premier >>> Nombre hautement indicateur >>> Valeurs notables >>> Propriétés >>> Conjectures de Carmichael >>> Calcul de phi >>> Somme de phi >>> Produit de phi >>> Division de phi >>> Puissance avec phi >>> Totient parfait

Fonction PHI d'EULER

ou indicatrice d'EULER

ou totient d'EULER

Calculs / Opérations

Phi (n) est la quantité de nombres premiers avec n, inférieurs à n.

Ses propriétés sont riches et extraordinairement simples.

Voir approche simple en Débutants

Rappel sur le principe du dénombrement

FONCTION PHI D'EULER

Définition

𝝋(n)

est la quantité de

nombres premiers

avec n, qui sont inférieurs à n

Pour n > 1, le totient ou indicateur d'Euler j (n) est le nombre de nombres premiers avec n, inférieur à n.

The function phi or totient function of n is the number of positive integers not exceeding n and relatively prime to n.

Propriété

n	Premiers avec n	φ(n)
1	On pose φ(1) =	1
2	1	1
3	1 2	2
4	1 3	2
5	1 2 3 4	4
6	1 5	2
7	1 2 3 4 5 6	6
8	1 3 5 7	4
9	1 2 4 5 7 8	6
10	1 3 7 9	4
etc.

NOMBRE PREMIER

Nombre premier

φ(p) = p – 1

C'est d'ailleurs une condition nécessaire et suffisante pour qu'un nombre n soit premier.

Nombres premiers entre eux

Le totient est multiplicatif pour des nombres premiers entre eux.

Exemple

n	φ(n)	n premier	n – φ(n)
1	1	/	0
2	1	P	1
3	2	p	1
4	2		2
5	4	p	1
6	2		4
7	6	p	1
8	4		4
9	6		3
10	4		6
etc.

Pour les nombres premiers p – phi(p) = 1

Puissance d'un nombre premier

Exemple

En fait, il existe quatre formules pour la puissance de p

Vérification

Nombre hautement indicateur ou totient record

Combien de fois le nombre T est-il totient de n?

Par exemple: T = 72 = φ {73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270}. Le nombre 72 est le totient de 17 nombres. Aucun nombre avant lui n'atteint cette quantité. Il est Hautement-totient ou hautement indicateur.

Liste:

1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1 152, 1 440, 2 880,

4 320, 5 760, 8 640, 11 520, 17 280, 25 920, 30 240, 34 560, 40 320, 51 840, …

Anglais: Highly totient number

Suite en Nombres hautement indicateurs / Voir Nombres hautement composés

Valeurs notables
Consécutifs	Liste des nombres n de 1 à 10 000 dont le suivant a même totient.

Propriétés
	Aucun nombre n'est égal à son indicatrice d'Euler sauf n = 1.
	Toute indicatrice existe au moins deux fois. Suite ci-dessous

"Conjecture" de Carmichael

La conjecture de Robert Carmichael (1907) à propos des totients concerne la multiplicité des valeurs de la fonction totient d'Euler φ(n). Il en fait un théorème et le démontre puis en 1922, il conclut que cela reste un problème ouvert.

Elle dit:

Pour tout entier n ≥ 2, il y a au moins un autre entier différent tel que leur totient soient identiques φ(n) = φ(m).

Formulation de Ribenboim (1996)

Autre formulation:

Si A(f) est la quantité d'entiers positifs n pour lesquels φ(n) = f, alors A(f) n'est jamais égal à 1.

Théorème:

A(f) prend toute les valeurs possibles des entiers positifs, sauf la valeur unité.

Exemples

Pour chaque valeur d'un totient, il existe au moins un deuxième nombre de même totient.

Ce que l'on sait

Cette propriété est vérifiée jusqu'à:

10³⁷ Carmichael lui-même,

10⁴⁰⁰Victor Klee,

10^{10^10} par Kevin Ford (1998).

Historique de A(f)

Waclaw Sierpinki avait conjecturé que A(f) prend toutes les valeurs possibles; démonté par Kevin Ford en 1999.

Voir Totient inverse / Conjectures

Référence: Carmichael's Totient Function Conjecture

CALCUL DE PHI
Formule	Exemple 10 = 2 x 5 p₁ = 2 p₂ = 5 φ(n) = 10 (1 – 1/2) (1 – 1/5) = 10 x 1/2 x 4/5 = 4
Cas de deux diviseurs	Calcul n = p . q φ(n) = n (1 – 1/p) (1 – 1/q) = n (p – 1) (q – 1) /p . q = (p – 1) (q – 1)

Voir Radical d'un nombre

SOMME de PHI

Propriété

Tout nombre est la somme

des indicatrices de ses diviseurs:

La formule se lit:

Exemples

n = 10

d(10) = { 1, 2, 5, 10 }

φ => 1, 1, 4, 4

Somme = 1 + 1 + 4+ 4 = 10

n = 12

d(12) = { 1, 2, 3, 4, 6, 12 }

φ => 1, 1, 2, 2, 2, 4

Somme = 1 + 1 + 2+ 2 + 2 + 4 = 12

Voir Illustration

Propriété

Exemple

n = 12

Premiers avec 12 = {1, 5, 7, 11}

Leur somme s = 1 + 5 + 7 + 11 = 24

φ(12) = 4

Calcul de s

s = 1/2 x 12 x 4 = 24

PRODUIT de PHI

Propriété

Si a et b

sont premiers entre eux

(a.b) = φ (a) . φ(b)

La fonction indicatrice d'Euler

est multiplicative.

Exemples

φ (10) = 4

φ (10) = φ (2) . φ (5)

= 1 x 4 = 4

(12) = 4

φ (12) = φ (3) . φ (4)

= 2 x 2 = 4

Attention:

Avec des non premiers, ça ne marchent pas

φ (12) = φ (2) . φ (6)

= 1 x 2 ne donne pas 4.

Propriété

Si d est le PGCD de a et b

φ(a.b) = d. φ (a) . φ (b) / φ (d)

Exemples

12 = 2 x 6

d = PGCD(2,6) = 2

φ (12) = 2 φ (2) . φ (6) / φ (2)

= 2 x 1 x 2 / 1

= 4

DIVISION de PHI

Propriété

Si d divise a

φ (d) divise φ (a)

Exemples

d	φ (d)	a	φ (a)
5	4	10	4
		100	40
6	2	12	4
		18	6
		24	8
		30	8

PUISSANCE avec PHI

Théorème d'Euler

ou de Fermat-Euler

C'est une généralisation du petit théorème de Fermat. Il est à la base du cryptage par le système RSA.

Exemple

m = 5 et φ (5) = 4

a⁴ º 1 mod 5

pour tout a premier avec 5

a	a⁴	a⁴ mod 5
1	1	1
2	16	1
3	81	1
4	256	1
5	625	0
6	1296	1
7	2401	1
8	4096	1
9	6561	1
10	10000	0

Voir Fermat / Autre généralisation d'Euler / Application: racine primitive

ITÉRATIONS avec PHI – Totient parfait

Le totient d'un nombre est itéré et la somme est égale au nombre.

Les premiers totients parfaits:

3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375 …

Toutes les puissances de 3 sont totients parfaits.

Une grande majorité des totients parfaits sont des multiples de 3. Le plus petit contre-exemple est: 4375.

Voir Nombre parfait

Suite	Phi – Propriétés Diviseurs Euler – Index Constante d'Euler Table des totients jusqu'à 500
Voir	Fonctions arithmétiques – Index Initiation à la théorie des nombres Premiers entre eux Quantité de diviseurs Quantité de puissances inférieures à n Suite de Farey
DicoNombre	Nombre 2 592
Site	La fonction indicatrice d'Euler – Alain Kraus – pdf à partir de la page 19. Euler's Totient Calculator OEIS A000010 – Euler totient function phi(n) OEIS A097942 – Highly totient numbers
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Nombre/PhiEuler.htm