Nombres premiers

[Djmaxgamer]

Bonjour a tous, j'ai passé comme une partie d'entre vous mon bac. Pour ma part, Bac S option SI avec spé maths. Mais justement parlons spé maths. Le bac est terminé, mais par curiosité on peut encore s'y interesser pas vrai
Bref je viens de penser à une manière de trouver les nombres premiers les plus grands...et je me demande pourquoi cette technique, qui permettrait de trouver des nombres premiers a plus de 10 million de chiffres n'est pas utilisée... (clin d'oeil aux 100 000 USD offert à la découverte d'un de ces dit-nombres premiers).

Pour cela je suis parti d'une des démonstrations du caractère infini de la liste des nombres premiers. Jvais vous l'écrire (bon le bac est passé hein les erreurs splus grave :p)

Supposons que la liste des nombres premiers est finie (et qu'elle contient n nombres premiers).
Dans ce cas, on peut définir une suite de termes finie contenant les n nombres premiers.
Posons :
Avec la suite contenant tous les nombres premiers
Comme contient tous les nombres premiers, on aurait sp qui serait un nombre non premier.
On sait qu'un nombre est premier si il n'est divisible par aucun nombre premier inférieur à lui (cela découle du fait que tous les nombres peuvent être décomposables en un produit de facteurs premiers : pour vérifier le caractère premier d'un nombre il faut donc vérifier sa divisibilité avec tous les nombres premiers inférieurs à lui)
Utilisons un raisonnement par récurrence. Vérifions pour .
On a car
De la même manière, on a :
On peut réitérer ce raisonnement jusqu'à n.
On a donc pour tout

Donc il n'existe pas de décomposition de produit de facteur premiers (facteurs étant dans la liste pn).
( Donc est un nombre premier. : faux )
Il existe donc d'autres nombres premiers que ceux contenus dans la suite . Ce qui entre en contradiction avec la supposition initiale.
En raisonnant par l'absurde, il existe une infinité de nombre premier.



Voila pour la démonstration du cours (normalement exigible au bac donc j'espère pas avoir de questions la dessus (si je ne me suis pas planté) )
Mais d'après ce raisonnement pour avoir un nombre premier très grand, il suffit de multiplier tous les nombres premiers connus et d'ajouter 1.

Mais alors pourquoi n'est ce pas la technique utilisée ? D'après le raisonnement, une vérification n'est pas nécessaire : c'est dans la définissions même de ce nombre (dans la démonstration ) qu'est mis en place son caractère premier.

Alors pourquoi ces vérification énormes ? Ne suffirait-il pas d'effectuer ce calcul ?

Mais je comprends bien que cette technique met a part une quantité énorme de nombre premiers. En prenant uniquement les 4 premiers on a :

211 est bien premier (voir demonstration)
mais bien sur les nombres sont oubliés. Ainsi on a pas le nombre premier qui suit dans la liste, mais un nombre plus grand.
Mais cela n'est-il pas suffisant pour trouver le nombre premier très grand ?

On peut par exemple trouver un nombre premier à 12 chiffres très facilement :

Qui est donc premier.

Quelqu'un aurait-il une explication ?



EDIT : J'ai ptetre l'air bête a dire ca maintenant...mais le problème ne réside-t-il pas dans le fait que cette démonstration montre qu'il existe une décomposition de nombre premiers de ne contenant pas les termes de la suite supposée finie mais pas dans le fait que est premier ?

EDIT2 : c'est bien cela je crois... contre exemple :

cela montre que si on suppose que la suite des nombres premiers s'arrete à , on a encore et des nombres premiers (plus grands que ) mais pas necessairement que est premier...

[uztop]

Salut,

question intéressante et très bonne démarche vu que je vois que tu as réussi à répondre tout seul à la question que tu te poses.
Oui, c'est exactement ça, on a montré que la décomposition de Sp ne contient aicun des termes de la liste, il y a donc d'autres nombres premiers qui existent, mais ça ne montre pas que Sp est premier.

[Djmaxgamer]

Dans ce cas ma question devient : pourquoi ne pas utiliser cette technique comme "outil de sélection de nombres susceptibles d'être premiers" pour ensuite vérifier ?

Il existe surement des manieres plus selectives (je connais pas vraiment a part leur nom et leur définition) telles que la suite de Mersenne ou les nombres de Fermats.
Mais de la même manière le 5ème terme de la suite de Mersenne n'est pas premier.
(11 étant le 5ème nombre premier)


Et de la même manière, le 5ème terme de la suite de Fermat n'est pas premier :




Donc au final, on utilise pas cette technique de sélection car justement elle n'est pas assez "sélective" (dans le sens où beaucoup de nombres non premiers sont obtenus) ?

[nodjim]

Bonjour.
Tu oublies un léger détail dans ton raisonnement, ce que pour vérifier si ton produit est premier ou pas, il te faut faire un nombre exagéré de divisions par tous les nombres compris entre le plus grand facteur premier de ton produit et la racine carrée du nombre à tester.
Alors que pour les nombres 2^n-1 ou 2^n+1, on connait des tests très pratiques qui réduisent considérablement le nombre de vérifications.

[Djmaxgamer]

ok je ne savais pas qu'il existait une technique plus simple que de tester la divisibilité avec tous les nombres jusqu'à la racine carré du supposé nombre premier. Dans ce cas c'est bien plus clair :we:

Mais ces techniques sont, pour la compréhension, abordables pour un terminale S ?


ps : il y a énormité de calculs, mais il faut juste tester pour les autres nombres premiers entre et , ce qui réduit quand même la liste, mais doit être quand même bien plus grands que les techniques dont tu parles

[uztop]

ps : il y a énormité de calculs, mais il faut juste tester pour les autres nombres premiers entre et , ce qui réduit quand même la liste, mais doit être quand même bien plus grands que les techniques dont tu parles

oui, ton idée correspond à peu près au crible d'Erastophène (il faut bien savoir quels sont les nombres qui sont premiers en dessous de ) Ca fait beaucoup trop de calculs pour que ça soit faisable pour des grands nombres

[Djmaxgamer]

Après quelques recherches il s'avèrerait que certains nombre premiers ont été trouvé avec cette technique : http://primes.utm.edu/largest.html#largest

Euclid's proof that there are infinitely many primes uses numbers of the form n#+1. Kummer's proof uses those of the form n#-1. Sometimes students look at these proofs and assume the numbers n#+/-1 are always prime, but that is not so. [hahahaha quelle ironie] When numbers of the form n#+/-1 are prime they are called primorial primes. [...] The current record holders and their discoverers are:
rank.........prime..................digits.......when
1.............392113#+1..........169966....2001

Comme quoi certains ont été courageux pour trouver un nombre à 170 000 chiffres ^^

Mais rien qu'en comparant cette valeurs au 9 millions du plus grand premier on voit la différence niveau facilité de vérification.

Mais justement je trouve pas sur le net ces tests, ces techniques permettant de vérifier moins difficilement si ou sont premiers ou pas