Nombre premier

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 :)

Réponses

  • 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.
  • Ca pourrait faire un bel exo sur le serveur, non ?
  • Oui c'est joli Mathieu. Bravo!

    bob
  • Mathieu,la démonstration est faite comment ?
  • Le truc de gauche est égal a 1 si et seulement si pour tout entier <SPAN CLASS="MATH"><IMG WIDTH="72" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/9/92638/cv/img1.png&quot; ALT="$ 1<k<n$"></SPAN>
    <BR>
    <BR><SPAN CLASS="MATH"><IMG WIDTH="165" HEIGHT="50" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/07/9/92638/cv/img2.png&quot; ALT="$ \displaystyle [E(\frac{n}{k}) - E(\frac{n-1}{k})] = 0$"></SPAN>
    <BR>
    <BR>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.<BR>
  • 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.
  • 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}$
  • 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
  • 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
  • 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.
  • 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
  • Bon allez, puisque personne ne se dévoue je propose l'exercice initial sur le serveur .
  • 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 ?
  • 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.
  • 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 !).
Connectez-vous ou Inscrivez-vous pour répondre.