Projet : Document sur la fonction indicatrice d'Euler

Ca fait plusieurs années que je m'intéresse à cette fonction car je la trouve passionnante (ca va faire plaisir à Z car c'est Euler qui l'a étudiée le premier ). Bon nombre de propriétés autour de cette fonction ont déjà été démontré mais d'autres attendent encore à l'être...

J'aimerais en fait, avec votre aide et si vous le voulez bien, produire un document latex sur cette fonction : définitions, propriétés, démonstrations, etc...

Mais pour cela, il faudrait d'abord regrouper toutes les définitions, le plus possible de propriétés démontrées sur cette fonction, avec la démonstration qui va avec de préférence bien sûr, ainsi que les conjectures.

Je possède le livre "Merveilleux Nombres Premiers" de Jean-Paul Delahaye dans lequel il y a quelques uns de ces éléments, ainsi que divers liens ou documents trouvés sur le net. Il y a un chapitre aussi dans un des livres de la collection "Théorie des nombres pour amateur" que tu possèdes et dont on avait parlé Z, me souvient plus de l'auteur. Je me souviens particulièrement qu'elle contenait la démonstration d'une inégalité que je n'ai pas réussi à retrouver : (ph)(n) > une fonction avec ln. Je me souviens à peu près comment fonctionnait la démo mais impossible de la retrouver par moi-même... :frowning2:

Voilà alors trouvez-vous ça intéressant ? Et êtes vous prêt à m'aider ? Au moins pour trouver et regrouper le plus d'infos possible sur cette fonction... Mais bon il n'y a aucune contrainte, aucune obligation... c'est juste un passe temps comme les autres, mais un passe temps qui m'intéresse beaucoup personnellement... vu que quand j'ai le temps, j'essaye de trouver de nouvelles propriétés attachées à cette fonction...

Plan :

Partie I : Travaux d'Euler

Définition I.1 : Fonction indicatrice d'Euler, notée (ph) (inclus premières valeurs + graphe + histoire si possible)

Proposition I.1 : Soit n ∈ N : n est premier ⇔ (ph)(n) = n - 1

Démonstration :

Proposition I.2 : ∀ p premier,∀ k ∈ N* : $ph)(p^k$ ) = $p^k$ (1 - 1/p)

Démonstration :

Proposition I.3 : ∀ n ∈ N*, ∀ m ∈ N*, tels que n et m soient premiers entre eux :
(ph)(n.m) = (ph)(n).(ph)(m)

Démonstration :

Proposition I.4 : ∀ n ∈ N*, n>=2, n = PRODUIT[i>0] $(p$ _i$$^{k_i$} $), a v e c t o u s l e s$ p_i$ premiers et tous les $k_i$ ∈ N* :
(ph)(n) = n.PRODUIT(i) (1 - $1/p_i$ )

Démonstration :

Proposition I.5 : ∀ n ∈ N* : n = SOMME[d|n] ((ph)(d))

Démonstration :

