Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
199 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Nombre premier

Envoyé par Mathieu 
Nombre premier
il y a treize années
<latex> 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 :)
Re: Nombre premier
il y a treize années
<latex> 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.
Re: Nombre premier
il y a treize années
avatar
Ca pourrait faire un bel exo sur le serveur, non ?
bob
Re: Nombre premier
il y a treize années
Oui c'est joli Mathieu. Bravo!

bob
Re: Nombre premier
il y a treize années
Mathieu,la démonstration est faite comment ?

ptitloupfouchou
Re: Nombre premier
il y a treize années
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="[www.les-mathematiques.net]; ALT="$ 1&lt;k&lt;n$"></SPAN> <BR> <BR><SPAN CLASS="MATH"><IMG WIDTH="165" HEIGHT="50" ALIGN="MIDDLE" BORDER="0" SRC="[www.les-mathematiques.net]; 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>
Re: Nombre premier
il y a treize années
<latex> 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.
Re: Nombre premier
il y a treize années
avatar
<latex> 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 ? smiling smiley

Sylvain
Re: Nombre premier
il y a treize années
<latex> 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.
Re: Nombre premier
il y a treize années
avatar
<latex> 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
Re: Nombre premier
il y a treize années
avatar
Bon allez, puisque personne ne se dévoue je propose l'exercice initial sur le serveur .
Re: Nombre premier
il y a treize années
<latex> 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 ?
Re: Nombre premier
il y a treize années
<latex> 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 !).
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 139 162, Messages: 1 353 828, Utilisateurs: 25 110.
Notre dernier utilisateur inscrit Rapha.


Ce forum
Discussions: 5 169, Messages: 62 651.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page