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...
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 app/ N : n est premier equiv/ (ph)(n) = n - 1 Démonstration :
Proposition I.2 : qqsoit/ p premier, qqsoit/ k app/ N* : (ph)(pk) = pk(1 - 1/p) Démonstration :
Proposition I.3 : qqsoit/ n app/ N*, qqsoit/ m app/ N*, tels que n et m soient premiers entre eux :
(ph)(n.m) = (ph)(n).(ph)(m) Démonstration :
Proposition I.4 : qqsoit/ n app/ N*, n>=2, n = PRODUIT[i>0] (piki), avec tous les pi premiers et tous les ki app/ N* :
(ph)(n) = n.PRODUIT(i) (1 - 1/pi) Démonstration :
Proposition I.5 : qqsoit/ n app/ N* : n = SOMME[d|n] ((ph)(d)) Démonstration :
Proposition I.6 : (Théorème de la fonction d'Euler) qqsoit/ n app/ N*, qqsoit/ a app/ N*, tels que n et a soient premiers entre eux :
a(ph)(n) = 1 (mod n) Démonstration :
Proposition I.7 : qqsoit/ n app/ N*, qqsoit/ a app/ N*, tels que n et a soient premiers entre eux :
exist/ k app/ N* tel que ak = 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 : qqsoit/ n app/ N*, n>=3 : (ph)(n) est pair Démonstration :
Proposition II.2 : qqsoit/ n app/ N, qqsoit/ d app/ N, tel que d|n : (ph)(d.n) = d.(ph)(n) Démonstration :
Proposition II.3 : qqsoit/ n app/ N : (ph)(n)|n equiv/ n = 1 et alors n/(ph)(n) = 1 OU n = 2k, k app/N* et alors n/(ph)(n) = 2 OU n = 2k'.3k'', k' app/ N*, k'' app/ N* et alors n/(ph)(n) = 3 Démonstration :
Conjecture III.1 : qqsoit/ n app/ N*, exist/ m app/ N*, m diff/ 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 : qqsoit/k app/ N* : 2k.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)) equiv/ x = 1 OU x = 2k avec k app/ N* OU x = 2k'.3k'' avec k' app/ N*, k'' app/ N*
Conjecture V.1 : Cas n = 1 : x = 1 (mod (ph)(x)) equiv/ 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 : an-1 = 1 (mod n) et a(n-1)/q diff/ 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 : ae.d = a (mod n)
Marc Guinot c'est vrai !! Je l'oublie tout le temps c'est pas vrai !!
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é...
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. ^^
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 = p1k1 . p2k2 . ... . piki avec les pi premiers impairs tels que qqsoit/ i , pi < pi+1 et ki app/ N* et il faisait remarquer un truc du genre p1 >= 3, p2 >= 5,...etc...
Ensuite il passait aux inverses, 1 / p1 <= 1/3 < 1/2, 1 / p1 <= 1/5 < 1/2, ... , 1 / pi < 1/2
n >= 2i
donc ln(n) >= ln(2i) 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.
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...
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 ?
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.
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).
@+
Merci Z... Pas mal du tout tout cela...
Et puis c'est sûr qu'en Latex ça a une meilleure gueule !!
Très intéressante ta démo du I.3. Elle est beaucoup plus simple que celle que j'avais donné, mais pour pouvoir l'utiliser faudrait démontrer la I.5 avant. En tout cas cette démo faudra la mettre dans le document, je la connaissais pas et elle est vraiment pas mal.
Concernant tes propriétés 3 et 4, j'avais réussi à les trouver et à les démontrer par moi-même donc ce sera pas difficile à démontrer.
La 5 je la connaissais pas...
Et puis pour les conjectures 6, 7 et 8 c'est bien maintenant on a les noms... Je savais juste que la 7 était de Carmichael mais pas les 2 autres. Faudra rajouter la 6 aussi dans le plan...
A propos de la 10, ben voilà d'où elle sort la limite II.6 J'espère que t'as la démo ce serait cool !!
Bon ben ça avance plutôt bien tout ça...
Je mettrai à jour le plan un peu plus tard, faudrait que je commence à bosser là un peu tout de même !!
J'ai encore d'autres formules sous le coude que j'avais réussi à trouver... particulièrement 2 formules qui permettent de prouver la conjecture de Carmichael pour une grande partie des entiers. Les démos sont pas compliquées et c'est toujours intéressant à indiquer...
Comme j'en avais parlé précédemment, ça pourrait être intéressant aussi de produire un document sur la théorie des congruences, et un autre sur une petite introduction à la théorie des nombres, contenant en particulier le théorème fondamental de l'arithmétique, le petit théorème de Fermat et le théorème chinois. Ca ferait 2 bons documents introducteurs à celui de la fonction indicatrice d'Euler.
@+ tard et merci encore pour cette belle avancée...
I.5 se prouve assez simplement en réfléchissant aux formes réduites des n fractions 1/n, 2/n, ..., n/n. Sisi, je t'assure.
La limite 10, hum... sa preuve y est, mais laisse-moi un peu de temps pour comprendre ce que racontent Hardy&Wright ! Je me doutais que tu serais content de cette trouvaille.
Dans le même genre d'idées que la démarche précédente (9:40), on peut aller un peu plus loin. La suite dans quelques minutes...
Oui j'en avais déjà vu une démo dans un bouquin, mais quand à la retrouver... =/.... En tout cas j'ai la formule qui permet de calculer la valeur de la fonction dzeta pour tous les entiers pairs.
Pour les impairs c'est encore le mystère... J'ai juste une démo qui montre que dzeta(3) est irrationnel, mais faut voir la démo de malade !!!
). Bon nombre de propriétés autour de cette fonction ont déjà été démontré mais d'autres attendent encore à l'être...
Je me souviens particulièrement qu'elle contenait la démonstration d'une inégalité que je n'ai pas réussi à retrouver 
3) / 
? 
Je savais juste que la 7 était de Carmichael mais pas les 2 autres. Faudra rajouter la 6 aussi dans le plan...
!! Je préfère pas imaginer le charabia !! 
