Qui a inventé la preuve de primalité sans division ?

[inviteb0cf188d]

Bonjour,
Une petite devinette mathématico-historique:
Qui a inventé la première méthode permettant de prouver qu'un nombre est premier sans nécessiter de diviser ce nombre par tous les nombres premiers précédents inférieurs à ?
Tony
-----

[karatekator]

je ne savais même pas qu'il exister un autre methode!
Et comment on fait pour étudier la primalite dun nombre sans effectuer de division?

[inviteab2b41c6]

Je dirais Euler ou Fermat, mais je pense à une certaine méthode qui est plutot la preuve de la NON primalité...
Quelle est cette méthode?

[inviteb0cf188d]

Un indice : il est (était) Français.

comment on fait pour étudier la primalite dun nombre sans effectuer de division ?

On utilise des propriétés mathématiques tarabisquotées ...
A suivre.

[A voir en vidéo sur Futura]

[inviteab2b41c6]

Alors je dirais Fermat, mais j'aimerai bien savoir ce qu'était cette méthode...

[invitef60ce002]

Ce doit être Fermat avec son petit théorème.
Si n est un nombre premier, et b un nombre entier quelconque, alors b^n-b est un multiple de n.
Si b^n-b n'est pas un multiple de n, alors n n'est pas premier.

[inviteab2b41c6]

Comme je le disais ce théorème est un critère de non primalité et non de primalité...(cf Carimchael)
Donc je ne suis pas totalement sur de notre réponse conjointe...

[invitef60ce002]

Deplus, est-ce que "Si n est un nombre premier, et b un nombre entier quelconque, alors b^n-b est un multiple de n" implique forcément la réciproque ? Il y a peut être des cas avec n non-premier qui fonctionne ...

[inviteeecca5b6]

Bezout ? Vu qu'il a beaucoup travaillé sur les entiers, premiers entre eux...

[invite4793db90]

Deplus, est-ce que "Si n est un nombre premier, et b un nombre entier quelconque, alors b^n-b est un multiple de n" implique forcément la réciproque ? Il y a peut être des cas avec n non-premier qui fonctionne ...

Ce sont justement les nombres de Carmichaël.

[inviteb0cf188d]

C'est Edouard Lucas (1842-1891).

Vous trouverez sur le site officiel plein d'informations (bibliographie, publications) : site officiel .

J'ai également mis sur mon site plusieurs des copies (.pdf) - trouvées à la BNF - de ses ouvrages principaux : Livres .

Il y a également la thèse de Mme Décaillot.

A propos du test de non-primalité de Fermat, Lucas a élaboré ce qu'il appelait la réciproque du théorème de Fermat.

Lucas a appliqué sa méthode sur le nombre de Mersenne : . Et c'est donc le premier nombre dont on a prouvé la primalité sans le diviser par des nombres premiers.

La méthode de Lucas est basée sur l'étude des "fonctions numériques simplement périodiques", à partir de la suite de Fibonacci. On parle d'ailleurs maintenant de "Séquence de Lucas". L'étude des propriétés de telles suites permet de définir un critère de primalité.
Ainsi, pour les nombres de Mersenne, on utilise le test dit LLT (Lucas-Lehmer Test), qui s'exprime très simplement :
Soit un nombre de Mersenne (q est premier). Soit la suite : . Alors est premier si et seulement si on a le terme .

La méthode est décrite dans les détails dans les livres fournis.
Mon site contient également le chapitre 2 du livre de Paul Ribenboim (Anglais, désolé) qui donne une preuve plus mathématique (mais pas forcément plus simple ...).

Une preuve compète (avec réciproque) n'a été fournie clairement qu'au début du XXème siècle, par D. Lehmer. Mais c'est à Edouard Lucas que revient la découverte de ces méthodes.

Et de plus Edouard Lucas fut un personnage fort sympathique.

Bonne lecture !

Pour plus d'infos sur la recherche des plus grands nombres premiers, voir le site : GIMPS et son forum.

Tony

[invite3f53d719]

Tient à propos, j'avais fait pour mon tpe un petit applet pour tester grâce au test de Lucas-Lehmer si un nombre de Mersenne est premier : http://tpe.crypto.free.fr/contenu/cl...ts/JLucas.html

[invite4e5046fc]

En effet , il existe d'autres tests de primalité je cite : le test de Miller - Rabin.
Ce qui est étrange c'est le polynôme de Jones ainsi que les fractions de Conway et Guy, jetez-y qqes coups d'oeil et vous réaliserez!

[invite3f53d719]

En effet , il existe d'autres tests de primalité je cite : le test de Miller - Rabin.

Ce n'est pas un test de primalité: il dit juste qu'un nombre est premier avec une très grande proabilitée

[invite8c3c232e]

