Preuve de la conjecture de Derrick Lehmer

Poirot

De quelle conjecture parles-tu ?

Dom

Ce doit être un truc du genre :

« J’ai démontré 1+1=3
Preuve : comme 1+1=2 alors en on voit bien que ça entraîne 1+1=3.
Moi au moins je partage mes découvertes. Et si on me montre une erreur, je l’admets.
»

Joyeux Noël !

babsgueye

Non @Dom, ce n'est pas un résultat génial génial, mais ça a son importance mathématique. C'est du genre : $B(n)\,\iff\,P(n)$, si tu as lu le fil.

Merci, à toi aussi.

babsgueye

Bonsoir.
Je rouvre ici un vieux fil.
Pour ne pas obliger à lire les post précédents car je propose une nouvelle approche, je reprends l'introduction sur le sujet. Je propose à la critique cette nouvelle approche que je pense être une réponse à la question.

INTRODUCTION

On sait que tout nombre entier naturel, se décompose de manière unique à l'ordre des facteurs près, en produit de nombres premiers.

En mathématiques, l'indicatrice d'Euler(*) est une fonction arithmétique de la théorie des nombres, qui a tout entier naturel non nul, associe 

le nombre d'entiers compris entre 1 et n (inclus) et premiers avec n.

Elle intervient en mathématiques pures, à la fois en théorie des groupes, en théorie algébrique des nombres et en théorie analytique des 

nombres.

En mathématiques appliquées, à travers l'arithmétique modulaire, elle joue un role important en théorie de l'information et plus 

particulièrement en cryptologie.

La fonction indicatrice est aussi appelée indicateur d'Euler, fonction phi d'Euler ou simplement fonction phi, car la lettre $\varphi$ est 

communément utilisée pour la désigner.

Elle est nommée en l'honneur du mathématicien suisse Leonard Euler, qui fut le premier à l'étudier.

Derrick Lehmer a énoncé que:

CONJECTURE:

Un nombre entier $n > 1$ est premier, si et seulement si $n\equiv 1\bmod \varphi (n)$.

PREUVE DE LA CONJECTURE

$\bullet$ Montrons $\,\Rightarrow$)

Si n est premier, alors $\varphi (n) = n - 1 \iff n = 1 + \varphi (n)$ donc $n\equiv 1\bmod \varphi (n)$.

$\bullet$ Montrons $\,\Leftarrow$)

Si $n\equiv 1\bmod \varphi (n)$, alors $n = 1 + a\varphi (n),\, a\in\mathbb{N^*}\quad(1)$

Posons $n = \prod_{i=1}^{r}p_{i}^{r_{i}},\, r\in\mathbb{N^*}$. 

Alors $\varphi (n) = \displaystyle\prod_{i=1}^{r}(p_{i}^{r_{i}} - p_{i}^{r_{i}-1}) = \displaystyle\prod_{i=1}^{r}(p_{i} - 1)p_{i}^{(r_{i}-1)}$.

Mais alors:

$(1)\iff\,\displaystyle\prod_{i=1}^{r}p_{i}^{r_{i}} = 1 + a\displaystyle\prod_{i=1}^{r}(p_{i} - 1)p_{i}^{(r_{i}-1)}$

Ce qui équivaut à : $\displaystyle\prod_{i=1}^{r}p_{i}^{r_{i}} - a\prod_{i=1}^{r}(p_{i} - 1)p_{i}^{(r_{i}-1)} = 1$

C'est à dire $\displaystyle\prod_{i=1}^{r}p_{i}^{(r_{i} - 1)}(\displaystyle\prod_{i=1}^{r}p_{i} - a\displaystyle\prod_{i=1}^{r}(p_{i} - 1)) = 1\quad (2)$.

Mais,

$\displaystyle\prod_{i=1}^{r}p_{i}^{(r_{i} - 1)}$ est un entier positif, alors l'égalité $(2)$ est possible si et seulement si,

$\displaystyle\prod_{i=1}^{r}p_{i}^{(r_{i} - 1)} = 1\,\textrm{et}\,\displaystyle\prod_{i=1}^{r}p_{i} - a\displaystyle\prod_{i=1}^{r}(p_{i} - 1) = 1$.

Mais $\displaystyle\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 = \displaystyle\prod_{i=1}^{r}p_{i},\,\textrm{et}\,\displaystyle\prod_{i=1}^{r}p_{i} - a\displaystyle\prod_{i=1}^{r}(p_{i} - 1) = 1,\,\textrm{avec},\;r\;\textrm{et}\; a\;\in\mathbb{N^*}$

1er cas:

