Conjecture de Carmichael sur la fonction indicatrice d’Euler

Vous êtes ici : Accueil / Articles / Mathématiques

Présentation de l’indicatrice d’Euler

La fonction indicatrice d’Euler notée $\varphi$ associe à tout entier naturel le nombre d’entiers inférieurs qui sont premiers avec lui.

La conjecture de Carmichael stipule que toute image par la fonction indicatrice d’Euler possède au moins 2 antécédents. Autrement dit

$\forall m, \exists n\ \mbox{tel que}\ \varphi( m ) = \varphi( n )$

Quelques résultats

Nous allons vérifier la conjecture jusqu’à de grands nombres.

Proposition 1 : Le plus petit nombre ne vérifiant pas la conjecture est divisible par $2^2$ .

Démonstration :

Pour tout nombre premier avec 2 ( donc impair ) n, $\varphi( 2n ) = \varphi( n )$ .

Proposition 2 : Le plus petit nombre ne vérifiant pas la conjecture est divisible par $2^23^2$ .

Démonstration :

Le plus petit nombre ne vérifiant pas la conjecture étant divisible par $2^2$ , il s’écrit de la forme $2^2k$ . Si k est premier avec 3, alors $\varphi( 3*2k ) = 2\times\varphi( 2k ) = \varphi( 2^2k )$ .

Proposition 3 : Le plus petit nombre ne vérifiant pas la conjecture est divisible par $2^23^27^2$ .

Démonstration :

Le plus petit nombre ne vérifiant pas la conjecture étant divisible par $2^23^2$ , il s’écrit de la forme $2^23^2k$ . Si k est premier avec 7, alors $\varphi( 7*2*3k ) = 6\times\varphi( 2*3k ) = \varphi( 2^23^2k )$ .

Proposition 4 : Le plus petit nombre ne vérifiant pas la conjecture est divisible par $2^23^27^243^2$ .

Démonstration :

Le plus petit nombre ne vérifiant pas la conjecture étant divisible par 4x9x49, il s’écrit de la forme $2^23^27^2k$ . Si k est premier avec 43, alors $\varphi( 43*7*2*3k ) = 42\times\varphi( 2*3*7k ) = \varphi( 2^23^27^2k )$ .

Si $3^3$ divise n

Alors $\varphi(n) = 3^2\varphi(\frac{n}{3})$

Proposition 5 : S’il est divisible par $3^3$ , le plus petit nombre ne vérifiant pas la conjecture est divisible par $2^{2}3^{3}7^{2}19^{2}43^{2}127^{2}5419^{2}$ .

En effet, toujours d’après le même principe

$2*3^{2}+1 = 19$ est premier, donc $19^2$ divise n
$2*3^{2}*7+1 = 127$ est premier, donc $127^2$ divise n
$2*3^{2}*7*43+1 = 5419$ est premier, donc $5419^2$ divise n

Proposition 6 : S’il est divisible par $3^3$ , le plus petit nombre ne vérifiant pas la conjecture est divisible par $2^{2}3^{3}7^{2}19^{2}43^{2}127^{2}2287^{2}5419^{2}101347^{2}304039^{2}78456283^{2}86714839^{2}532676863^{2}$ .

$2*3^{2}*127+1 = 2287$ est premier, donc $2287^2$ divise n
$2*3*7*19*127+1 = 101347$ est premier, donc $101347^2$ divise n
$2*3^{2}*7*19*127+1 = 304039$ est premier, donc $304039^2$ divise n
$2*3*19*127*5419+1 = 78456283$ est premier, donc $78456283^2$ divise n
$2*3^{2}*7*127*5419+1 = 86714839$ est premier, donc $86714839^2$ divise n
$2*3^{2}*43*127*5419+1 = 532676863$ est premier, donc $532676863^2$ divise n

Un dernier pour la route :

Proposition 7 : S’il est divisible par $3^3$ , le plus petit nombre ne vérifiant pas la conjecture est divisible par $2^{2}3^{3}7^{2}19^{2}43^{2}127^{2}2287^{2}5419^{2}101347^{2}304039^{2}78456283^{2}86714839^{2}532676863^{2}$ et par $3278561457979260561820783603203948493222867^{2}$ .