C'est Edouard Lucas (1842-1891).

Vous trouverez sur le site officiel plein d'informations (bibliographie, publications) : site officiel .

J'ai également mis sur mon site plusieurs des copies (.pdf) - trouvées à la BNF - de ses ouvrages principaux : Livres .

Il y a également la thèse de Mme Décaillot.

A propos du test de non-primalité de Fermat, Lucas a élaboré ce qu'il appelait la réciproque du théorème de Fermat.

Lucas a appliqué sa méthode sur le nombre de Mersenne : . Et c'est donc le premier nombre dont on a prouvé la primalité sans le diviser par des nombres premiers.

La méthode de Lucas est basée sur l'étude des "fonctions numériques simplement périodiques", à partir de la suite de Fibonacci. On parle d'ailleurs maintenant de "Séquence de Lucas". L'étude des propriétés de telles suites permet de définir un critère de primalité.
Ainsi, pour les nombres de Mersenne, on utilise le test dit LLT (Lucas-Lehmer Test), qui s'exprime très simplement :
Soit un nombre de Mersenne (q est premier). Soit la suite : . Alors est premier si et seulement si on a le terme .

La méthode est décrite dans les détails dans les livres fournis.
Mon site contient également le chapitre 2 du livre de Paul Ribenboim (Anglais, désolé) qui donne une preuve plus mathématique (mais pas forcément plus simple ...).

Une preuve compète (avec réciproque) n'a été fournie clairement qu'au début du XXème siècle, par D. Lehmer. Mais c'est à Edouard Lucas que revient la découverte de ces méthodes.

Et de plus Edouard Lucas fut un personnage fort sympathique.

Bonne lecture !

Pour plus d'infos sur la recherche des plus grands nombres premiers, voir le site : GIMPS et son forum.

Tony

Merci pour toutes ces informations très intéressantes !

J'essaie de comprendre cette partie (source Page 62 http://visualiseur.bnf.fr/CadresFene...52&I=132&M=tdm)

Si a,b,c,... désignent les racines d'une équation dans laquelle les coefficients sont entiers, et celui de la plus haute puissance de l'inconnue égal à l'unité, l'expresion

désigne le produit par p d'une fonction symétrique entière des racines de l'équation, et, par suite, un multiple de p.

Quelqu'un peut m'aider ?

[gg0]

Bonjour.

Dans le développement de , on obtient des termes de la forme où a+b+c+...=p avec un coefficient multiple de p sauf pour les termes
Le cas de deux nombres (formule du binôme) est éclairant et se généralise (développement multinomial).

Cordialement.

[invite8c3c232e]

Bonjour,

Merci pour ta réponse mais cela va trop vite pour moi. Allons-y par petites étapes.

Si a,b,c,... désignent les racines d'une équation => ?
dans laquelle les coefficients sont entiers => on parle de quels coefficients ?
et celui de la plus haute puissance de l'inconnue égal à l'unité => np = 1 ?

[gg0]

Ah, ok !

Il faut tout reprendre, tu n'as jamais fait d'études mathématiques ?

Mais quelques idées :
* " ?" Pas nécessairement, si j'ai une bonne intuition de ce à quoi ça va servir ensuite. On ne les utilisera pas directement (si j'ai la bonne idée).
* "on parle de quels coefficients ?" l'équation est supposée polynomiale, donc la notion de coefficients est évidente : ceux du polynôme.
* " np = 1 ? " Pourquoi ça ? On te dit seulement que le terme de plus haut degré est de coefficient 1. Si le polynôme est de degré m, alors le polynôme commence (ou termine, si on l'écrit par degrés croissants) par x^m.

Cordialement.

NB : il faudra peut-être que j'aille voir le texte que tu lis, mais il doit y avoir des indices sur le sens des mots, non ?

[invite8c3c232e]

Mes cours remontent à une époque très lointaine et je me dis que j'aurais du conserver mes notes, j'ai oublié pas mal de choses !
Merci pour votre indulgence.


Je fais appel à une bonne âme qui pourrait me dire où se situe mon erreur dans la compréhension de la suite du théorème


Je prends la solution réelle + les 2 autres solutions racines, c'est correct ?
J'ai utilisé un outil en ligne d'où le manque de précison mais en principe la somme = 0

Par contre pour

L'expression suivante ne me donne pas un multiple de p
Manque de précision ?

[gg0]

C'est normal, tu n'as pas fait le calcul indiqué.

Le fait de prendre seulement la partie réelle des deux racines complexes fausse complètement le calcul.

Cordialement.

[invite8c3c232e]

Effectivement, étant de signe contraire et s'annulant je n'en avais pas tenu compte. Tout change pour
Maintenant le calcul est correct. (Ah le fameux Souvenirs, souvenirs... )

Merci pour ton aide !