Répondre à la discussion
Affichage des résultats 1 à 21 sur 21

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



  1. #1
    T.Rex

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

    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

    -----


  2. Publicité
  3. #2
    karatekator

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

    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?
    Sauf erreur, je ne me trompe jamais

  4. #3
    Quinto

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

    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?

  5. #4
    T.Rex

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

    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.

  6. #5
    Quinto

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

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

  7. A voir en vidéo sur Futura
  8. #6
    sylvainix

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

    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.

  9. Publicité
  10. #7
    Quinto

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

    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...

  11. #8
    sylvainix

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

    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 ...

  12. #9
    Evil.Saien

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

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

  13. #10
    martini_bird

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

    Citation Envoyé par sylvainix
    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.

  14. #11
    T.Rex

    Edouard Lucas

    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

  15. #12
    Eric78

    Re : Edouard Lucas

    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
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  16. Publicité
  17. #13
    A1

    Re : Edouard Lucas

    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!

  18. #14
    Eric78

    Re : Edouard Lucas

    Citation Envoyé par A1
    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
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  19. #15
    MathMathMath

    Re : Edouard Lucas

    Citation Envoyé par T.Rex Voir le message
    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 ?

  20. #16
    gg0

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

    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.

  21. #17
    MathMathMath

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

    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 ?

  22. #18
    gg0

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

    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 ?

  23. Publicité
  24. #19
    MathMathMath

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

    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 ?

  25. #20
    gg0

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

    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.

  26. #21
    MathMathMath

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

    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 !

Sur le même thème :

Discussions similaires

  1. Qui a inventé l'ADSL ?
    Par algerianfetish dans le forum Internet - Réseau - Sécurité générale
    Réponses: 10
    Dernier message: 14/05/2006, 09h17
  2. division euclidienne d'un polynôme par (x-a) qui ne tombe pas juste
    Par Seirios dans le forum Mathématiques du collège et du lycée
    Réponses: 9
    Dernier message: 29/04/2006, 13h12
  3. Annonce d une Division d Oeuf humain,sans spermatozoide..
    Par neutrinos dans le forum Actualités
    Réponses: 8
    Dernier message: 23/12/2004, 12h13