NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 25/01/2017

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

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

 

 

 

 

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

Premier p

 

 = n – 1

 

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

 

 = pn-1 (n – 1)

 

Le totient est multiplicatif pour des nombres premiers entre eux.

 

 

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.

 

 

 

 

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

Voir Nombres hautement composés

 

 

 

Valeurs notables

 

Consécutifs

 

 

 

 

Liste des nombres n de 1 à 10 000

dont le suivant a même totient.
 

 

 

Seul cas inférieur à1010 selon Guy (2004):

 

 

 

Curiosités

(9007199254740881) = 9007199254740880

 (9007199254740997) = 9007199254740996

 (9999999999999999999) = 6666666666666666660

 

 

 

Propriétés

 

Propriété

 

n'existe pas pour n >1

 

*          Aucun nombre n'est égal à son indicatrice d'Euler sauf n = 1.

Théorème

 

 

*          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 . 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 .

Formulation de Ribenboim (1996)

 

*    Autre formulation:

 

Si A(f) est la quantité d'entiers positifs n pour lesquels , 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'à:

*    1037 Carmichael lui-même,

*    10400 Victor Klee,

*    1010^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

 

 

Avec la décomposition en facteurs premiers:

 

 

 

Exemple

 

10 = 2 x 5

p1 = 2

p2 = 5

 

 (n) = 10 (1 – 1/2) (1 – 1/5)

= 10 x 1/2 x 4/5

=   4

 Cas de deux diviseurs

 

 = (p – 1) (q – 1)

 

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é

 

Soit s la somme de

tous les nombres premiers avec n

inférieurs à n.

 

s = 1/2 n .  (n)

 

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

 

Si a et m sont des entiers naturels premiers entre eux

 

 

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

a4 º 1 mod 5

pour tout a premier avec 5

 

a

a4

a4 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.

 

 

Exemple

 

 

Voir Nombre parfait

 

 

 

 

 

 

Suite

*         Phi – Propriétés

*         Diviseurs

*         EulerIndex

*         Constante d'Euler

*         Table des totients jusqu'à 500

Voir

*         Fonctions arithmétiquesIndex

*         Initiation à la théorie des nombres

*         Premiers entre eux

*         Quantité de diviseurs

*         Suite de Farey

DicoNombre

*         Nombre 2 592

Site

*         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