Supposons $n$ pair; c'est à dire qu'il a $2$ comme facteur, et donc $n = 2\times \displaystyle\prod_{i=1}^{(r-1)}p_{i}$ (à l'ordre des facteurs près).

Mais alors $n - a\varphi (n) = 2\times \prod_{i=1}^{(r-1)}p_{i} - a\displaystyle\prod_{i=1}^{(r-1)}(p_{i} - 1) = 1$, ce qui n'est possible que 

si $a\displaystyle\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.

2eme cas:

Supposons $n$ impair.

Si $r = 1$ alors $n = p_{1}$ est premier.

Sinon $n$ est sans carré, et donc $n = \displaystyle\prod_{i=1}^{r}p_{i}$ avec $r\geq 2$.

$n\equiv 1\bmod \varphi (n)$, alors $n = 1 + a\varphi (n),\, a\in\mathbb{N^*}\quad (3)$

C'est dire que $n - 1 = a\displaystyle\prod_{i=1}^{r}(p_{i} - 1)\quad (4)$. Notons toute de suite qu'alors $\forall i\in [\![1, r]\!],],\,p_{i} - 1$ est premier avec $p_{j}\forall j\in [\![2, r]\!]$.

On sait aussi que $n = \displaystyle\sum_{d/n}\varphi (d)$.
Soit $n = 1 + \displaystyle\sum_{i=1}^{r}(p_{i} - 1) + \displaystyle\sum_{1\leq i\lt j\leq r}^{r}(p_{i} - 1)(p_{j} - 1) + \displaystyle\sum_{1\leq i\lt j\lt k\leq r}^{r}(p_{i} - 1)(p_{j} - 1)(p_{k} - 1) + \cdots + \displaystyle\prod_{i=1}^{r}(p_{i} - 1)\quad (5)$.

$(4)$ et $(5)$ impliquent :
$a\displaystyle\prod_{i=1}^{r}(p_{i} - 1) = \displaystyle\sum_{i=1}^{r}(p_{i} - 1) + \displaystyle\sum_{1\leq i\lt j\leq r}(p_{i} - 1)(p_{j} - 1) + \displaystyle\sum_{1\leq i\lt j\lt k\leq r}(p_{i} - 1)(p_{j} - 1)(p_{k} - 1) + \cdots + \displaystyle\prod_{i=1}^{r}(p_{i} - 1)$

Ce qui implique $\big((a - 1)p_{1} - a\big)\displaystyle\prod_{i=2}^{r}(p_{i} - 1) = (p_{1} - 1)A + A$, où on a posé :
$A = \displaystyle\sum_{i=2}^{r}(p_{i} - 1) + \displaystyle\sum_{1\lt i\lt j\leq r}(p_{i} - 1)(p_{j} - 1) + \displaystyle\sum_{1\lt i\lt j\lt k\leq r}(p_{i} - 1)(p_{j} - 1)(p_{k} - 1) + \cdots + \displaystyle\sum_{i=2}^{r}\displaystyle\prod_{j=2, j\neq i}^{r}(p_{j} - 1)$

C'est à dire que : $\big((a - 1)p_{1} - a\big)\displaystyle\prod_{i=2}^{r}(p_{i} - 1) = p_{1}A$

Mais étant donné que $p_{1}$ est premier avec $\displaystyle\prod_{i=1}^{r}(p_{i} - 1)$ alors $p_{1}$ divise $(a - 1)p_{1} - a$, d'où $p_{1}$ divise $a$.

Ce qui est contradictoire avec $(3)$. Donc $r = 1$ et $n = p_{1}$ est premier.

$Theoreme$ :

Un nombre entier $n > 1$ est premier, si et seulement si $n\equiv 1\bmod \varphi (n)$.

Je pense quand même que la rédaction peut être améliorer par qui connait le sujet.

Cordialement.

PS : j'ai eu un problème avec ''align'' d'où la présentation..

Math Coss

Ça y est, ça repart. Des pseudo-démonstrations de conjectures difficiles, sans l'once d'une idée apparente, sans un seul ingrédient non trivial, bourrées d'erreurs fondamentales et qui deviennent de plus en plus difficiles à lire, jusqu'à ce que l'auteur ou les lectrices craquent. Prometteur.

babsgueye

@Math Coss je me suis débrouillé sans l'aide d'un administrateur pour clarifier. Mais s'il vous plait, il faut appuyer là où ça fait mal.

[Utilisateur supprimé]

Je rejoins @Math Coss dans son commentaire, retravaille ton texte et reposte le quand il sera suffisamment clair.

babsgueye

Je reprends ma phrase.  ''Il faut juste appuyer là où ça fait mal'', ça permettra d'avancer plus rapidement.

[Utilisateur supprimé]

Commençons par ceci, je n'ai pas compris ton (4), rédige le.
Édit. Non au fait ce serait bien de rédiger ce point mais aussi de le justifier. Et la formule qui suit mériterait d'être formalisée.

babsgueye

On a posé $n = \displaystyle\prod_{i=1}^{r}p_{i}$ (Auparavant on avait démontré que $n$ est sans de carré).
$n = 1 + a\varphi (n)$ est notre hypothèse de départ. $(4)$ vient tout simplement du fait que $\varphi (n) = \displaystyle\prod_{i=1}^{r}(p_{i} - 1)$.
En plus cette égalité implique que si $p_{j}$ divise $p_{i} -  1$, pour $i\in [\![1, r]\!]$, alors $p_{j}$ divise $1$.

PS. Excusez du temps mis avant le retour (indépendant de ma volonté).