Preuve de la conjecture de Derrick Lehmer
Salut.
Je propose à la critique cette démonstration de la conjecture de Derrick Lehmer.
Derrick Lehmer a dit que:
$\textrm{Conjecture}$ :
$n > 1$ est premier, si et seulement si $n\equiv 1\bmod \varphi (n)$.
Preuve:
Soient les trois assertions quantifiées par $n$ suivantes.
$P(n)$ := ''$n$ est un nombre premier''.
$D(n)$ := ''$n\equiv 1\bmod \varphi(n)$''.
$B(n)$ := ''$(\varphi(n)\big)^{n}\equiv - 1\bmod n$''
Montrons que $P(n)\,\iff\,B(n)\,\iff\,D(n)$.
$\bullet$ Si $P(n)$ alors, $n$ est un nombre premier, et donc $\varphi(n) = n - 1$.
Mais $\varphi(n) = n - 1\implies n\equiv 1\bmod \varphi(n)\implies D(n)$.
C'est dire que $P(n)\,\implies\,D(n)\qquad (1)$.
On a aussi (d'après le petit théorème de Fermat) $(\varphi(n)\big)^{n}\equiv \varphi(n)\bmod n$ or $\varphi(n) = n - 1$
et donc $(\varphi(n)\big)^{n}\equiv n - 1\bmod n \equiv - 1\bmod n$ d'où $B(n)$.
C'est dire que $P(n)\,\implies\,B(n)$.
$\bullet$ Si $B(n)$ alors, $(\varphi(n)\big)^{n}\equiv - 1\bmod n$.
$a)$ Montrons que si $n$ est sans carré, alors $(\varphi(n)\big)^{n}\equiv \varphi(n) \bmod n$,
et donc $\varphi(n) \equiv - 1\bmod n$ si on a $B(n)$.
En effet si $n$ est sans carré, on peut poser $n = \prod_{i=0}^{r}p_{i},\,r\,\in\,\mathbb{N}^*$ et les $p_{i}$ premiers.
Mais alors $\varphi(n) = \prod_{i=0}^{r}(p_{i} - 1),\,r\,\in\,\mathbb{N}^*$, et par la suite,
$\big(\varphi(n)\big)^{n} = \big(\prod_{i=0}^{r}(p_{i} - 1)\big)^{n} = \big(\prod_{i=0}^{r}(p_{i} - 1)\big)^{\prod_{i=0}^{r}p_{i}}$
Mais $\big(\prod_{i=0}^{r}(p_{i} - 1)\big)^{p_{i}}\equiv \prod_{i=0}^{r}(p_{i} - 1)\bmod p_{i},\,\forall\,i\,\in\,[\![1; r]\!]$.
Les $p_{i}$ étant tous premiers entre eux (car premiers), alors
$\big(\prod_{i=0}^{r}(p_{i} - 1)\big)^{\prod_{i=0}^{r}p_{i}}\equiv \prod_{i=0}^{r}(p_{i} - 1)\bmod \prod_{i=0}^{r}p_{i}$.
C'est-à-dire que $\big(\varphi(n)\big)^{n}\equiv \varphi(n)\bmod n$. Mais comme on a supposé $B(n)$, alors $\varphi(n)\equiv - 1\bmod n$.
Mais donc $\varphi(n) = - 1 + \alpha n,\,\alpha\,\in\,\mathbb{N}^*$, et comme on a $\varphi(n)\,\lt\,n,\,\forall\,n\,\in\,\mathbb{N}^*$, alors
$\alpha = 1$ et par la suite $\varphi(n) = - 1 + n$, ce qui veut dire que $n$ est premier.
$b)$ Mais si $n$ a un facteur carré, on peut posé $n = p_{j}^{\alpha_{j}}\prod_{i=0}^{r}p_{i}^{\alpha_{i}},\j,\,r\,\in\,\mathbb{N}^*$, avec
$\alpha_{j},\,\alpha_{i}\,\in\,\mathbb{N}^*\,\forall\,i\,\in\,[\![1; r]\!],\,\alpha_{j}\geq 2$.
Mais alors $\varphi(n) = (p_{j} - 1)p_{j}^{\alpha_{j}-1}\prod_{i=0}^{r}(p_{i} - 1)p_{i}^{\alpha_{i}-1}$.
Ce qui implique $\big(\varphi(n)\big)^{n} = \big((p_{j} - 1)p_{j}^{\alpha_{j}-1}\prod_{i=0}^{r}(p_{i} - 1)p_{i}^{\alpha_{i}-1}\big)^{n}$
Et donc $\big(\varphi(n)\big)^{n}\equiv - 1\bmod n$ est impossible, car cela voudrait dire que \
$\big((p_{j} - 1)p_{j}^{\alpha_{j}-1}\prod_{i=0}^{r}(p_{i} - 1)p_{i}^{\alpha_{i}-1}\big)^{n} = - 1 + \beta p_{j}^{\alpha_{j}}\prod_{i=0}^{r}p_{i}^{\alpha_{i}}$, ce qui entrenerait que $p_{j}$ divise 1 (car $\alpha_{j}-1\geq 1$), ce qui est évidemment absurde.
On a montré par $a)$ et $b)$ que si $B(n)$ alors $n$ est premier.
C'est dire que $B(n)\,\implies\,P(n)\qquad (2)$.
$\bullet$ Maintenant si $D(n)$, alors $n = 1 + a\varphi(n),\,a\,\in\,\mathbb{N}^*$, et par suite $a$ et $n$ sont premiers entre eux (un facteur de $a$ et $n$ est un facteur de 1).
On a aussi que $\varphi(n)$ et $n$ doivent etre premiers entre eux, et donc $n$ est impair et sans carré (ce qui entraine que $n$ est un nombre de Carmichael).
$D(n)\,\implies\,a\varphi(n) = n - 1$, et donc $\big(a\varphi(n)\big)^{n} = (n - 1)^{n} \equiv - 1\bmod n$ (car $n$ impair).
On a alors $\big(a\varphi(n)\big)^{n} = a^{n}\big((\varphi(n)\big)^{n}\equiv a(\varphi(n))^{n}\equiv - 1\bmod n$
(car $n$ est un nombre de Carmichael).
Alors $\big((\varphi(n)\big)^{n}\equiv (- a)^{-n} = - (a^{-1})^{n}\equiv - a^{-1}\bmod n$.
Donc $a^{-1}\equiv (a^{-1})^{n}\bmod n$, ce qui implique $(a^{-1})^{n-1}\equiv 1\bmod n$, et donc
$(a^{-1})^{-1}\equiv a^{n-2}\bmod n$ et par suite $a^{n-3}\equiv 1\bmod n$.
On a donc $a^{n-3}\equiv a^{n-1}\bmod n$.
Alors $a^{n-3} - a^{n-1}\equiv 0\bmod n\,\implies\,a^{n-3}(1 - a^{2})\equiv 0\bmod n\,\implies\,a^{2}\equiv 1\bmod n$.
C'est dire que $a \equiv a^{-1}\bmod n$, et donc $a = 1$ où $a = n - 1$ (car $0\,\lt\,a\,\lt\,n$).
Mais comme on a $D(n)$, $a = n - 1$ est impossible, et donc $a = 1$, ce qui entraine $B(n)$ et $P(n)$.
C'est-à-dire :
$D(n)\,\implies\,B(n)$ et $D(n)\,\implies\,P(n)\qquad (3)$.
($(1),\,(2)$ et $(3)$) entraine $D(n)\,\iff\,B(n)\,\iff\,P(n)$.
D'où :
$\textrm{Théorème}$ :
$n > 1$ est premier, si et seulement si $n\equiv 1\bmod \varphi (n)$.
$n > 1$ est premier, si et seulement si $\big((\varphi(n)\big)^{n}\equiv - 1\bmod n$.
Cordialement.
Je propose à la critique cette démonstration de la conjecture de Derrick Lehmer.
Derrick Lehmer a dit que:
$\textrm{Conjecture}$ :
$n > 1$ est premier, si et seulement si $n\equiv 1\bmod \varphi (n)$.
Preuve:
Soient les trois assertions quantifiées par $n$ suivantes.
$P(n)$ := ''$n$ est un nombre premier''.
$D(n)$ := ''$n\equiv 1\bmod \varphi(n)$''.
$B(n)$ := ''$(\varphi(n)\big)^{n}\equiv - 1\bmod n$''
Montrons que $P(n)\,\iff\,B(n)\,\iff\,D(n)$.
$\bullet$ Si $P(n)$ alors, $n$ est un nombre premier, et donc $\varphi(n) = n - 1$.
Mais $\varphi(n) = n - 1\implies n\equiv 1\bmod \varphi(n)\implies D(n)$.
C'est dire que $P(n)\,\implies\,D(n)\qquad (1)$.
On a aussi (d'après le petit théorème de Fermat) $(\varphi(n)\big)^{n}\equiv \varphi(n)\bmod n$ or $\varphi(n) = n - 1$
et donc $(\varphi(n)\big)^{n}\equiv n - 1\bmod n \equiv - 1\bmod n$ d'où $B(n)$.
C'est dire que $P(n)\,\implies\,B(n)$.
$\bullet$ Si $B(n)$ alors, $(\varphi(n)\big)^{n}\equiv - 1\bmod n$.
$a)$ Montrons que si $n$ est sans carré, alors $(\varphi(n)\big)^{n}\equiv \varphi(n) \bmod n$,
et donc $\varphi(n) \equiv - 1\bmod n$ si on a $B(n)$.
En effet si $n$ est sans carré, on peut poser $n = \prod_{i=0}^{r}p_{i},\,r\,\in\,\mathbb{N}^*$ et les $p_{i}$ premiers.
Mais alors $\varphi(n) = \prod_{i=0}^{r}(p_{i} - 1),\,r\,\in\,\mathbb{N}^*$, et par la suite,
$\big(\varphi(n)\big)^{n} = \big(\prod_{i=0}^{r}(p_{i} - 1)\big)^{n} = \big(\prod_{i=0}^{r}(p_{i} - 1)\big)^{\prod_{i=0}^{r}p_{i}}$
Mais $\big(\prod_{i=0}^{r}(p_{i} - 1)\big)^{p_{i}}\equiv \prod_{i=0}^{r}(p_{i} - 1)\bmod p_{i},\,\forall\,i\,\in\,[\![1; r]\!]$.
Les $p_{i}$ étant tous premiers entre eux (car premiers), alors
$\big(\prod_{i=0}^{r}(p_{i} - 1)\big)^{\prod_{i=0}^{r}p_{i}}\equiv \prod_{i=0}^{r}(p_{i} - 1)\bmod \prod_{i=0}^{r}p_{i}$.
C'est-à-dire que $\big(\varphi(n)\big)^{n}\equiv \varphi(n)\bmod n$. Mais comme on a supposé $B(n)$, alors $\varphi(n)\equiv - 1\bmod n$.
Mais donc $\varphi(n) = - 1 + \alpha n,\,\alpha\,\in\,\mathbb{N}^*$, et comme on a $\varphi(n)\,\lt\,n,\,\forall\,n\,\in\,\mathbb{N}^*$, alors
$\alpha = 1$ et par la suite $\varphi(n) = - 1 + n$, ce qui veut dire que $n$ est premier.
$b)$ Mais si $n$ a un facteur carré, on peut posé $n = p_{j}^{\alpha_{j}}\prod_{i=0}^{r}p_{i}^{\alpha_{i}},\j,\,r\,\in\,\mathbb{N}^*$, avec
$\alpha_{j},\,\alpha_{i}\,\in\,\mathbb{N}^*\,\forall\,i\,\in\,[\![1; r]\!],\,\alpha_{j}\geq 2$.
Mais alors $\varphi(n) = (p_{j} - 1)p_{j}^{\alpha_{j}-1}\prod_{i=0}^{r}(p_{i} - 1)p_{i}^{\alpha_{i}-1}$.
Ce qui implique $\big(\varphi(n)\big)^{n} = \big((p_{j} - 1)p_{j}^{\alpha_{j}-1}\prod_{i=0}^{r}(p_{i} - 1)p_{i}^{\alpha_{i}-1}\big)^{n}$
Et donc $\big(\varphi(n)\big)^{n}\equiv - 1\bmod n$ est impossible, car cela voudrait dire que \
$\big((p_{j} - 1)p_{j}^{\alpha_{j}-1}\prod_{i=0}^{r}(p_{i} - 1)p_{i}^{\alpha_{i}-1}\big)^{n} = - 1 + \beta p_{j}^{\alpha_{j}}\prod_{i=0}^{r}p_{i}^{\alpha_{i}}$, ce qui entrenerait que $p_{j}$ divise 1 (car $\alpha_{j}-1\geq 1$), ce qui est évidemment absurde.
On a montré par $a)$ et $b)$ que si $B(n)$ alors $n$ est premier.
C'est dire que $B(n)\,\implies\,P(n)\qquad (2)$.
$\bullet$ Maintenant si $D(n)$, alors $n = 1 + a\varphi(n),\,a\,\in\,\mathbb{N}^*$, et par suite $a$ et $n$ sont premiers entre eux (un facteur de $a$ et $n$ est un facteur de 1).
On a aussi que $\varphi(n)$ et $n$ doivent etre premiers entre eux, et donc $n$ est impair et sans carré (ce qui entraine que $n$ est un nombre de Carmichael).
$D(n)\,\implies\,a\varphi(n) = n - 1$, et donc $\big(a\varphi(n)\big)^{n} = (n - 1)^{n} \equiv - 1\bmod n$ (car $n$ impair).
On a alors $\big(a\varphi(n)\big)^{n} = a^{n}\big((\varphi(n)\big)^{n}\equiv a(\varphi(n))^{n}\equiv - 1\bmod n$
(car $n$ est un nombre de Carmichael).
Alors $\big((\varphi(n)\big)^{n}\equiv (- a)^{-n} = - (a^{-1})^{n}\equiv - a^{-1}\bmod n$.
Donc $a^{-1}\equiv (a^{-1})^{n}\bmod n$, ce qui implique $(a^{-1})^{n-1}\equiv 1\bmod n$, et donc
$(a^{-1})^{-1}\equiv a^{n-2}\bmod n$ et par suite $a^{n-3}\equiv 1\bmod n$.
On a donc $a^{n-3}\equiv a^{n-1}\bmod n$.
Alors $a^{n-3} - a^{n-1}\equiv 0\bmod n\,\implies\,a^{n-3}(1 - a^{2})\equiv 0\bmod n\,\implies\,a^{2}\equiv 1\bmod n$.
C'est dire que $a \equiv a^{-1}\bmod n$, et donc $a = 1$ où $a = n - 1$ (car $0\,\lt\,a\,\lt\,n$).
Mais comme on a $D(n)$, $a = n - 1$ est impossible, et donc $a = 1$, ce qui entraine $B(n)$ et $P(n)$.
C'est-à-dire :
$D(n)\,\implies\,B(n)$ et $D(n)\,\implies\,P(n)\qquad (3)$.
($(1),\,(2)$ et $(3)$) entraine $D(n)\,\iff\,B(n)\,\iff\,P(n)$.
D'où :
$\textrm{Théorème}$ :
$n > 1$ est premier, si et seulement si $n\equiv 1\bmod \varphi (n)$.
$n > 1$ est premier, si et seulement si $\big((\varphi(n)\big)^{n}\equiv - 1\bmod n$.
Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pourquoi : $(\varphi(n)\big)^{n}\equiv \varphi(n)\bmod n$ ?
Je suis peut-être déjà hors jeu, mais tu auras sûrement un argument convaincant.
Si $n=10$ alors $\big(\varphi(n)\big)^{n}=1048576$
Et $\varphi(10)=4$.
PS:
Avant de tenter de procéder à une démonstration on commence par tester numériquement ce qu'on veut démontrer.
Généralement, bien souvent, si la conjecture est fausse en quelques minutes on trouve un contre-exemple.
Mais est-ce que tu peux me sortir un contre exemple avec $n$ impair ? ou tout simplement de valuation 2-adique différent de $1$.
Merci.
$\varphi(15)=8$
$8^{15}=35184372088832\equiv 2[15]$
J'ai l'impression que tu affirmes que si $a\equiv b\mod{n}$ et $a'\equiv b'\mod{n'}$ avec $a,a',b,b'$ entiers et $n,n'$
entiers premiers entre eux alors on a aussi: $aa'\equiv bb'\mod{nn'}$
$3\equiv 1\mod{2}$ et $11\equiv 1 \mod{5}$ mais $33\equiv 3\mod{10}$
$n>1$ est premier si et seulement si $(n-1)!+1\equiv 0 [n]$ càd $(n-1)!=w.n-1$.
De plus, si $n$ est composé et différent de $4$ alors $(n-1)!\equiv 0[n]$.
J'explique.
Pour tout $n$, son $\varphi(n)$ est obtenu à partir de la décomposition de $n$ en facteurs premiers et en remplaçant chaque facteur $p^k$ par $(p-1)p^{k-1}$ où $p$ est premier.
Alors, pour obtenir un multiple de $n$ quand $n$ est composé, il suffit de multiplier $\varphi(n)$ par $(n-1)!$ pour remettre les facteurs $p$ manquants qui avaient été remplacés par des $(p-1)$. Mais ceci ne fonctionnera pas si $n$ est premier puisque $(n-1)(n-1)!$ ne sera pas multiple de $n$. Dans ce cas, on aura $(n-1)(n-1)!=(n-1).(w.n-1)=w.n^2-w.n-n+1\equiv 1[n]$ par Wilson.
Bref, on a obtenu :
a) $n>1$ est premier si et seulement si $\varphi(n)(n-1)!\equiv 1[n]$.
b) $n>1$ est composé si et seulement si $\varphi(n)(n-1)!\equiv 0[n]$.
Pour revenir à la conjecture de Lehmer :
a) c'est trivial que pour $n>1$ premier on a $\varphi(n)=n-1$ et donc $n=\varphi(n)+1\equiv 1[\varphi(n)]$
b) si $n>1$ est composé, alors on vient de voir que $\varphi(n)(n-1)!\equiv 0[n]$ càd $\varphi(n)(n-1)!=kn$ pour un certain $k$.
De plus, si $n$ n'est pas égal à $4$ alors $(n-1)!$ est multiple de $n$. Donc ce $k$ est aussi un multiple de $\varphi(n)$.
Reste à étudier précisément ce $k$ pour diviser le premier membre de l'égalité par ce $k$ et en déduire la conjecture.
Je crois que pour $n\ge 10$ qui n'est pas de la forme $2p$ avec $p$ premier, ce $k$ est même multiple de $n.\varphi(n)$.
....à suivre...
Si $a\equiv c \,[p_1]$ et $a\equiv c\, [p_2]$ et, $p_1$ et $p_2$ premiers entre eux, alors $a\equiv c\,[p_{1}p_{2}]$.
Mais je vois que c'est faux avec les contre-exemples (j'ai bien sur, bien vérifié pour pour $15$ @serge burckel !).
Mais ce que je signale ici et sur quoi vous ne revenez pas et que, c'est un argument qui a été utilisé dans la démo du théorème de Korselt dans le lien, et que je ne vois pas encore la différence d'hypothèses entre lui et moi.?
Sur la démonstration du théorème de Korselt que tu mentionnes.
On n'est pas dans la même configuration que tu décris plus haut.
On a $a^n\equiv a \mod{p_i}$ avec $p_i$ un diviseur premier de $n$ et les $p_i$ sont distincts
Dans ces relations c'est juste le module qui varie ce qui fait qu'on a bien que: $a^n\equiv a \mod{\text{produit des }p_i}$
C'est une conséquence de la propriété suivante:
si $m$ et $n$, premiers entre eux, divisent $a$ alors $mn$ divise $a$.
PS:
Avant de te lancer dans des calculs tu devrais songer à te cultiver un peu sérieusement en arithmétique élémentaire.
Il faut confronter son propre écrit et récrire exactement ce qu’il y a sur le lien.
L’un en dessous de l’autre on verra s’il s’agit de la même assertion.
***NB : poser le lien est super important bien sûr, mais là, dans cette discussion, comme l’assertion est courte, c’est important de les récrire toutes les deux.
Cliché du lien : il faut me montrer l’assertion qui serait la même que le second cliché.
Cliché de l’assertion : dans cette assertion, $n$ est un nombre premier (non ?)
Bien sur que la conjecture est vraie. Et je reviens bientôt, te donner la preuve sans cet argument faux qui m'a conduit en erreur. En fait à coté, il y beaucoup plus simple,..mais vous n'essayez pas d'être positifs et ça vous rend presque aveugle.
@Math Coss, l'erreur que j'ai faite n'a rien à voir avec $D(n)\,\implies\, B(n)$, et donc pour dire que la conjecture de Derrick Lehmer n'a pas été démontrée dans le post, il faut lire plus bas (là où je dis avoir prouvé que $D(n)\,\implies\, B(n)$ et $D(n)\,\implies\, P(n)$).
C'est bien la critique, mais elle peut être positive et non pas un subtil dénigrement ! abes
La première ligne qui a troublé mon esprit est tout au début « On a aussi ... ».
Tu es l’auteur, donc soit tu la supprimes et je continue à lire soit tu la démontres.
Pour ma part il ne s’agit pas d’être positif ou négatif.
C’est l’avantage des maths : on lit un texte et on le valide ou non.
Tu inventes des propriétés arithmétiques (qui sont hélas fausses) quand tu en as besoin. Ce n'est pas une simple erreur de calcul. Il n'y a aucun artifice du langage qui transforme un truc mathématique faux en quelque chose de vrai (si c'est ce genre de facilité que tu recherches deviens politicien).
La morale de l'histoire c'est à toi qu'elle revient.
PS:
Tu prétends démontrer des conjectures avec des outils qui ne sont pas nouveaux et qui sont très basiques. Soit.
Mais tu dois bien te douter que tu n'es pas le seul à avoir emprunter ce chemin*. Ce qui devrait te rendre très prudent et très précautionneux pour le moins.
*: personne n'a démontré ce type de résultat avec quelques additions et quelques divisions.
C'est quand même splendide, tu reconnais que tu n'as pas de démonstration actuellement, mais tu affirmes quand même que tu sais que la conjecture est vraie !
Ben c'est le principe des maths, on ne croit que ce qui est démontré. Pour l'instant c'est du vent.
Supposons $n$ composé avec des facteurs premiers $p_1,p_2,...p_k$ où chaque nombre premier $p_i$ a un exposant $k_i\ge 1$.
Alors $\varphi(n)p_1p_2...p_k$ est par définition de $\varphi(n)$ un multiple de $n$. En fait c'est même égal à $n(p_1-1)...(p_k-1)$.
Si on suppose par l'absurde de la conjecture que $(n-1)$ est un multiple de $\varphi(n)$, alors $(n-1)p_1...p_k$ devrait donc être un multiple de $\varphi(n)p_1p_2...p_k$ et donc de $n$.
Mais si la décomposition de $n$ contient un carré $p_i^{k_i}$ avec $k_i\ge 2$, c'est tout simplement impossible puisque $(n-1)$ ne peut pas avoir un facteur premier de $n$ qui pourrait éventuellement compléter un $p_i$ avec $k_i=2$. Une raison à cela :$pgcd(n,n-1)=1$.
Cela réduit les cas. Est-ce que cela aide un peu ?
Il reste le cas où $n$ est composé et égal à un produit de nombres premiers $p_1.p_2...p_k$ sans carrés.
Dans ce cas on a : $\varphi(n)=(p_1-1)(p_2-1)...(p_k-1)$...ce dernier cas est simple par induction sur $k$...non ?
(à suivre...)
@Fdp tu me parles de démonstration qu'un bon élève de seconde peut arriver à faire...basta !
@Poirot j'ai dit dans mon post précédent :
''@Math Coss, l'erreur que j'ai faite n'a rien à voir avec $D(n)\,\implies\,B(n)$, et donc pour dire que la conjecture de Derrick Lehmer n'a pas été démontrée dans le post, il faut lire plus bas (là où je dis avoir prouvé que $D(n)\,\implies\,B(n)$ et $D(n)\,\implies\,P(n)$.''
Donne-moi ton idée sur ça d'abord, avant que je ne parle d'autre chose.
@serge burckel on sait démontrer sans problème que $n$ est sans carré. C'est mème un nombre de Carmichael dans le cas dont tu parles. Il aut maintenant montrer que c'est un nombre premier.
Je répète avant de partir :
TU poses une preuve qui contient disons 50 lignes.
Je dis « je ne comprends pas la ligne 8 donc je ne continue pas, peux tu la préciser ? ».
Et toi, tu ne le fais pas. Et tu n’y es bien entendu pas obligé.
Mais moi j’en déduis que ton travail n’est pas sérieux.
Tes réponses aux autres sont similaires. Tu souhaites qu’on regarde ailleurs que là où on regarde.
Ça s’arrête là. C’est du bon Shtam, dans ses codes.
On ne peut pas dire « regardez ma preuve mais oubliez les petits tracas ici et là, inutile de me les montrer car je ne développerai pas » et s’attendre à de la coopération.
Bon courage.
Il m'a fallu moins de cinq minutes pour repérer deux trucs dont l'un était faux (contre-exemple à l'appui) et un autre truc non justifié et je sentais bien l'utilisation d'une propriété imaginaire (fausse).
Si je croyais détenir la preuve d'une telle conjecture je passerais beaucoup de temps pour être bien sûr de mon fait (vérification sans concession de tout jusqu'au moindre détail) pour ne pas me ridiculiser. Je n'aime pas me retrouver dans le rôle du bouffon quand mon intention est qu'on me prenne au sérieux. (pour être pris au sérieux il faut être sérieux soi-même).
Evidemment cela prend du temps et cela demande un effort qui peut être considérable si la preuve est très longue.
Pour finir, mon avis est que tout ceci est une perte de temps qui n'apporte rien (à part tuer l'ennui peut-être) à celui qui s'y consacre mais je sais que ne vais pas convaincre.
Mais la ligne 8 dont tu parles, c'est d'après le petit théorème de Fermat...
Celui qui démontrera vraiment cette conjecture ne va pas faire dix lignes sur cette trivialité (je parle du sens direct)
Je ne comprends pas ce que tu insinues par là. On parle de $\big(\varphi(n)\big)^{n}\equiv \varphi(n)\,[n]$.
Si $n$ est premier alors $n\equiv 1\bmod \varphi (n)$ (pour la raison indiquée au dessus).
C'est la réciproque qui n'est pas une trivialité apparemment.
PS:
Consacrer autant de lignes dans la démonstration d'une conjecture comme celle-ci à des trivialités est suspect.
Derrick Lehmer a dit que:
Conjecture :
$n > 1$ est premier, si et seulement si $n\equiv 1\bmod \varphi (n)$.
Preuve:
Soient les trois assertions quantifiées par $n$ suivantes.
$P(n)$ := ''$n$ est un nombre premier''.
$D(n)$ := ''$n\equiv 1\bmod \varphi(n)$''.
$B(n)$ := ''$(\varphi(n)\big)^{n}\equiv - 1\bmod n$''
Montrons que $P(n)\,\iff\,D(n)\,\implies\,B(n)$.
$\bullet$ Si $P(n)$ alors, $n$ est un nombre premier, et donc $\varphi(n) = n - 1$.
Mais $\varphi(n) = n - 1\implies n\equiv 1\bmod \varphi(n)\implies D(n)$.
C'est dire que $P(n)\,\implies\,D(n)\qquad (1)$.
On a aussi (d'après le petit théorème de Fermat)
$(\varphi(n)\big)^{n}\equiv \varphi(n)\bmod n$ or $\varphi(n) = n - 1$
et donc $(\varphi(n)\big)^{n}\equiv n - 1\bmod n \equiv - 1\bmod n$ d'où $B(n)$.
C'est dire que $P(n)\,\implies\,B(n)$.
$\bullet$ Si $D(n)$, alors $n = 1 + a\varphi(n),\,a\,\in\,\mathbb{N}^*$, et par suite $a$ et $n$ sont premiers entre eux (un facteur de $a$ et $n$ est un facteur de 1).
On a aussi que pour la raison similaire $\varphi(n)$ et $n$ doivent etre premiers entre eux, et donc $n$ est impair et sans carré (ce qui entraine que $n$ est un nombre de Carmichael, d'après le théorème de Korselt).
$D(n)\,\implies\,a\varphi(n) = n - 1$, et donc $\big(a\varphi(n)\big)^{n} = (n - 1)^{n} \equiv - 1\bmod n$ (car $n$ impair).
On a alors $\big(a\varphi(n)\big)^{n} = a^{n}\big((\varphi(n)\big)^{n}\equiv a(\varphi(n))^{n}\equiv - 1\bmod n$
(car $n$ est un nombre de Carmichael).
Alors $\big((\varphi(n)\big)^{n}\equiv (- a)^{-n} = - (a^{-1})^{n}\equiv - a^{-1}\bmod n$.
Mais $a^{n-1}\equiv 1\bmod n$, donc $a^{-1}\equiv a^{n-2}\bmod n$.
Alors $ (- a)^{-n} = - (a^{-1})^{n}\equiv - a^{-1}\equiv - a^{n-2}\bmod n$, et donc $a^{n-2}\equiv a^{-n}\bmod n$.
C'est-à-dire $a^{n-1}\equiv a^{1-n}\bmod n$
C'est dire que $a \equiv a^{-1}\bmod n$, et donc $a = 1$ où $a = n - 1$ (car $0\,\lt\,a\,\lt\,n$).
Mais comme on a $D(n)$, $a = n - 1$ est impossible, et donc $a = 1$, ce qui entraine $B(n)$ et $P(n)$.
C'est-à-dire :
$D(n)\,\implies\,B(n)$ et $D(n)\,\implies\,P(n)\qquad (2)$.
($(1)$ et $(2)$) entraine $P(n)\,\iff\,D(n)\,\implies\,B(n)$.
D'où :
Théorème :
$n > 1$ est premier, si et seulement si $n\equiv 1\bmod \varphi (n)$.
Tu déduis je ne sais comment que $n$ est impair et sans carré.
Pourtant le "raisonnement" que tu penses faire doit s'appliquer aussi, me semble-t-il, à $n=2$.
En effet, $\varphi(2)=1$ on a donc bien que $2\equiv 1 \mod{\varphi(2)}$.
Pas la peine de rajouter un truc pour traiter le cas de $n=2$ à part, le problème pour moi à cet endroit est pourquoi $n$ devrait être impair?
Mais de toute façon j'avais fait la démonstration sans cette remarque sur les nombres de Carmichael. Je tu l'exiges je l'envoie..
Tu ne réponds pas à ma question.
Ton hypothèse de départ dans cette partie de ta "démonstration" est: $n\equiv 1\bmod \varphi(n)$ (aucune précision sur $n$)
Pour $n=2$, par exemple, cette hypothèse est vérifiée. Donc je ne vois pas comment tu arrives à la conclusion (fausse) que $n$ doit être impair.
Mais voici @Fdp la preuve que tu demandes. Je l'ai fait en large parce que je pense que j'ai pas besoin de le mettre dans ma démonstration de la conjecture.
Si $n\equiv 1\bmod \varphi (n)$, alors $n = 1 + k\varphi (n),\, k\in\mathbb{N^*}\;(1)$
Posons $n = \prod_{i=1}^{r}p_{i}^{r_{i}},\, r\in\mathbb{N^*}$.
Alors $\varphi (n) = \prod_{i=1}^{r}(p_{i}^{r_{i}} - p_{i}^{r_{i}-1}) = \prod_{i=1}^{r}(p_{i} - 1)p_{i}^{(r_{i}-1)}$.
Mais alors:
$\begin{align} (1)\,&\iff\,\prod_{i=1}^{r}p_{i}^{r_{i}} = 1 + k\prod_{i=1}^{r}(p_{i} - 1)p_{i}^{(r_{i}-1)}
&\iff\,\prod_{i=1}^{r}p_{i}^{r_{i}} - k\prod_{i=1}^{r}(p_{i} - 1)p_{i}^{(r_{i}-1)} = 1\,
&\iff\,\prod_{i=1}^{r}p_{i}^{(r_{i} - 1)}(\prod_{i=1}^{r}p_{i} - k\prod_{i=1}^{r}(p_{i} - 1)) = 1\end{align}$.
Mais,
$\prod_{i=1}^{r}p_{i}^{(r_{i} - 1)}$ est un entier positif, alors cette dernière égalité est possible si et seulement si,
$\prod_{i=1}^{r}p_{i}^{(r_{i} - 1)} = 1\,\textrm{et}\,\prod_{i=1}^{r}p_{i} - k\prod_{i=1}^{r}(p_{i} - 1) = 1$.
Mais $\prod_{i=1}^{r}p_{i}^{(r_{i} - 1)} = 1 \,\Rightarrow\, r_{i} - 1 = 0,\,\textrm{c'est à dire},\,r_{i} = 1\,\forall\,i\in[\![1; r]\!] $.
Alors $n = \prod_{i=1}^{r}p_{i},\,\textrm{et}\,\prod_{i=1}^{r}p_{i} - k\prod_{i=1}^{r}(p_{i} - 1) = 1,\,\textrm{avec},\;r\;\textrm{et}\; k\;\in\mathbb{N^*} $
Supposons $n$ pair; c'est à dire qu'il a $2$ comme facteur, et donc $n = 2\times \prod_{i=1}^{(r-1)}p_{i}$ (à l'ordre des facteurs près)
Mais alors $n - k\varphi (n) = 2\times \prod_{i=1}^{(r-1)}p_{i} - k.\prod_{i=1}^{(r-1)}(p_{i} - 1) = 1$, ce qui n'est possible que
si:$k.\prod_{i=1}^{(r-1)}(p_{i} - 1)$ est impair (la différence de deux entiers pairs est pair, donc $\neq 1$).
Donc $n$ ne contient aucun facteur impair, et alors $n = 2$ est premier.
Remarque : On pouvait, pour avoir le résultat précédent, seulement remarquer qu'un entier $n = \prod_{i=1}^{r}p_{i}$, $p_{i}$ premier pour tout $i$, qui vérifie l'égalité $(1)$, est premier ou est un nombre de Carmichael (donc impair, ayant au moins trois facteurs s'il n'est pas premier).
Théorème (Korselt 1899) .
Un entier positif composé $n$ est un nombre de Carmichael si et seulement si
aucun carré de nombre premier ne divise $n$ (on dit que $n$ est sans facteur carré) et
pour chaque diviseur premier $p$ de $n$, le nombre $p-1$ divise $n-1$.
De plus, un tel $n$ divise tous les $a^n-a$ (même pour $a$ non premier à $n$).
(*) Il découle de ce théorème que tous les nombres de Carmichael sont des produits d'au moins trois nombres premiers différents.
La propriété (*) est une condition nécessaire...mais pas suffisante pour être un nombre de Carmichael...c'est juste ?
Juste pour apporter une petite contribution (peut-être inutile)...je continue (pour la forme) l'étude des cas que j'avais commencée.
J'en étais au dernier cas : celui des nombres composés sans carrés $n=p_1p_2...p_k$ avec $k\ge 2$ et tous les $p_i$ sont différents.
1. Pour $k=2$, on pose $n=p.q$ avec $p<q$ où $p,q$ sont des nombres premiers.
1.1. Si $p=2$ alors $n=2q$ et $\varphi(n)=(q-1)$ et $n-1=2q-1=2(q-1)+1=2\varphi(n)+1$.
Donc c'est ok : $n-1$ n'est pas multiple de $\varphi(n)$.
1.2. Si $p>2$ alors $n=pq$ et $\varphi(n)=(p-1)(q-1)$ et $n-1=\varphi(n)+p+q-2$.
C'est assez facile de voir que $0<p+q-2<\varphi(n)=(p-1)(q-1)$.
C'est encore ok : $n-1$ est encore de la forme $a\varphi(n)+b$ avec $0<b<\varphi(n)$.
2. Il ne reste plus que le cas où $k\ge 3$.
Donc, ton dernier post qui commence par <<Tu me parles...>> affirme contenir ce qu'il faut comme preuve pour compléter. Oui ?
Si c'est le cas, cela semble compréhensible, lisible et vérifiable.
Pour ma part, j'ai essayé de contribuer un peu et de proposer aussi des approches simples.
Si cela te permet d'obtenir une preuve complète et simple, c'est très bien.
Je ne vois comment tu obtiens cette équivalence. Pourquoi $a^n\equiv a \bmod n$ ? Cette équivalence est vraie si $n$ est premier mais là on n'a pas supposé $n$ premier...
Il semble clair que sa dernière version se passe de ces détours inutiles et qu'elle parait plus correcte, simple, complète et synthétique dans cette forme. Reste à vérifier méticuleusement chaque point (et l'esprit qu'il contient ;-)).
On peut donc attendre que @babsgueye confirme cela, qu'il reconnaisse ces erreurs initiales et aussi que des membres de ce forum l'ont, chacun à sa manière, motivé pour trouver la voie de la simplification et de la clarté pour les convaincre.
@serge burckel, j'ai déjà reconnu cette erreur dans mes messages précédents.
@Fdp parfois je poste trop rapidement, c'est pas une raison mais je sais qu'en maths en général, et dans ce forum en particulier, les acteurs ne laissent pas passer les erreurs.
@raoul. S $a^{n} = a\bmod n$ est du au fait que $n$ est un nombre de Carmichael. C'est dit dans le théorème de Korselt.
je continue à lire ta preuve ici http://www.les-mathematiques.net/phorum/read.php?43,2137890,2138512#msg-2138512 et à un moment tu dis :
ce "et donc" m'échappe, tu peux expliquer ?
je prends $a=2$ et $n=3$. À gauche j'obtiens $\big(a^{-1}\big)^{n-1}=(2^{-1})^2=\dfrac{1}{4}$ tandis qu'à droite j'obtiens $(a^{-1})(a^{n-2})=(2^{-1})(2^{1})=1$.
Il y a un problème on dirait...
Je pense que l'inverse c'est dans le corps $Z/nZ$ (si $n$ premier).
Donc $2^{-1}=2$ (et pas $1/2$) puisque $2.2=4=1$ dans ce corps.
Bon ok alors autre exemple numérique $a=2$ et $n=5$ : selon babsgueye on devrait avoir $\big(a^{-1}\big)^{n-1} \equiv (a^{-1})(a^{n-2}) \bmod n$
à gauche j'obtiens $\big(a^{-1}\big)^{n-1} \equiv \big(2^{-1}\big)^{4} \equiv 1 \bmod 5$
à droite j'obtiens $(a^{-1})(a^{n-2}) \equiv (2^{-1})(2^{3}) \equiv 4 \bmod 5$
@babsgueye je n'obtiens pas la même chose.
Merci.
PS : j'ai rectifié sur mon précédent message.