2006-12-20 06:38:59 · 22 réponses · demandé par marie D 1 dans Sciences et mathématiques ➔ Mathématiques
1) Par définition un nombre premier est un nombre divivible par
1 et par lui-même. À noter que le nombre 1 n'est pas un nom-
bre premier. De plus, 6 n'est pas un nombre premier car
6 = 2 X 3 mais 11 est un premier car 11/1 = 11 reste 0 et
11/11 =1 reste 0 ( 1 et 11 sont les seuls facteurs admissibles)
2) Aucuns polynôme d'une seule variable ne peut générer tous
les nombres premiers. Par contre, la formule
f(n) = 36n^2 -810n +2753 donne tous les nombres
premiers entre 0 et 44.
3) Euclide a montré qu'il existait une infinité de nombres pre-
miers.
4) Dans les années quarantes le mathématicien hongrois Paul
Erdös a montré par des méthodes arithmétiques élémentaires
qu'il existait une infinité de nombres premiers.
5) Le théorème des nombres premiers permet de répondre à des
questions du genre:
a) combien y a-t-il de nombre premier inférieur à 100 000 ?
b) quelle est la probabilité pour qu'un nombre entier aléa-
toire de 100 chiffres soit premier ?
6) L'algorithme d'Érathostène est une méthode simple pour
trouver un nombre premier.
7) Il n'existe pas jusqu'à présent un ordre dans la distribution des
nombres premiers. De plus, aucune formule mathématique ne
peut générer tous les nombres premiers.
8) Voici quelques nombres premiers : 2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,51,53,59,61,67,71
2006-12-21 10:16:20 · answer #1 · answered by frank 7 · 0⤊ 0⤋
En les cherchant...
Sérieusement, il existe de nombreux tests de primarité. Le plus facile est le crible d'Eratosthène, mais qui est en temps exponentiel.
Depuis peu, un algorithme en temps polynomial a été trouvé par trois mathématiciens indiens, il s'agit de l'algorithme AKS, mais il est assez difficile à montrer et à appliquer (il travaille dans des anneaux de polynomes congrus modulo un autre polynome et congru modulo un entier). AKS est efficace théoriquement mais pas en pratique (il manipule des polynomes de plusieurs giga-octets et n'est efficace qu'asymptotiquement).
Il existe également des tests dits probabilistes, comme Solovay-Strassen ou Miller-Rabin, qui peuvent se tromper en te renvoyant le résultat. Mais rassure-toi, la probabilité d'erreur étant rendue plus faible que celle d'une défaillance du système (ie d'une erreur de transmission de bit dans ton pc), on considère qu'ils ne se trompent jamais. Le test de Miller-Rabin est le plus utilisé car il est rapide et facile à mettre en oeuvre. Pour leurs tests de primarité, par exemple, le logiciel Mathematica utilise un test de Miller- Rabin, et Maple utilise un test de Miller-Rabin couplé à un test de Solovay-Strassen.
2006-12-20 09:18:59 · answer #2 · answered by rodgeur 3 · 1⤊ 0⤋
Si ta question est seulement de trouver un autre nombre premier, alors multiplie tous les nombres premiers que tu connais et ajoute 1.
Tu auras un autre nombre premier.
Pas celui juste après dans la liste, mais tu en auras un autre quand même.
L'ensemble des nombres premiers est infini.
En revanche, si ta question est de savoir si un nombre donné est premier, bah les ordinateurs les plus puissants du monde se cassent déjà les dents dessus dès que l'on touche à la cryptographie.
2006-12-20 08:56:02 · answer #3 · answered by Toonio 4 · 1⤊ 0⤋
En cherchant un diviseur, et si on en trouve pas d'autre que 1 et lui-même alors c'est un nombre premier (ex : 1, 2, 3, 5,7,11,13,17,19,23.....)
Je sais pas si c'est la réponse que tu voulais
2006-12-20 06:51:42 · answer #4 · answered by mimory 2 · 1⤊ 0⤋
Si ton nombre n'est pas trop grand il y a un moyen très simple :
Pour tout x élément de R,
X est un nombre premier si et seulement si sa racine carré Y n'est divisible par aucun des nombres premiers inférieurs à Y.
2006-12-23 05:28:46 · answer #5 · answered by aqses 3 · 0⤊ 0⤋
En ecrivant un petit programme informatique, qui part de 2 essaie de trouver le nombre premier suivant à partire de 3 et au delà en divisant par les précédents, si la division n'est pas entière c'est qu'il a trouvé un nouveau qu'il rajoute à la liste et reprendre à partir de p+1. où p est le dernier nombre premier trouvé. (tu peux aussi rajeuter de ne diviser que les nombre impairs)
2006-12-21 11:01:58 · answer #6 · answered by Leen 3 · 0⤊ 0⤋
Il existe ce qu'on appelle le crible d'Erathostène.
2006-12-21 02:18:59 · answer #7 · answered by frenchbaldman 7 · 0⤊ 0⤋
Le probleme du crible d'Eratosthene, c'est que c'est un algorithme super long à implémenter. Bon courage pour aller cocher tes petites cases jusqu'à racine de N...
Ceci dit, Monsieur Pierre de Fermat a une solution qui prouve une fois de plus que c'est un gros malin.
Monsieur gros malin a pris les nombres F(n)=2^(2^n)+1 et pis il a eu un éclair de génie.
Par exemple, pour n=2, on a
F(2)=2^(2^2)+1=17
qui est un nombre premier.
Et puis pour n=0,1,2,3 et 4, ca marche aussi. Du coup Monsieur gros Fermat malin a dit:
"tout nombre F(n)=2^(2^n)+1 avec n entier positif est un nombre premier"
Génial,non?
Bon, le souci c'est que ça marche pas pour 5 (ni pour quoi que ce soit en dessous de 32)
Pourtant, tout ca était d'une rigueur fantastique. Je sais pas pourquoi, ça me fait repenser au dernier théorème ou monsieur malin gros Fermat disait:
"J'ai une démonstration magnifique, mais j'ai pas la place pour l'écrire sur mon petit cahier"
J'imagine un mec qui sort ça le jour de son bac.
Ce qu'il est drole ce monsieur Fermat.
2006-12-20 15:44:47 · answer #8 · answered by Anonymous · 0⤊ 0⤋
Pour les très grans nombres, aucune loi n'a été trouvée - enfin il y a beaucoup de lois sur la distribution, pas sur la recherche d'un nombre premier particulier. Les ordinateurs permettent d'aller très loin... "pas plus". Il est bien possible que la proposition "n est premier" soit indécidable (Gödel). Des recherches approfondies ont lieu au Portugal.
2006-12-20 11:31:58 · answer #9 · answered by Obelix 7 · 0⤊ 0⤋
En les cherchant...à l'aide d'ordinateurs et de tests. Voir plus haut!
Les nombres de Mersenne donnent de bons résultats: on vient d'en trouver un en septembre 2006...
2006-12-20 10:27:12 · answer #10 · answered by kelbebe 4 · 0⤊ 0⤋