Proposition I.6 : (Théorème de la fonction d'Euler) ∀ n ∈ N*, ∀ a ∈ N*, tels que n et a soient premiers entre eux :
$a^{(ph)(n)}$ = 1 (mod n)

Démonstration :

Proposition I.7 : ∀ n ∈ N*, ∀ a ∈ N*, tels que n et a soient premiers entre eux :
∃ k ∈ N* tel que $a^k$ = 1 (mod n) et le plus petit k vérifiant cette équation divise (ph)(n)

Démonstration :

Partie II - Autres Propriétés sur (ph)

Proposition II.1 : ∀ n ∈ N*, n>=3 : (ph)(n) est pair

Démonstration :

Proposition II.2 : ∀ n ∈ N, ∀ d ∈ N, tel que d|n : (ph)(d.n) = d.(ph)(n)

Démonstration :

Proposition II.3 : ∀ n ∈ N : (ph)(n)|n ⇔ n = 1 et alors n/(ph)(n) = 1 OU n = $2^k$ , k ∈N* et alors n/(ph)(n) = 2 OU n = $2^{k'}$ . $3^{k''}$ , k' ∈ N*, k'' ∈ N* et alors n/(ph)(n) = 3

Démonstration :

Proposition II.4 : ∀ n ∈ N*, n>=3 : (ph)(n) >= (n . ln (2)) / (ln(n) + ln(2))

Démonstration :

Proposition II.5 : $lim_{n->∞}$ (ph)(n) = ∞

Démonstration :

Proposition II.6 : $lim_{n->∞}$ (n. $s q r t$ 3) / $s q r t$ (SOMME[i=0 à n] ((ph)(i)) = $p i$

Démonstration : ????????????????????

Partie III - Equation (ph)(x) = n

Définition III.1 : Anti-indicateur

Conjecture III.1 : ∀ n ∈ N*, ∃ m ∈ N*, m ≠ n : (ph)(n) = (ph)(m)

Partie IV - Equation x - (ph)(x) = n

Définition IV.1 : Co-indicateur : Le co-indicateur de n est défini comme étant égal à n - (ph)(n)

Définition IV.2 : Anti-co-indicateur : Un anti-co-indicateur est un nombre qui n'est jamais co-indicateur.

Proposition IV.1 : ∀k ∈ N* : $2^k$ .509203 est un anti-co-indicateur

Démonstration : ????????????????????

Proposition IV.2 : Il existe une infinité d'anti-co-indicateurs

Démonstration :

Conjecture IV.1 : Tous les anti-co-indicateurs sont pairs

Partie V - Equation x = n (mod (ph)(x))

Proposition V.1 : Cas n = 0 : x = 0 (mod (ph)(x)) ⇔ x = 1 OU x = $2^k$ avec k ∈ N* OU x = $2^{k'}$ . $3^{k''}$ avec k' ∈ N*, k'' ∈ N*

Conjecture V.1 : Cas n = 1 : x = 1 (mod (ph)(x)) ⇔ x est premier

Partie VI - Utilisation de (ph) dans des démonstrations

Démonstration VI.1 : Théorème de Lucas-Kraitchik-Lehmer : Si n > 1 est tel que, pour tout facteur premier q de n-1, il existe un entier a > 1 tel que : $a^{n-1}$ = 1 (mod n) et $a^{(n-1)/q}$ ≠ 1 (mod n), alors n est premier

Démonstration VI.2 : Théorème du RSA : Soit p et q deux nombres premiers. On pose n = p.q. Si e est un entier premier avec (p - 1).(q - 1), alors il existe un entier d > 0, tel que e.d = 1 (mod (p - 1).(q - 1)). Pour cet entier d et un entier a premier avec n, on a : $a^{e.d}$ = a (mod n)

oui oui, j'aime bien ce genre d'idée thématique

l'auteur dont tu parles est marc Guinot

comme je suis en déménagement, les livres sont en cartons : faudra attendre que je remette la main dessus lol

Ok merci Z c'est sympa !

Marc Guinot c'est vrai !! Je l'oublie tout le temps c'est pas vrai !! :rolling_eyes:

Ben moi aussi je commence à être en plein déménagement d'autant plus que je commence à bosser demain. Je pourrais venir ici que le week-end dans les prochaines semaines, donc c'est pas grave, c'est pas pressé...

Salut.

C'est bête que je ne sois pas chez moi jusqu'à la rentrée, j'aurais pu te parler de la comparaison avec ln (je l'ai fait en sup, il m'aurait suffit de sortir mon cours). Mais Zauctore te trouvera ça en moins de 2. ^^

@+

`A la p. 52 du tome 3, le théorème 23 dit que : * pour tout entier n >= 3, on a (ph)(n) >= n ln(2) / [ln(n) + ln(2)].*

Est-ce l'inégalité que tu cherchais ?

Oui il me semble que c'est bien celle-là ! La démo y est avec. Merci Z.

Tu la veux avec ou bien tu préfères que je te laisse chercher un peu ?

J'aimerais bien la retrouver surtout que je me souviens qu'elle était facilement compréhensible... Si mes souvenirs sont bons, il posait soit n>=3 et n = $p_1$ $$^{k_1$ }$ . $p_2$ $$^{k_2$ }$ . ... . $p_i$ $$^{k_i$ }$ avec les $p_i$ premiers impairs tels que qqsoit/ i , $p_i$ < $p_{i+1}$ et $k_i$ app/ N* et il faisait remarquer un truc du genre $p_1$ >= 3, $p_2$ >= 5,...etc...
Ensuite il passait aux inverses, 1 / $p_1$ <= 1/3 < 1/2, 1 / $p_1$ <= 1/5 < 1/2, ... , 1 / $p_i$ < 1/2

Je suis mal parti hein ?

J'arrive pas à faire ressortir le ln !! C'est pénible !! Un indice stp Z... Apparemment faut mettre en évidence un ln(n-2) quelque part !!!

Ok

avec tes notations, tu as n >= $p_1$ ... $p_i$ >= $2^i$ d'où une majoration de i, n'est-ce pas

or, tu as aussi (ph)(n) >= n/(i+1), etc.

Je suis une brêle... J'ai oublié de majorer i !!

n >= $2^i$
donc ln(n) >= $ln(2^i$ ) car la fonction ln est croissante
donc ln(n) >= i ln(2)
donc i <= ln(n) / ln(2)
donc i + 1 <= [ln(n) / ln(2)] + 1 = [ln(n) + ln(2)] / ln(2)
donc 1 / (i + 1) >= ln(2) / [ln(n) + ln(2)] car la fonction inverse est décroissante
donc (ph)(n) >= n / (i + 1) >= n ln(2) / [ln(n) + ln(2)]

Le plan du document se trouve dans le premier post.

C'est une première ébauche incomplète bien sûr...
J'ai encore des hésitations, notamment concernant le regroupement des propriétés principales démontrées par Euler lui-même. Pour l'instant je les ai regroupées dans la partie I.
Quel est votre avis à ce sujet ?

Si vous avez des propriétés supplémentaires ou tout commentaire à émettre sur le plan et son contenu, n'hésitez surtout pas à nous en faire part.

Comme application de l'inégalité qui t'occupait ces derniers temps, Guinot donne ceci : si n > 100 alors (ph)(n) > 14.

Oui oui, ça permet justement de fixer une limite dans la recherche de l'ensemble des n tels que (ph)(n) = k.

Quelle preuve vas-tu donner pour I.3 ?

Pour I.3 j'ai déjà vu sur le net une preuve très courte utilisant la théorie des anneaux, mais c'est pas forcément très clair pour quelqu'un qui ne la connaît pas (comme moi ).

En fait j'ai les démonstrations de toutes les propriétés de la partie I dans le livre Merveilleux Nombres Premiers - de Jean-Paul Delayahe. La démo du I.3 qui s'y trouve est un peu plus longue, mais d'un niveau beaucoup plus abordable que celle utilisant la théorie des anneaux.

Par contrre je n'ai trouvé aucune démo du II.6, ni du IV.1.
Pour la IV.1 je sais juste qu'on la trouve dans la référence : J. Browkin and A. Schinzel, On integers not of the form n − ϕ(n),
Colloquium Mathematicum 68 (1995), 55–58., mais impossible de mettre la main sur un exemplaire.
Je trouve ça vraiment décevant qu'un grand nombre de démos soient inaccessibles au grand public... :frowning2:

Sinon pour les démos d'une même propriété, si il en existe plusieurs intéressantes, pourquoi pas envisager d'en mettre plusieurs dans le document ?

La démo pour la propriété I.3 que j'ai, consiste à disposer tous les nombres de 1 à n.m en un tableau de m colonnes et n lignes :

1__________2____________3 ................ m-1_____________m
m+1_______m+2_________m+3............. m+(m-1)m+m
2m+1______2m+2________2m+3........... 2m+(m-1)2m+m
.... ________............ ........... .....
(n-2)m+1__(n-2)m+2____(n-2)m+3 ......(n-2)m+(m-1)(n-2)m+m
(n-1)m+1(n-1)m+2___(n-1)m+3 ......(n-1)m+(m-1)____(n-1)m+m

Pour pouvoir calculer (ph)(n.m), il faut trouver combien parmi ces n.m nombres sont premiers avec n.m. Un nombre premier avec n.m est premier avec m mais aussi avec n. Donc essayons de savoir combien il y a de tels nombres par élimination.
Dans la première ligne il y a (ph)(m) nombres premiers avec m. Donc il y en a m-(ph)(m) qui ne le sont pas donc ils ne font pas partie des (ph)(n.m) nombres premiers avec n.m. De plus, tous les nombres des colonnes correspondantes sont à éliminer aussi car soit k un de ces nombres qui n'est pas premier avec m, alors m+k, 2m+k, ..., (n-2)m+k, (n-1)m+k ne sont bien évidemment pas premiers avec m non plus.
Donc il reste (ph)(m) colonnes de n nombres donc (ph)(n.m) <= n.(ph)(m).
Dans chacune de ces (ph)(m) colonnes, il y a exactement un nombre égal à 0 (mod n), un nombre égal à 1 (mod n), ..., un nombre égal à n-1 (mod n), donc n valeurs distinctes modulo n.
En effet, supposons que deux éléments d'une même colonne, b.m+a et b'.m+a, puissent être égaux modulo n : si b.m+a = b'.m+a (mod n), alors b.m = b'.m (mod n). En multipliant par l'inverse m modulo n (cet inverse existe puisque m et n sont premiers entre eux), on a b = b' (mod n), et plus simplement b = b' (puisque b et b' sont compris entre 0 et n-1). A une valeur donnée correspond donc un seul et même élément de la colonne : on a donc prouvé que tous les nombres des colonnes restantes sont distincts modulo n.
Donc dans chacune des (ph)(m) colonnes restantes de nombres n'ayant aucun facteur commun avec m, la suppression des nombres ayant un facteur commun avec n laissera exactement (ph)(n) nombres.
Au total, on aura donc laissé (ph)(n).(ph)(m) nombres.
Donc il y a exactement (ph)(n).(ph)(m) nombres premiers avec n.m, donc (ph)(n.m)=(ph)(n).(ph)(m). CQFD

C'est pas forcément clair mais ça pourrait être mieux dit... L'inconvénient est qu'elle fait appel à l'arithmétique modulaire qui, il y a 7 ans, n'était enseignée qu'en Terminale S, uniquement en spécialité math et encore on n'avait pas vu la notion d'inverse modulo un nombre ; aujourd'hui je ne sais pas.
A moins qu'une autre démo plus facilement compréhensible eexiste.

C'est plus ou moins basé sur la preuve de 1760 d'Euler, d'après Guinot.

En fait on peut ne pas parler de mod si on se contente de divisibilité et de reste - de toute façon, ce n'est qu'une question de vocabulaire et la notion de congruence n'était pas encore explicite du temps d'Euler ; ça ne rendra pas forcément les choses plus obscures de se passer de modulo.

Je n'avais jamais entendu parler de ces n - (ph)(n). Et pour II.6, c'est bien

?
jamais vue auparavant : où l'as-tu lue ?

Oui mais ça nous fait utiliser des propriétés sur les inverses modulo un nombre qui ne sont pas forcément triviales... à moins qu'un autre document explicite la théorie des congruences, c'est faisable et surement intéressant aussi car utile aux lycéens en particulier.

Concernant les n-(ph)(n), j'ai trouvé ça sur Wikipédia.

Et à propos de la limite, oui c'est bien ça. Elle est indiquée dans le livre de Jean-Paul Delahaye- Merveilleux Nombres Premiers, mais il n'y a ni la démo, ni l'auteur. :frowning2:

D'ici-peu, je vais te proposer une autre approche de la proposition I.3, d'après topics in the theory of numbers, par Erdös et Suranyi (Springer, 2003).
@+