Discrimination d'un nombre premier

[elmardi]

Bonjour,

Bien que n'ayant qu'un BAC+2 en informatique, je pense avoir trouvé une formule pour discriminer les nombres premiers, et je désirerais donc la mettre à l'épreuve. Et si jamais elle résiste, peut-on la simplifier ?

La voici en langage informatique :

Soit n un nombre entier impair ou premier supérieur ou égal à 5,
Si ((2^(n-1)) - 1)/n donne un résultat Entier, alors, n est premier.

[SaintAmand]

Bonjour,

Soit n un nombre entier impair ou premier supérieur ou égal à 5,
Si ((2^(n-1)) - 1)/n donne un résultat Entier, alors, n est premier.

L'hypothèse «n nombre premier» est inutile (un nombre premier supérieur à 2 est nécessairement impair).

Ta conjecture est fausse: 341 divise et pourtant 341 = 11x31. En revanche, la réciproque:

Si p est un nombre premier>2, alors p divise

est vraie. C'est un cas particulier du petit théorème de Fermat:

Si p est un nombre premier, et si a est un entier non divisible par p, alors p divise .

[JackeOLanterne]

Quelques algorithmes et relations déterminent des quantités de nombres premiers. :id:

[leon1789]

Bonjour,

Bien que n'ayant qu'un BAC+2 en informatique, je pense avoir trouvé une formule pour discriminer les nombres premiers, et je désirerais donc la mettre à l'épreuve. Et si jamais elle résiste, peut-on la simplifier ?

La voici en langage informatique :

L'implication est fausse pour n=341.

voir "nombres pseudo-premiers" de base 2 : http://fr.wikipedia.org/wiki/Nombre_pseudopremier

[Amberss]

est vraie. C'est un cas particulier du petit théorème de Fermat:

[Elerinna]

Le libellé exact est : Si p est un entier premier alors , ou (petit théorème):

[nodjim]

Il n'empêche, c'est bien par cette méthode que les grands nombres probablement premiers sont cherchés pour servir dans le codage RSA. On les dit probablement premiers car il y a peu de nombres composés qui ont cette propriété.