Nombres premiers

[Patrickkk]

Bonjour,
Quelqu'un peut me dire comment on fait pour pouvoir dire si un nombre est premier ou pas?
Merci d'avance pour votre aide.

[Patrickkk]

J'ai un exercice avec pleins de nombres immenses et je dois dire si ils sont premiers ou pas... Comment faire, je n'ai aucune idée...
Aidez moi svp!

[Lostounet]

Un nombre premier est un nombre n'admettant pas de diviseurs autre que lui-même et 1.

Il suffit donc de trouver un seul diviseur différent du nombre-même et 1 pour dire qu'il n'est pas premier. Maintenant, je ne sais pas à quel point ça pourrait tenir.
Pourrais-tu nous donner un exemple de nombre?

[oscar]

THEOREME: Le plus petit diviseur d' un nombre COMPOSE est 1er et son
carré est inférueur ou égal à ce nombre

APPLICATION: Reconnaître si un nombre donné N est 1er

1)Il suffit d' essayer les diviseurs 1ers 2;3;5....à l' exclusion des diviseurs composés

2)N est 1er quand, à défaut d' une division exacte, on aboutit à un diviseur
1er dont le carré est Supérieur à N.


Exemples: 71: 79:;101;109:233:349:487;571;619:757:659

[oscar]

Nombres 1ers <1000


http://yfrog.com/2tnombres1ersinfrieursa10j

[nodjim]

C'est quoi ces nombres immenses ? tu peux nous en donner quelques uns pour voir ?

[Patrickkk]

THEOREME: Le plus petit diviseur d' un nombre COMPOSE est 1er et so carreé
est inférueur ou égal à ce nombre

APPLICATION: Reconnaître si un nombre donné N est 1er

1)Il suffit d' essayer les diviseurs 1ers 2;3;5....à l' exclusion des diviseurs composés

2)N est 1er quand, à défaut d' une division exacte, on aboutit à un diviseur
1er dont le carré est Supérieur à N.


Exemples: 71: 79:;101;109:233:349:487;571;619:757:659

Oui, mais il faudrait essayer tous les nombre premiers inférieurs à alors?
Des nombres comme 256817, 257323 ou 11323...

[Ericovitchi]

ils ne sont pas premiers
256817 = 11x37x631
257323 = 11x149x157
11323 = 13²x67

[Patrickkk]

Ok merci beaucoup, j'ai trouvé tout les autres.

[Zweig]

Tu peux sinon utiliser le théorème de Wilson si ton nombre n'est pas très trsè grand ..

[ffpower]

Euh, Wilson, c'est une blague, cette méthode..Vas y, montre avec Wilson que 101 est premier pour voir^^

[Ben314]

A l'aise blaise :

et quand on ajoute 1, on voit clairement que ça se divise par 101 :zen:

[Zweig]

Bah oui, avec l'ordinateur, ça se fait ^^ (pour des pas très grands nombres ...)

[ffpower]

Je pense qu'il vaut mieux réduire modulo 101 au fur à mesure des calculs^^
Mais même comme ca, ca reste une blague :)

[Zweig]

J'vois pas en quoi c'est une blague ... Pour des nombres dont le calcul, via ordinateur, de la factoriel ne prend pas trois plombes, le test de la primalité du nombre en question se fait en deux calculs, au lieu de tester tous les nombres<= V(n) pour voir si se sont des diviseurs ...

Après en concours, effectivement, c'est inefficace ...

[Ben314]

OK, sauf que si tu as une machine (ou un ordi) sous la main, même pour lui, ça va beaucoup plus vite de tester la divisibilité par 2, par 3 puis par les 6k+-1 jusqu'à avoir dépassé la racine du nombre.

[Patrickkk]

Re
J'ai un autre problème:
Comment démontrer que n;)-n est un multiple de 2, 3 et 7?
J'ai réussi pour 2 mais je n'y arrive pas pour 3 et 7...
Merci d'avance pour vos réponses.

[Ericovitchi]

en décomposant n;)-n = (n-1) n (n+1) (n²-n+1) (n²+n+1)
on voit qu'il est divisible par (n-1) n et (n+1) donc 3 nombres consécutifs, il y a forcement un multiple de 3 dedans.
Pour 7 c'est un peu pareil, je te laisse cogiter.

[Patrickkk]

Ok, merci beaucoup!
Mais peux tu m'expliquer comment tu à fait pour factoriser?

[Patrickkk]

Re,
J'ai quand même des difficultés pour la divisibilité par 7:
Je peux conjecturer que si n est pair, n²+n+1 (n de la forme 2k) est divisible par 7
et si n est impair (2k+1), c'est n²-n+1 qui est divisible par 7.
Mais je n'ai aucune idée comment démontrer cela.
Merci encore pour votre aide.