Démonstration de l'ensemble des Nombres premiers

invite43bf475e · 14/07/2007, 18h17

Bonjour à tous!

Par cette belle journée, je rentre de la capitale après une aprem shopping ( c'es génial en effet), mais une question reste gravée dans moin esprit :
Tout le monde sait qu'en maths, il y n'y a pas qu'une seule méthode pour déterminer un résultat, mais Euclide a t-il utiliser une seule méthode pour démontrer que l'ensemble des nombres premiers est infini?

*Je la réexplique : (demo par l'absurde)

On suppose que l'ensemble IP des nombres premiers est un ensemble fini :
IP : {p1,p2,...,pn}
-Soit N, un entier naturel défini par N=p1xp2x...xpn + 1, N étant plus grand que n'importe quel élément de IP, N n'appartient pas à IP.
-De plus N $\text{[math]}$ 1, donc par définition, N possède au moins un diviseur premier p, élément de IP.
-p divise alors, à la fois p1xp2x...xpn, et N, donc p divise toute combinaison linéaire à coefficients entiers de ces deux nombres, et notamment leur différence, donc p divise 1. Ce qui absurde car p est premier, donc l'hypothèse posée sur IP est fausse, on en déduit qu'il existe une infinité de nombres premiers...

Une autre méthode?

invitec053041c · 14/07/2007, 18h28

Il doit certainement il y en avoir plusieurs.
Comme la démonstration de l'irrationnalité de $\text{[math]}$ (par la décomposition en facteurs premiers,le lemme de Gauss...).

invite43bf475e · 14/07/2007, 18h36

Tu peux préciser?

invitec053041c · 14/07/2007, 18h37

Envoyé par M I L A S

Tu peux préciser?

Préciser quoi ?

A voir en vidéo sur Futura · Aujourd'hui

invite43bf475e · 14/07/2007, 19h16

Le lemme de gauss

invitec053041c · 14/07/2007, 20h21

Mmm, moi et l'arithmétique ça fait 2 (c'est le cas de le dire

)
Mais de mémoire ça donne quelque chose comme ça:
Si $\text{[math]}$ , p et q entiers naturels premiers entre eux (car on peut supposer la fraction irréductible).
Alors, p²=2q²
donc p|2q² mais pgcd(p,q)=1 donc pgcd(p,q²)=1
Et d'après le lemme de Gauss, p|2.
1er cas:
p=1, donc $\text{[math]}$ ce qui est faux car le carré d'un nombre compris entre 0 et 1 est compris entre 0 et 1.

2nd cas:
p=2, donc
$\text{[math]}$ ,avec q entier, faut pas rêver

. (les carrés parfaits ne se terminent pas par 2)

invitec053041c · 14/07/2007, 20h27

(mais c'est complètement hors sujet

)

**Gwyddon** · 14/07/2007, 20h30

Belle démonstration Ledscat

Sinon pour revenir au sujet initial, il existe bien sûr d'autres méthodes. Par exemple on peut prouver qu'un sous-ensemble de l'ensemble des nombres premiers est infini ce qui a fortiori prouve que l'ensemble des nombres premiers est infini.

invitebb921944 · 14/07/2007, 22h05

On suppose que l'ensemble IP des nombres premiers est un ensemble fini :
IP : {p1,p2,...,pn}
-Soit N, un entier naturel défini par N=p1xp2x...xpn + 1, N étant plus grand que n'importe quel élément de IP, N n'appartient pas à IP.
-De plus N>=1, donc par définition, N possède au moins un diviseur premier p, élément de IP.
-p divise alors, à la fois p1xp2x...xpn, et N, donc p divise toute combinaison linéaire à coefficients entiers de ces deux nombres, et notamment leur différence, donc p divise 1. Ce qui absurde car p est premier, donc l'hypothèse posée sur IP est fausse, on en déduit qu'il existe une infinité de nombres premiers...

J'suis d'accord mais il me semble que tu n'as pas justifié que N n'est pas premier si ?

invitec053041c · 14/07/2007, 22h10

Envoyé par Ganash

J'suis d'accord mais il me semble que tu n'as pas justifié que N n'est pas premier si ?

Si:

N étant plus grand que n'importe quel élément de IP, N n'appartient pas à IP

Comme IP est l'ensemble supposé fini des nombres premiers, alors N ne l'est pas.

Cordialement.

invité576543 · 15/07/2007, 06h49

Envoyé par Gwyddon

Par exemple on peut prouver qu'un sous-ensemble de l'ensemble des nombres premiers est infini ce qui a fortiori prouve que l'ensemble des nombres premiers est infini.

Quelqu'un connaît-il un ensemble explicite infini de premiers, genre P(n) avec P une formule explicite injective des entiers vers les entiers premiers?

Cordialement,

invite43bf475e · 15/07/2007, 10h19

Il me semble qu'il existe des algorithmes permettant de déterminer les nombres premiers, d'ailleurs c'est le soucis de la cryptographie actuelle, réussir à factoriser un nombre très grand, genre 650650650530000580148111505068 054032106505640654006540252299 898797981330031651964108408421 54154 en un produit de facteurs premiers...

bon c'est pas le sujet mais c'est important de le dire!

invitec053041c · 15/07/2007, 12h30

Je doute qu'il existe un tel algorithme si ?
Car connaissant $\text{[math]}$ , il est extrêmement difficile de connaître $\text{[math]}$ .

invite43bf475e · 15/07/2007, 12h52

Au moyen des algorithmes de tri non ?

invitec053041c · 15/07/2007, 12h53

Envoyé par M I L A S

Au moyen des algorithmes de tri non ?

Je ne sais pas, je préfère me taire plutôt que dire des bêtises.

invitebb921944 · 15/07/2007, 13h05

Il n'a pas demandé une suite contenant tous les nombres premiers mais une infinité de nombres premiers !
On n'est donc pas obligé de déterminer Pn+1 en connaissant Pn.
Pour ma part j'ai cherché un peu et je n'en ai pas trouvé.
Il y a bien quelques suites dont les 40 (à peu près) premières valeurs sont des nombres premiers, certains nombres constructibles relativement aisément comme ceux de Carmichael qui ont de grandes probabilités d'être premiers (les pseudos premiers) mais pas de suite comme celle recherchée...

**invite35452583** · 15/07/2007, 15h11

Envoyé par M I L A S

Il me semble qu'il existe des algorithmes permettant de déterminer les nombres premiers, d'ailleurs c'est le soucis de la cryptographie actuelle, réussir à factoriser un nombre très grand, genre 650650650530000580148111505068 054032106505640654006540252299 898797981330031651964108408421 54154 en un produit de facteurs premiers...

bon c'est pas le sujet mais c'est important de le dire!

Je trouve qu'implicitement cela répond presqu'à la question : si un tel ensemble infini était connu, les recherches de très grands nombres premiers pour la cryptographie ne connaîtraient pas une telle frénésie. (Il suffirait de piocher dans un tel ensemble à moins que les nombres donnés soient peu manipulables car trop grand d'où le "presque").

Bref, je doute aussi qu'un tel ensemble existe (à l'état de nos connaissances actuelles).

invité576543 · 15/07/2007, 17h00

Envoyé par homotopie

Je trouve qu'implicitement cela répond presqu'à la question : si un tel ensemble infini était connu, les recherches de très grands nombres premiers pour la cryptographie ne connaîtraient pas une telle frénésie. (Il suffirait de piocher dans un tel ensemble à moins que les nombres donnés soient peu manipulables car trop grand d'où le "presque").

Bref, je doute aussi qu'un tel ensemble existe (à l'état de nos connaissances actuelles).

J'en doute aussi.

Mais, au passage, l'argument n'est pas bon du tout! S'il existait un tel ensemble et que les clés étaient choisies dedans, ou dérivées de nombres dans cette liste, ça simplifierait sacrément l'attaque du chiffre...

Cordialement,

**Gwyddon** · 15/07/2007, 17h23

Envoyé par mmy

J'en doute aussi.

Mais, au passage, l'argument n'est pas bon du tout! S'il existait un tel ensemble et que les clés étaient choisies dedans, ou dérivées de nombres dans cette liste, ça simplifierait sacrément l'attaque du chiffre...

Cordialement,

Je n'ai plus d'exemple en tête, mais il me semble que l'on peut prouver que certaines suites contiennent une infinité de nombres premiers. Par contre, on ne sait pas où dans cette suite.

Donc effectivement ce que j'ai dit était faux, je pensais à ce type de suite et je me suis mal exprimé.

**invite35452583** · 16/07/2007, 10h58

Envoyé par mmy

J'en doute aussi.

Mais, au passage, l'argument n'est pas bon du tout! S'il existait un tel ensemble et que les clés étaient choisies dedans, ou dérivées de nombres dans cette liste, ça simplifierait sacrément l'attaque du chiffre...

Cordialement,

En effet, oui.

**acx01b** · 23/07/2007, 19h53

bonsoir

wikipedia en donne une de suite de nombre tous premiers et qui contient tous les nombres premiers mais où 2 apparait une infinité de fois

moi pour racine de 2 j'utilise celle ci:
on suppose racine de 2 = p/q (premiers entre eux)
=> p²/q² = 2
mais p² et q² sont premiers entre eux donc leur quotient a peu de chance de faire 2
donc racine de 2 n'est pas égal à p/q

**nnn** · 24/07/2007, 08h47

bah des algorithmes trouvant tous les nombres premiers ça existe, c'est pas un problème (genre tu prends tous les nombres un par un et tu testes tous leurs diviseurs), le problème c'est de le faire en un temps raisonnable, inférieur à l'infini ; )

**Theyggdrazil** · 24/07/2007, 10h23

Envoyé par mmy

Quelqu'un connaît-il un ensemble explicite infini de premiers, genre P(n) avec P une formule explicite injective des entiers vers les entiers premiers?

Cordialement,

Désolé tout ce que j'ai c'est des suites qui ne contiennent aucun premier !

Si on avait ce que tu demandes, on aurait beaucoup moins de problèmes à calculer les grands nombres premiers

(et pour gagner 100 000$, ce serait bien plus facile aussi :P)

Edit : Rohla encore... Faut vraiment que j'apprenne à lire un post en entier avant de répondre :s désolé du doublon

**martini_bird** · 24/07/2007, 10h40

Envoyé par mmy

Quelqu'un connaît-il un ensemble explicite infini de premiers, genre P(n) avec P une formule explicite injective des entiers vers les entiers premiers?

Cordialement,

Salut,

il existe bien une formule explicite, mais le manque d'information vient alors de la répartition des zéros de la fonction $\text{[math]}$ de Riemann.

Si on note $\text{[math]}$ le n-ième nombre premier, on voit bien que $\text{[math]}$ se déduit de la fonction de comptage $\text{[math]}$ .
Or la somme (finie)
$\text{[math]}$ admet une expression fermée :

$\text{[math]}$

où $\text{[math]}$ est le logarithme intégral, et la somme $\text{[math]}$ porte sur les zéros non-triviaux de la fonction $\text{[math]}$ .

Enfin on peut calculer $\text{[math]}$ à l'aide de $\text{[math]}$ en inversant la relation (inversion de Möbius) :
$\text{[math]}$
où $\text{[math]}$ est la fonction de Möbius.

On peut donc bricoler une formule monstrueuse mais fermée pour $\text{[math]}$ , d'aucun utilité en pratique car on connaît trop peu la répartition des zéros $\text{[math]}$ .

Cordialement.

invité576543 · 24/07/2007, 10h58

Juste un question présentée comme naïve: la fonction μ ayant un petit rapport avec les premiers, est-ce que calculer le nième nombre premier à partir de la connaissance de la fonction μ ne peut pas se faire bien plus facilement que par l'approche que tu proposes?

En d'autres termes, ne trouve-t-on pas à la sortie quelque chose que l'on a été obligé d'entrer?

Cordialement,

**martini_bird** · 24/07/2007, 11h13

En d'autres termes, ne trouve-t-on pas à la sortie quelque chose que l'on a été obligé d'entrer?

Très juste !

En pratique, je sais que cette formule a été utilisée en tronquant la somme (de sorte que la connaissance de la fonction $\text{[math]}$ pour un "petit" nombre d'entiers permet d'obtenir de bonnes approximations asymptotiques). Il y a même une formule empirique due à Ramanujan qui donne d'excellentes approximations, mais je ne l'ai pas retrouvée.

Envoyé par mmy

est-ce que calculer le nième nombre premier à partir de la connaissance de la fonction μ ne peut pas se faire bien plus facilement que par l'approche que tu proposes?

Bonne question, je n'ai pas d'idée sur le sujet.

A noter qu'on a la relation
$\text{[math]}$
et qu'on pourrait se cacher en disant que si on connaît parfaitement la fonction $\text{[math]}$ , on doit pouvoir calculer $\text{[math]}$ sans trop de problème. Mais bon, c'est un peu tricher...

Cordialement.

**leg** · 26/07/2007, 10h17

bonjour à tous
je pense que ce problème est insoluble, car quelque soit les moyens materiels utilisé, il existerra toujours des nombres premiers superieur à cette limite ou à ses possibilté materiel; ce qui rend par conséquent, la tache ou les calculs hors de porté, lorsque P tend vers l'infini.

**nonef12** · 29/01/2014, 18h01

Plus une remarque qu'une réponse :

Les nombres de Fermat $\text{[math]}$ sont premiers 2 a 2, ce qui prouve que l'ensemble des nombres premiers est infini.

**gg0** · 29/01/2014, 20h02

6 ans après, est-ce vraiment utile ?

**S321** · 29/01/2014, 22h15

D'autant que les nombres de Fermat ne sont pas tous premiers. Entre F₅ et F₃₂ pas un seul n'est premier.

On n'est même pas certains qu'il existe plus de cinq nombres de Fermat premiers, ça fait petit pour une infinité.

Démonstration de l'ensemble des Nombres premiers

Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Re : Démonstration de l'ensemble des Nombres premiers

Discussions similaires

Preuve originale de l'infinitude des nombres premiers

Graphs de la classification des nombres premiers

Classification des nombres premiers

Ensemble des nombres premiers