$2*3^{2}*7*43*5419*101347*304039*78456283*86714839*532676863+1$ = 3278561457979260561820783603203948493222867

Nous allons nous en arrêter là.

Si $3^3$ ne divise pas n

Alors $\varphi(n) = 2\times3\varphi(\frac{n}{3})$

Proposition 8 : S’il n’est pas divisible par $3^3$ , le plus petit nombre ne vérifiant pas la conjecture est divisible par $2^{2}3^{2}7^{2}13^{2}43^{2}3613^{2}$ .

$2^2*3+1 = 13$ est premier, donc $13^2$ divise n
$2^2*3*7*43+1 = 3613$ est premier, donc $3613^2$ divise n

Proposition 9 : S’il n’est pas divisible par $3^3$ , le plus petit nombre ne vérifiant pas la conjecture est divisible par $2^{2}3^{2}7^{2}13^{2}43^{2}79^{2}157^{2}547^{2}1093^{2}3613^{2}6709^{2}46957^{2}8078669^{2}12118003^{2}$ .

$2*3*13+1 = 79$ est premier, donc $79^2$ divise n
$2^2*3*13+1 = 157$ est premier, donc $157^2$ divise n
$2*3*7*13+1 = 547$ est premier, donc $547^2$ divise n
$2^2*3*7*13+1 = 1093$ est premier, donc $1093^2$ divise n
$2^2*3*13*43+1 = 6709$ est premier, donc $6709^2$ divise n
$2^2*3*7*13*43+1 = 46957$ est premier, donc $46957^2$ divise n
$2^2*13*43*3613+1 = 8078669$ est premier, donc $8078669^2$ divise n
$2*3*13*43*3613+1 = 12118003$ est premier, donc $12118003^2$ divise n

Commentaires

M. Cholet a dit le 6 avril 2009

Belle conjecture dont j’ai cherché une éventuelle démonstration. Eh bien, je pense que je l’ai trouvé. Plus facile que je ne l’aurais pensé ! Je souhaiterais savoir comment publier un résultat mathématique de cette ampleur.

Ludovic PATEY a dit le 6 avril 2009

Bonjour monsieur,
Si effectivement vous avez trouvé la conjecture, il y a 2 manières de propager vos résultats :

les conférences

les publications dans des revues mathématiques

J’aimerais beaucoup prendre connaissance de votre démonstration. Pourriez-vous me l’envoyer à ludovic arobase supinfo.com ?

M. Cholet a dit le 6 avril 2009

Avez vous des exemples de revues mathématiques à me proposer pour publier ma démonstration ?

Ludovic PATEY a dit le 6 avril 2009

A vrai dire, je n’ai jamais eu l’occasion de publier et je n’ai pas de nom de revue en tête.
Une personne plus apte à vous répondre serait par exempel Jean-Paul Delahaye :
http://www2.lifl.fr/ delahaye/

M. Cholet a dit le 6 avril 2009

Merci à vous Ludovic, votre site est intéressant et bien organisé. Continuez à développer votre site. Les propositions et leurs démonstrations sont claires.

chico fr a dit le 8 avril 2009

Pourrais-tu donner la démonstration pour 431 ?
J’ai la vague impression que quelque chose m’échappe.

Ludovic PATEY a dit le 8 avril 2009

C’est vrai que j’ai été un peu vite, mais c’est exactement le même principe que précédemment :
Dans la proposition 5, il a été prouvé que tout contre exemple était notamment divisé par 2²431², donc phi(n) = 2*431*phi(n/(2*431)).
Or 431*2+1 est un nombre premier, donc phi(431*2+1) = 431*2.
Donc phi(n) = phi(863)*phi(n/(2*431)). Or si a et b sont premier entre eux, phi(a)*phi(b) = phi(ab). Donc si n est premier avec 863, phi(n) = phi(n*863/862).
Est-ce que cela te semble plus clair ?

chico fr a dit le 9 avril 2009

C’est justement la démonstration de la 5e prposition sur le fait que 431² divise n qui me tracasse.

Ludovic PATEY a dit le 9 avril 2009

Oups, effectivement. Je sors le 5 de nul part. Il faut donc que je refasse les calculs à partir de ce point. Vous avez tout à fait raison.

M. Cholet a dit le 9 avril 2009

