Nombre premier

Mathieu · July 2006

Bonjour,

Je viens de trouver et démontrer un résultat intéressant bien qu' il soit apparemment inexploitable.
Il a déjà surement été démontré mais voila:

soit $n \in \N^*$

$n$ est premier si et seulement si $\displaystyle{ \sum_{k=1}^{n-1} [E(\frac{n}{k}) - E(\frac{n-1}{k})] = 1}$ où $E$ désigne la partie entière.

C' est fou ce qu' on peut trouver comme formules sur les nombres premiers

borde · July 2006

Ce résultat pourrait presque être utilisé (en théorie) comme "fonction indicatrice" des nombres premiers (pas exactement, toutefois), tout comme la fonction $\displaystyle {1_{\mathcal {P}}(n) = 1 + \left [ \frac {2 - \tau(n)}{n} \right ]}$ (avec $n \geqslant 2$ entier) qui vaut $1$ (resp. $0$) si $n$ est (resp. n'est pas) premier.

Néanmoins, la différence des parties entières et l'estimation grossière de cette différence par $\displaystyle {\frac {1}{k} + O(1)}$ risque de ne faire de cette formule qu'un bel exemple théorique. Mais nul doute que ce résultat plaira à bon nombre d'intervants du forum.

Borde.

Le barbu rasé · July 2006

Ca pourrait faire un bel exo sur le serveur, non ?

bob · July 2006

Oui c'est joli Mathieu. Bravo!

bob

Yalcin · July 2006

Mathieu,la démonstration est faite comment ?

ptitloupfouchou · July 2006

Le truc de gauche est égal a 1 si et seulement si pour tout entier <IMG WIDTH="72" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/9/92638/cv/img1.png" ALT="$ 1<k<n$">
 
 <IMG WIDTH="165" HEIGHT="50" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/9/92638/cv/img2.png" ALT="$ \displaystyle [E(\frac{n}{k}) - E(\frac{n-1}{k})] = 0$">
 
 et on voit clairement que c'est équivalent à dire que n n'est pas un multiple de k d'ou le résultat il me semble.

Mathieu · July 2006

En fait, ce résultat provient d' un résultat un peu plus général que j' ai démontré:
Soit $n \in \N^{*}$
On note $D(n)$ le nombre de diviseurs de $n$

Alors $\displaystyle{D(n) = 1 + \sum_{k=1}^{n-1} [ E(\frac{n}{k}) - E(\frac{n-1}{k})]}$

Donc $n$ est premier si et seulement si $D(n) = 2$

Ce qui s' écrit également $\displaystyle{\sum_{k=1}^{n} E(\frac{n}{k}) = \sum_{k=1}^{n-1} E(\frac{n-1}{k})}$

J' ai tracé la courbe représentative de $D$ sous maple (en considérant $\displaystyle{D(x) = 1 + \sum_{k=1}^{E(x)-1} [ E(\frac{E(x)}{k}) - E(\frac{E(x)-1}{k})]}$ )
Et la courbe est très chaotique, mais semble "ne jamais aller très haut" comparé à la taille des nombres.
On peut majorer $D(n)$ par $\displaystyle{1 + n + \sum_{k=1}^{n} \frac{1}{k}}$ mais c' est une majoration grossière, ce qui est du aux parties entières.
J' essaie de trouver un équivalent de $D(n)$ mais je n' y arrive pas.

La démonstration de l' écriture de $D(n)$ n' est pas longue (1 page), je la met dès que j' ai le temps.

Mathieu · July 2006

Petite erreur à la 6eme ligne: ce n' est pas $\displaystyle{\sum_{k=1}^{n} E(\frac{n}{k}) = \sum_{k=1}^{n-1} E(\frac{n-1}{k})}$ mais $\displaystyle{ \sum_{k=1}^{n-1} [E(\frac{n}{k}) - E(\frac{n-1}{k})] = 1}$

Sylvain · July 2006

Pas grand-chose à voir (quoique...): Il serait intéressant de tracer la courbe $Ord_{P}(x)$, où $Ord_{P}(n)$ désigne ce que j'appelle "l'ordre de primalité" de $n$.
Exemple: $7=p(4)$ et $4$ est composé, on a appliqué une fois la fonction $p$ qui à $n$ associe le $n$-ième nombre premier, donc on dira que $7$ est {\bf d'ordre de primalité 1}.
De même $67=p(19)=p(p(8))$, $8$ est composé, on a appliqué deux fois la fonction $p$, donc $67$ est {\bf d'ordre de primalité 2}.

Ce genre de classification des entiers devrait, je pense, s'avérer utile.

Qu'en pense l'ami Borde ? :-)

Sylvain

Sylvain · July 2006

Pas grand-chose à voir (quoique...): Il serait intéressant de tracer la courbe $Ord_{P}(x)$, où $Ord_{P}(n)$ désigne ce que j'appelle &quotl'ordre de primalité" de $n$.
Exemple: $7=p(4)$ et $4$ est composé, on a appliqué une fois la fonction $p$ qui à $n$ associe le $n$-ième nombre premier, donc on dira que $7$ est {\bf d'ordre de primalité 1}.
De même $67=p(19)=p(p(8))$, $8$ est composé, on a appliqué deux fois la fonction $p$, donc $67$ est {\bf d'ordre de primalité 2}.

Ce genre de classification des entiers devrait, je pense, s'avérer utile.

Qu'en pense l'ami Borde ? :-)

Sylvain

borde · July 2006

Mathieu a dit : "la courbe de la fonction $D$ (en fait réellement notée $\tau$ ou $d$) semble ne jamais aller très haut par rapport aux entiers".

{\it Et pour cause} : si $\tau$ désigne la fonction nombre de diviseurs, on a les propriétés suivantes :

(i) Pour tout $\varepsilon > 0$, on a $\tau(n) \ll_{\varepsilon} n^{\varepsilon}$ ({\it Référence} : mon livre, exercice 4.4 page 125).

(ii) {\bf L'ordre normal} de la fonction $\tau$ est $(\ln n)^{\ln 2}$. Autrement dit, pour un ensemble d'entiers naturels {\bf de densité} $1$, on a : $$\tau(n) = (\ln n)^{\ln 2 + o(1)}.$$

(iii) {\bf L'ordre moyen} de la fonction $\tau$ est $\ln n + 2 \gamma -1$. Autrement dit, pour tout entier naturel $n \geqslant 1$, on a : $$\frac {1}{n} \sum_{k \leqslant n} \tau(k) \sim \ln n + 2 \gamma -1.$$

Sylvain : j'ai compris ta notion, mais il faudrait que tu précises l'idée que tu as en tête. Par exemple, que peut nous apporter le renseignement qui précise que $67$ est d'ordre de primalité 2 ?

Borde.

Sylvain · July 2006

Borde: je n'ai pas d'idée précise en tête pour le moment ! A vrai dire, je pense qu'on pourrait peut-être envisager de construire un certain ensemble d'entiers avec des polynômes formels (c'est-à-dire des expressions du style $\displaystyle{\sum_{k=0}^{m}p^{(k)}}$), considérés comme des fonctions. Je m'intéresse un peu en ce moment aux extensions de corps et tutti quanti, alors peut-être peut-on faire des parallèles intéressants avec l'algèbre ("indépendance linéaire" de nombres d'ordres de primalité différents, je ne sais pas si tu vois ce que je veux dire). Désolé si je suis vague, mais il faut le temps que ça décante...
Observation amusante: $67$ et $17$ sont d'ordre de primalité $2$ et on a:
$$E((67)^{1/2})=8=\pi^{(2)}(67)$$
$$E((17)^{1/2})=4=\pi^{(2)}(17)$$

Peut-on généraliser ?

Sylvain

Le barbu rasé · July 2006

Bon allez, puisque personne ne se dévoue je propose l'exercice initial sur le serveur .

Mathieu · July 2006

Allez voici la méthode que j' ai utilisé:

Soit $d(k)$ le nombre diviseurs de $k$

Soit $\displaystyle{S_n = \sum_{k=1}^{n} d (k)}$

On voit aussi que $\displaystyle{S_n = \sum_{i=1}^{n} s (i)}$ où $s(i)$ est le nombre de fois où $i$ est un diviseur d' un nombre entre $1$ et $n$.

$s(i) = card A$ où $A = \{1..n\} \cap i \Z$

On en déduit que $\displaystyle{s(i) = E (\frac{n}{i})}$

Comme $d(n) = S_n - S_{n-1}$

On a $\displaystyle{d(n) = 1 + \sum_{k=1}^{n-1} [E(\frac{n}{k}) - E(\frac{n-1}{k})]}$

$n$ est premier si et seulement si $\displaystyle{d(n) = 2}$
D' où le résultat.

---
"Autrement dit, pour un ensemble d'entiers naturels de densité $1$" ca veut dire quoi ?

borde · July 2006

La démarche est correcte, mais peut être simplifiée par la méthode suivante (je vais tenter de reprendre toutes tes noltations) : puisque $\displaystyle {d(n) = \sum_{d \mid n} 1}$, alors on a : $$S_n = \sum_{k \leqslant n} \sum_{d \mid k} 1} = \sum_{d \leqslant n} \sum_{k \leqslant n/d} 1 = \sum_{d \leqslant n} \left [ \frac {n}{d} \right ],$$ où la seconde égalité provient d'une interversion des sommation. On conclut ensuite, comme tu le fais, avec $d(n) = S_n - S_{n_1}$.

Cette méthode (cf th 4.24 de mon livre) est extrêmement utilisée en théorie analytique des nombres.

Enfin, l'expression "pour un ensemble d'entiers de densité 1" signifie que, si $E$ est l'ensemble considéré, alors, pour tout réel $x \geqslant 1$, on a $$\sum_{n \leqslant x, \, n \in E} 1 = x(1+o(1)).$$

Salut Sylvain,

Des parallèles comme tu l'évoques ont déjà été étudié, en particulier en théorie transcendentale des nombres, où la $\Q-$dépendance linéaire est très présente. Mais c'est bien : continue à avoir des idées, cela développe le goût pour la recherche...

Borde.

borde · July 2006

La démarche est correcte, mais peut être simplifiée par la méthode suivante (je vais tenter de reprendre toutes tes noltations) : puisque $\displaystyle {d(n) = \sum_{d \mid n} 1}$, alors on a : $$S_n = \sum_{k \leqslant n} \sum_{d \mid k} 1} = \sum_{d \leqslant n} \sum_{h \leqslant n/d} 1 = \sum_{d \leqslant n} \left [ \frac {n}{d} \right ],$$ où la seconde égalité provient d'une interversion des sommation. On conclut ensuite, comme tu le fais, avec $d(n) = S_n - S_{n-1}$.

Cette méthode (cf th 4.24 de mon livre) est extrêmement utilisée en théorie analytique des nombres.

Enfin, l'expression "pour un ensemble d'entiers de densité 1" signifie que, si $E$ est l'ensemble considéré, alors, pour tout réel $x \geqslant 1$, on a $$\sum_{n \leqslant x, \, n \in E} 1 = x(1+o(1)).$$

Salut Sylvain,

Des parallèles comme tu l'évoques ont déjà été étudié, en particulier en théorie transcendentale des nombres, où la $\Q-$dépendance linéaire est très présente. Mais c'est bien : continue à avoir des idées, cela développe le goût pour la recherche...

Borde (doublon à supprimer. Cela faisait longtemps, ça doit être la défaite de l'équipe de France ! Merci, en tout cas !).

Nombre premier

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 7