Math forum
Les maths ont leur forum !
Les Cours Thierry
Cours de mathématiques et soutien scolaire par le webmaster de Math foru'
RUBRIQUES

 
Cours & Math-fiches

 
Math foru' sur Facebook


 
Rechercher dans les forums Derniers messages S'inscrire pour poster des messages S'inscrire pour poster des messages
vers le sujet précédent vers le sujet suivant
Modéré par: mtschoon, Thierry, Noemi
Fin 

Projet : Document sur la fonction indicatrice d'Euler

  - catégorie non trouvée dans : Supérieur
Envoyé: 31.07.2006, 00:49

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
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 icon_wink). 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. icon_confused Je me souviens particulièrement qu'elle contenait la démonstration d'une inégalité que je n'ai pas réussi à retrouver icon_confused : (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... icon_frown

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



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)(pk) = pk(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] (piki), avec tous les pi premiers et tous les ki ∈ N* :
(ph)(n) = n.PRODUIT(i) (1 - 1/pi)
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 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 : ∀ 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 = 2k, k ∈N* et alors n/(ph)(n) = 2 OU n = 2k'.3k'', 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 : limn->∞ (ph)(n) = ∞
Démonstration :

Proposition II.6 : limn->∞ (n.racine3) / racine(SOMME[i=0 à n] ((ph)(i)) = pi
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* : 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)) ⇔ x = 1 OU x = 2k avec k ∈ N* OU x = 2k'.3k'' 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 : an-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 : ae.d = a (mod n)

Top 
 
Envoyé: 31.07.2006, 10:14

Modérateur
Zauctore

enregistré depuis: août. 2005
Messages: 8175

Status: hors ligne
dernière visite: 07.03.13
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
Top 
Envoyé: 31.07.2006, 13:47

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
Ok merci Z c'est sympa ! icon_wink

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

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é... icon_biggrin



modifié par : madvin, 31 Juil 2006 @ 13:49
Top 
Envoyé: 31.07.2006, 20:21

Modérateur


enregistré depuis: juin. 2005
Messages: 1469

Status: hors ligne
dernière visite: 24.02.13
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. ^^

@+
Top 
Envoyé: 01.08.2006, 10:36

Modérateur
Zauctore

enregistré depuis: août. 2005
Messages: 8175

Status: hors ligne
dernière visite: 07.03.13
`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 ?
Top 
Envoyé: 02.08.2006, 08:42

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
Oui il me semble que c'est bien celle-là ! La démo y est avec. Merci Z.
Top 
Envoyé: 02.08.2006, 09:24

Modérateur
Zauctore

enregistré depuis: août. 2005
Messages: 8175

Status: hors ligne
dernière visite: 07.03.13
Tu la veux avec ou bien tu préfères que je te laisse chercher un peu ?
Top 
Envoyé: 03.08.2006, 09:46

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
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 = p1 k1 . p2 k2 . ... . pi ki 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

Je suis mal parti hein ? icon_confused
Top 
Envoyé: 06.08.2006, 14:04

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
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 !!!
Top 
Envoyé: 11.08.2006, 10:35

Modérateur
Zauctore

enregistré depuis: août. 2005
Messages: 8175

Status: hors ligne
dernière visite: 07.03.13
Ok

avec tes notations, tu as n >= p1...pi >= 2i d'où une majoration de i, n'est-ce pas

or, tu as aussi (ph)(n) >= n/(i+1), etc.
Top 
Envoyé: 12.08.2006, 02:21

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
icon_confused Je suis une brêle... J'ai oublié de majorer i !! icon_redface

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)]
Top 
Envoyé: 12.08.2006, 15:15

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
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.



modifié par : madvin, 12 Août 2006 @ 15:18
Top 
Envoyé: 12.08.2006, 22:19

Modérateur
Zauctore

enregistré depuis: août. 2005
Messages: 8175

Status: hors ligne
dernière visite: 07.03.13
Comme application de l'inégalité qui t'occupait ces derniers temps, Guinot donne ceci : si n > 100 alors (ph)(n) > 14.
Top 
Envoyé: 12.08.2006, 23:50

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
Oui oui, ça permet justement de fixer une limite dans la recherche de l'ensemble des n tels que (ph)(n) = k.
Top 
Envoyé: 13.08.2006, 08:52

Modérateur
Zauctore

enregistré depuis: août. 2005
Messages: 8175

Status: hors ligne
dernière visite: 07.03.13
Quelle preuve vas-tu donner pour I.3 ?
Top 
Envoyé: 13.08.2006, 10:49

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
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 icon_wink).

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

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 ?
Top 
Envoyé: 13.08.2006, 15:13

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
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. icon_confused



modifié par : madvin, 13 Août 2006 @ 16:45
Top 
Envoyé: 14.08.2006, 11:48

Modérateur
Zauctore

enregistré depuis: août. 2005
Messages: 8175

Status: hors ligne
dernière visite: 07.03.13
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
http://img142.imageshack.us/img142/4176/yimageif0.jpg ?
jamais vue auparavant : où l'as-tu lue ?
Top 
Envoyé: 14.08.2006, 13:11

Cosmos
madvin

enregistré depuis: oct.. 2005
Messages: 781

Status: hors ligne
dernière visite: 26.02.13
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. icon_frown



modifié par : madvin, 14 Août 2006 @ 13:16
Top 
Envoyé: 15.08.2006, 14:25

Modérateur
Zauctore

enregistré depuis: août. 2005
Messages: 8175

Status: hors ligne
dernière visite: 07.03.13
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).
@+
Top 


Boîte de connexion

 Bienvenue invité
Inscris-toi c'est gratuit !



Rejoins-nous afin de poser tes questions dans les forums de Math foru' :

 Crée ton compte
 Connexion :
Pseudo :


Mot de passe :


Retenir


Identifiants perdus ?
Membres
Dernier Nouveaux aujourd'hui0
Dernier Nouveaux hier0
Dernier Total13135
Dernier Dernier
ikazawah
 
Liens commerciaux