Ma démonstration s’en trouve momentanément bousculée.

Ludovic PATEY a dit le 9 avril 2009

J’en suis navré. Si cependant votre démonstration était basée sur une vérification empirique pour les nombres en dessous d’une certaine valeur, sachez que la conjecture a été vérifiée pour des très grandes valeurs, bien plus grandes que celles-ci. Si elle repose sur la méthode en elle-même, je vais essayer de trouver une alternative.

M. Cholet a dit le 9 avril 2009

Il s’agit hélas de la méthode. J’ai trouvé une propriété intéressante de l’indicatrice d’Euler qui est encore vraie mais ma compréhension, du problème tel qu’il est présenté ici, est tout de même mise à mal. Je ne baisse pas les bras car tout n’est pas faux. J’espère poouvoir contourné la difficulté. Cela risque néanmoins de prendre plus de temps que prévu.

Ludovic PATEY a dit le 9 avril 2009

Vous piquez vraiment ma curiosité :). En ce qui concerne la suite de la démonstration, si 2^3 divise n, alors la suite est vraie. Il faut donc voir le cas où n/4 est premier avec 2.

chico fr a dit le 9 avril 2009

Pourrais-tu être plus précis ? Comment la suite pourrait-elle être vraie si 2^3 divise n. Détaille un peu, SVP. Cela m’intéresse !

Ludovic PATEY a dit le 9 avril 2009

C’est simple : Si $2^3$ divise n, alors $\varphi(n) = 4* \varphi(n/4)$ .
Or $4 = \varphi(5)$ , donc $\varphi(n) = \varphi(5)*\varphi(n/4)$ .
Ainsi, si n est premier avec 5, $\varphi(n) = \varphi(5*n/4)$ . Ainsi si $2^3$ divise n, alors $5^2$ divise n. Il s’ensuit que l’on peut utiliser la suite car j’utilisais le facteur 5.

diablo 5 a dit le 9 avril 2009

Cela est particulièrement éclairant... Eclairant, merçi.

chico fr a dit le 10 avril 2009

J’ai beau chercher, je ne trouve pas... Y arrives-tu ? Si n/4 premier avec 2 ?

chico fr a dit le 10 avril 2009

Je cherche quelque chose qui me semble vital au problème. Il s’agit du nombre x tel que phi(x)=2^32=4294967296 et x impair. Connais-tu une méthode qui pourrait m’aider, SVP ?

Ludovic PATEY a dit le 10 avril 2009

Alors tout d’abord, en ce qui concerne ton message précédent, il faut plutôt chercher côté 3 : Il a été démontré que $3^2$ divisait tout contre exemple.

Si $3^3$ divise n, alors $\varphi(n) = 3^2*2*\varphi(\frac{n}{3^2*2})$ Or $3^2*2 = \varphi(19)$ et donc toujours suivant le même raisonnement, $19^2$ divise n

Si $3^3$ ne divise pas n, alors $\varphi(n) = 3*2^2*\varphi(\frac{n}{2^2*3})$ or $2^2*3 = \varphi(13)$ , donc $13^2$ divise n.
Ainsi, soit $19^2$ , soit $13^2$ divise n.
Pour démontrer la conjecture, il suffirait de démontrer qu’il est toujours possible d’ajouter des diviseurs à l’infini.

Ludovic PATEY a dit le 10 avril 2009

En ce qui concerne ton autre problème, $\varphi(x) = 2^n$ avec x impair si et seulement si x est un produit de facteurs premiers distincts et de la forme $2^k+1$
Regardons les k inférieurs à 32 tels que $2^k+1$ est un nombre premier. Nous obtenons 1, 2, 4, 8, 16. Or $16+8+4+2+1 < 32$ , donc ton équation n’a pas de solution impaire.

chico fr a dit le 10 avril 2009

J’avais compris qu’il suffisait de démontrer qu’il est toujours possible d’ajouter des diviseurs à l’infni, néanmoins n’y arrivant pas car nous ne connaissons pas suffisament la répartition des nombres premiers, je me suis tourné vers les puissances de 2 pour montrer la conjecture pour tous les nombres pairs et donc pour tous les nombres puisqu’elle est vraie pour tous les impairs. Il faut donc faire tendre la puissance de 2 vers l’infini. Ce qui me ramène à ma dernière question sur phi(x)=2^32=4294967296 où x impair. Selon moi, il n’existe qu’un unique impair !

chico fr a dit le 10 avril 2009

C’est bien ce que je craignais. 2^32 est un anti indicateur ! Intéressant pour les nombres de Fermat premiers ou non car 2^32=2^(2^5)=F5-1

Ludovic PATEY a dit le 10 avril 2009

Ce n’est pas un anti-indicateur car il existe un antécédent pair.
Quand bien même tu aurais trouvé des antécédents impairs par phi pour chaque puissance de 2, cela n’aurait pas prouvé la conjecture, car il faudrait que ce nombre impair soit premier avec n.

chico fr a dit le 10 avril 2009

J’admet que je suis allé un peu vite en besogne : 2^32 n’est évidemment pas un anti indicateur car 2^33 est solution mais cela reste néanmoins intéressant intéressant sur les nombres de Fermat.

Ludovic PATEY a dit le 10 avril 2009

En quoi est-ce intéressant pour les nombres de Fermat ?

chico fr a dit le 10 avril 2009

Sur la conjecture que les nombres de Fermat où n est supérieur à cinq sont tous non premiers.

Ludovic PATEY a dit le 10 avril 2009

Je connais bien cette conjecture, mais ce que tu as obtenu signifie jusque qu’il y a au moins un nombre de Fermat qui n’est pas premier, et ce nombre était déjà connu.

diablo 5 a dit le 10 avril 2009

J’avoue ne pas comprendre ton raisonnement sur phi(x)=2^32 n’a pas de solution.

diablo 5 a dit le 10 avril 2009

Pas de solution impaire pour phi(x)=2^32 ?!?

chico fr a dit le 10 avril 2009

Je suis un peu trop impulsif et conclu trop vite. Hélas encore mal ici !

Ludovic PATEY a dit le 11 avril 2009

Bon, tout d’abord, désolé du délai de réponse : ayant une connexion de moins de 1Kb/s ces jours ci, je ne répondrai plus avant mercredi. Je répondrai alors a diablo 5 en donnant une démonstration détaillée de l’absence de solution impaire, et donnerai une nouvelle démonstration pour l’article principal en espérant que cela permettra à M. Cholet d’avancer dans sa propre démonstration.

Ludovic PATEY a dit le 14 avril 2009

Diablo 5, quitte à détailler la démonstration de l’inexistence de solutions impaires, j’en ai profité pour généraliser :
http://www.pateysoft.fr/Expression-de-la-conjecture-de.html

Ludovic PATEY a dit le 15 avril 2009

M Cholet, en ce qui concerne la méthode, voici un article qui utilise la même méthode que moi et l’auteur semble penser également qu’il est possible de continuer à l’infini. De mon côté, j’ai un peu avancé dans la démonstration ci-dessus.
http://arxiv.org/ftp/arxiv/papers/0704/0704.2453.pdf

chico fr a dit le 19 avril 2009

Veuillez m’excuser, mais il me semble que dans la démonstration de la 8e proposition, utiliser 2^2 dans les combinaisons suivantes présupose que 2^3 divise tout contre exemple. Sinon, veuillez détailler pour 13.

chico fr a dit le 19 avril 2009

Eh non, le "2" supplémentaire vient du fait que phi(3)=2 si 3^3 ne divise pas le contre exemple. Désolé.

diablo 5 a dit le 19 avril 2009

Grace à ce "2" supplémentaire si 3^3 ne divise pas les contres exemples, nous pouvons utiliser "5" car 2^2=phi(5) et les calculs que vous aviez faits sont alors bon et donne plus de possibilités. Intéressants !

Ludovic PATEY a dit le 19 avril 2009

A vrai dire, dans le document que j’ai cité dans un post précédent, il est démontré que 2^32 divise forcément le contre exemple. Donc on peut le cas où 2^3 ne divise pas le nombre. Seulement, comme la démonstration est plus compliquée, j’ai laissé les 2 cas en utilisant un raisonnement simple.

Monsieur Question a dit le 7 mai 2009

J’ai vu en anglais sur wikipédia que d’après Klee, 8 et les nombres de Fermat premies ne divise pas le plus petit exemple. La conjecture serait donc vraie si et seulement si tous les nombres de la forme 8k+4 vérifiait la conjecture. Pourriez-vous confirmer cela ?

Ludovic PATEY a dit le 7 mai 2009

Non, je ne confirme pas cela.
D’après le document http://arxiv.org/ftp/arxiv/papers/0704/0704.2453.pdf
Klee a prouvé que le plus petit contre-exemple était divisible par $2^{42}$ ce qui est en contradiction avec ce que vous affirmez.

Steeve a dit le 26 mai 2009

Bonjour monsieur Patey,
Sauriez-vous confirmer que cette conjecture n’a pas encore été démontrée pour toute valeur naturelle ?
Pour ma part, j’ai voulu commencer une possible démonstration sur le fait que la plus petite valeur x telle que phi(x) = k est impaire pour toute valeur de k qui soit possible (donc en évitant k = 14 et les valeurs suivantes).
J’ai eu l’occasion d’en discuter un peu sur un forum, mais je n’ais eu que peu d’avis sur ce que je faisais. Au point que j’en suis à me demander si elle n’a pas été démontrée et que personne n’ose me le dire pour ne pas me démoraliser, d’où ma question.
Merci d’avance.

Ludovic PATEY a dit le 28 mai 2009

Bonjour, Je confirme que cette conjecture n’a pas été démontrée. Si effectivement le plus petit antécédant d’un nombre non anti-indicateur est impair, cela impliquerait que tous les nombres de Fermat soient premiers, ce qui n’est pas le cas. En voici la démonstration : http://www.pateysoft.fr/Expression-de-la-conjecture-de.html Cordialement,

Steeve a dit le 29 mai 2009

Un grand merci pour les éclaircissements.
Toutefois, lors de mes tests, je n’ais pas pu trouver de plus petite valeur x paire telle que phi(x) = k.
Pourriez-vous, s’il vous plait, m’en donner un exemple ?
Cela me serait grandement utile pour clôturer cette piste de recherche.
Merci encore.

Ludovic PATEY a dit le 30 mai 2009

Eh bien d’après mon résultat précédent, avec $\varphi(x) = 2^{32}$ , vous n’obtiendrez pas de valeur impaire.

Steeve a dit le 9 juin 2009

Je vous remercie grandement, il m’a fallu un peu de temps pour digérer ce que vous avez dis, mais j’ai compris comment obtenir ces valeur plus rapidement.
Comme vous le disiez, il n’y a pas de valeur impaire, ce qui clôt ma tentative de preuve.
J’ai aussi fais une découverte à propos de la proportion de valeurs paires et impaires, mais encore une fois sur de petites valeurs de x et je ne sais pas encore si cette règle est respectée pour toute valeur de x.
Soit I le nombre de valeurs impaires et P le nombre de valeurs paires, je crois que I <= P pour toute valeur de x.

Ludovic PATEY a dit le 9 juin 2009

Votre propriété se démontre très facilement :
phi(2) = 1, donc x est impair, phi(2x) = phi(2)*phi(x) = phi(x)
Il s’ensuit que pour tout antécédent impair x, il existe un antécédent pair, donc que I <= P.

M. Cholet a dit le 30 juin 2009

J’abandonne un temps. J’ai épuisé toutes mes idées. A la prochaine.

Praliné des Maths a dit le 20 avril 2010

Je n’y comprend rien, ce n’est pas très précie =’(

Praliné des Maths a dit le 20 avril 2010

l’art plastique c’est mieux

Steeve a dit le 21 avril 2010

Voudrais-tu bien exprimer ce qui est trop ’imprécis’ ?
Ce serait intéressant de pouvoir discuter de points qui semblent nébuleux.

Au contraire a dit le 23 avril 2010

C’est précis comme le sont les maths...

inelukimeya a dit le 28 août 2010

Ce qui nous bloque, c’est le cas n premier avec 17.
Une idée ?
En attendant je regarde les travaux de Klee et je vous tient au courant.

inelukimeya a dit le 31 août 2010

Cette idée est fertile, la suite des nombres est relativement simple.
Je passe à la conjecture de Lehmer.
A+

Annonces

Derniers articles

Articles populaires

Liens

Accueil

Envoyer à un ami

Télécharger

Plan du site

Rechercher

Le site

Divers