Savez-vous factoriser à la mode de Fermat ?

Publié le 18 Mai 2014 par blogdemaths

La question de savoir factoriser un nombre entier est cruciale de nos jours: de nombreux systèmes cryptographiques (dont le fameux RSA) reposent dessus. Mais, au 17ème siècle, du temps du mathématicien Pierre de Fermat, savoir factoriser un entier n’avait absolument aucune application pratique; le seul intérêt de trouver une factorisation était éventuellement ludique (on s’amusait comme on pouvait à l’époque).

Disons-le tout de suite, savoir factoriser un entier est un problème difficile. Par exemple, si je vous donne le nombre 15, vous me direz immédiatement que c’est 3 fois 5 mais si je vous donne 2 473 859, peu d’entre vous me répondront qu’il s’agit du produit de 1039 par 2381. L’exemple que je viens de vous donner reste relativement simple (!), mais dans une lettre envoyée à Fermat en 1643, le père Mersenne (il était prêtre), lui demanda de factoriser le nombre 100 895 598 169. Rien que ça ! Quel farceur ce Mersenne… Cependant, sa blague tomba à l’eau car il reçut aussitôt une lettre de Fermat (datée du 7 Avril 1643) dans laquelle on pouvait lire ceci:

Vous me demandez si le nombre 100 895 598 169 est premier ou non, et une méthode pour découvrir, dans l’espace d’un jour, s’il est premier ou composé. À cette question, je réponds que ce nombre est composé et se fait du produit de ces deux : 898 423 et 112 303, qui sont premiers.

Impressionnant. Sans calculatrice et en moins d’un jour, Fermat a réussi à factoriser un nombre à 12 chiffres ! Mais comment Fermat a-t-il fait pour factoriser ce nombre ? Car malheureusement Fermat n’a pas donné sa méthode dans cette lettre… (certaines mauvaises langues diront qu’il était coutumier du fait, et que sa marge était aussi courte que le Pape est une femme).

Ce que l’on sait en revanche, c’est que Fermat avait développé une méthode de factorisation, dite méthode de factorisation de Fermat (original comme nom) que je vais tenter de vous expliquer ici.

Une idée simple mais brillante

Soit $N$ un entier naturel qu’on veut factoriser. La méthode de Fermat découle de l’idée toute simple suivante: si on peut écrire $N$ comme une différence de deux carrés $N=a^2 -b^2$ alors $N=(a+b)(a-b)$ . Le problème de la factorisation se ramène donc à un problème de soustraction. Par exemple, $15=4^2 - 1^2$ donc $15 = (4+1) (4-1) = 5 \times 3$ .

Remarque: si $N$ est un nombre impair, une telle factorisation existe toujours. En effet, si $N=2n+1$ alors vous pouvez vérifier que $N= (n+1)^2 - n^2$ . Il faut faire tout de même attention car dans ce cas nous avons $a=n+1$ et $b=n$ , ce qui donne $a-b=1$ et $a+b=2n+1=N$ : la factorisation obtenue est donc triviale (savoir que $N=N \times 1$ n’a aucun intérêt, vous en conviendrez).

Deux conditions nécessaires

Dans toute la suite, on supposera que $N$ n’est pas un carré (car sinon, la factorisation de $N$ est facile à trouver: c’est $N = \sqrt{N} \times \sqrt{N}$ ). Si on est capable de trouver une décomposition comme une différence de deux carrés, autrement dit si $N = a^2 - b^2$ alors,

1) $a^2 -N$ est un carré
2) $a \geqslant E( \sqrt{N}) +1$ où $E( \sqrt{N})$ est la partie entière de $\sqrt{N}$ .

Explication: Le 1) est évident. Pour le 2), il faut remarquer que $a^2 = N + b^2 > N$ (strict car $N$ n’est pas un carré) et donc $a > \sqrt{N}$ , ce qui implique $a \geqslant E( \sqrt{N}) +1$ .

Ces deux conditions vont nous permettre, comme vous allez le voir, de donner un algorithme de factorisation.

La méthode de factorisation de Fermat

On note toujours $N$ le nombre à factoriser et on pose $q= E(\sqrt{N})$ . Puisque l’idée est de trouver $a$ et $b$ tels que $N=a^2 -b^2$ et puisqu’on a vu que si $a$ existe alors $a \geqslant q+1$ , alors on va choisir successivement $a=q+1$ , $a=q+2$ , $a=q+3$ , … jusqu’à ce qu’il y ait un $a$ tel que $a^2 - N$ soit un carré. Facile, non ?

Je donne un exemple simple: supposons qu’on souhaite factoriser $N= 799$ . On a $\sqrt{799} \simeq 28,26...$ donc $q=28$ .

On essaye avec $a=q+1 = 29$ . On a $a^2 - N = 29^2 - 799 = 43$ . Ce n’est pas un carré.
On essaye avec $a=q+2 = 30$ . On a $a^2 - N = 30^2 - 799 = 101$ . Ce n’est pas un carré.
On essaye avec $a=q+3 = 31$ . On a $a^2 - N = 31^2 - 799 = 162$ . Ce n’est pas un carré.
On essaye avec $a=q+4 = 32$ . On a $a^2 - N = 32^2 - 799 = 225$ qui est un carré !

Comme $225 = 15^2$ , on pose $b=15$ , et on a donc la relation $a^2 - N = b^2$ . Ainsi, $N = a^2 - b^2 = 32^2 - 15^2$ . On en déduit que $N=(32+15) (32-15)$ c’est-à-dire $N = 47 \times 17$ .

Raffinement

Dans le cas où le nombre $N$ est très grand, le nombre d’étapes et de calculs est potentiellement très élevé. Pour que cette méthode soit utilisable d’un point de vue pratique, il va falloir minimiser le nombre de calculs, et pour cela, on va essayer de voir comment réutiliser les calculs déjà effectués au fur et à mesure. En particulier il va être possible de calculer les $a^2 - N$ facilement.

Puisqu’on pose successivement $a=q+1$ , $a=q+2$ , etc. nous allons donc utiliser la notation $a_k = q + k$ . Essayons de trouver une relation de récurrence:

$a_{k+1} - N^2 = ((q+k)+1)^2 - N = (q+k)^2 + 2 (q+k) + 1 - N$

En réarrangeant les termes, on a donc:

$a_{k+1} - N^2 = (q+1)^2 - N + 2(q+k) + 1$

Nous voyons donc que:

$\boxed{ a_{k+1}^2 - N = a_k ^2 - N + 2 a_k + 1}$

Il reste maintenant à voir sur un exemple pratique comment utiliser cette relation de récurrence pour exécuter la méthode de Fermat.

Un exemple donné par Fermat lui-même

Fermat avait expliqué cette méthode dans une lettre datant de 1643 et dans laquelle il expliquait comment factoriser le nombre 2 027 651 281:

Fermat explique sa méthode.

(Cette image est extraite de: Œuvres de Fermat, publiées par les soins de MM. Paul Tannery et Charles Henry sous les auspices du Ministère de l’instruction publique. On peut trouver ce livre en ligne ici !)

Voici ce que l’exemple de Fermat donne sous forme de tableau (avec des notations modernes):

Chaque nombre de la dernière colonne s’obtient en faisant la somme des deux nombres au-dessus.

Vous voyez que ce tableau est très facile à remplir car:

$a$ augmente de 1 à chaque fois
$2a+1$ augmente de 2 à chaque fois
$a^2-N$ s’obtient en faisant la somme des deux cases situées au-dessus (à la manière du triangle de Pascal) et cela vient de la relation de récurrence que nous avons exhibée plus haut. Il n’y a donc aucune multiplication à faire, ni aucun carré à calculer ! (à part pour la première ligne bien sûr).

Dans l’exemple ci-dessus, on s’est arrêté dès qu’on est tombé sur un carré dans la dernière colonne: en effet, on a 1040400 = 1020² et donc, comme énoncé par Fermat dans son texte, on a

$N = 45 041^2 -1020^2 = (45 041+1020)(45 041-1020) = 46 061 \times 44 021$

Remarque: Comme vous l’avez sans doute constaté dans la lettre, Fermat savait directement reconnaître si un nombre n’est pas un carré, s’épargnant ainsi un calcul de racine carrée. Il utilisait la condition nécessaire suivante: si un nombre est un carré alors ses deux derniers chiffres sont 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, ou 96 (mais attention, ce n’est pas une condition suffisante). Dans l’exemple ci-dessus, vous voyez tout de suite dans la dernière colonne que les seuls nombres qui peuvent potentiellement être des carrés sont 499 944 et 1 040 400.

Retour sur la blague de Mersenne

J’ai implémenté la méthode de Fermat en Python et pour $N=100 895 598 169$ (donc $q=E(\sqrt{100 895 598 169}) = 317640$ ), on trouve qu’il faudrait $k=187723$ étapes avant que l’algorithme se termine ! Et on a alors

$a^2-N=(q+k)^2 - N = (317640+187723)^2 - 100 895 598 169 = 154496163600$

qui est le carré de $b=393060$ . Ainsi, on a

$N=(a+b)(a-b) = (q+k +b) (q+k -b)$

donc

$N= (317640+187723+393060) \times (317640 + 187723 - 392060)$

c’est-à-dire

$N= 898423 \times 112303$

On retrouve bien la réponse donnée par Fermat à Mersenne. Cependant, il est très peu probable que Fermat se soit tapé à la main le calcul des 187 723 étapes (sauf s’il aimait se faire mal…) et il n’a donc probablement pas utilisé cette méthode pour répondre au problème de Mersenne (mais au moins ça nous a donné une occasion de parler de cette méthode…). Mais alors, comment ce filou a-t-il donc fait, nom d’une pipe en acajou ?

Des explications possibles

Voici ci-dessous trois hypothèses possibles (la plus probable et la plus vraisemblable étant la première je pense):

Hypothèse n°1: les nombres parfaits multiples

Si on retranscrit fidèlement la correspondance de Fermat, le problème de la factorisation du nombre 100 895 598169 intervient à l’intérieur d’un problème sur les nombres parfaits multiples. Voici un extrait plus long de la lettre de Fermat à Mersenne:

La note de l'éditeur des Ouvres de Fermat contient une hypothèse possible sur la factorisation.

La note (1) de l’éditeur des Œuvres de Fermat contient une hypothèse possible sur la factorisation de 100 895 598 169.

Traduction : Ce que demandait plus globalement Mersenne à Fermat, c’est de dire si oui ou non la somme des diviseurs propres (« parties aliquotes ») du nombre:

$N = 214 748 364 800 000 \times 11 \times 19 \times 43 \times 61 \times 83 \times 169 \times 223 \times 331\times 379\times 601 \\ \times 757 \times 961 \times 1201 \times 7 019 \times 823 543 \times 616 318177 \times 6 561 \times 100 895 598 169$

est égale à un multiple de $N$ (les diviseurs propres sont les diviseurs de N différents de N). Une explication probable du raisonnement que Fermat aurait suivi pour factoriser 100 895 598 169 est donnée par la note de l’éditeur des Oeuvres de Fermat (de l’édition que j’ai cité plus haut dans l’article). Mais, telle qu’elle est écrite, on n’y comprend rien, donc la voici rédigée dans le fichier PDF ci-dessous :

Comment Fermat a-t-il factorisé 100 895 598 169 ?

Il s’agit de l’explication la plus probable car elle permet de répondre en même temps aux deux questions que Mersenne posait.

Hypothèse n°2: l’astuce de calcul ad hoc

Fermat se serait rendu compte que sa méthode n’aboutirait pas rapidement et donc, plutôt que de factoriser $N$ , il se serait dit « pourquoi ne pas factoriser un multiple de $N$ , quitte à rediviser par ce multiple ensuite ? » Et voici ce que ce qu’il aurait peut-être fait: il aurait multiplié $N$ par 32, ce qui donne $32 N = 3228659141408$ et il se serait rendu compte que ce nombre est presque un carré. Plus précisément, $32 N +1 =3228659141409 = (1796847)^2$ (rappelons que Fermat savait reconnaître rapidement si un nombre n’est pas un carré et qu’il savait extraire une racine carré sans trop de difficulté). Ainsi,

$32N = (1796847)^2 - 1 = (1796847+1) (1796847 -1) = 1796848 \times 1796846$

Puis, il suffit de diviser par 32, en remarquant que le premier facteur est divisible par 16 et le deuxième est divisible par 2:

$N = \dfrac{1796848 }{16} \times \dfrac{1796846}{2}$

et donc on trouve bien:

$N = 112 303 \times 898 423$

L’idée de trouver une décomposition en différence de deux carrés d’un multiple de $N$ est l’idée de base d’un crible moderne appelé crible quadratique, où le principe est de chercher deux nombres $a$ et $b$ tels que $a^2 \equiv b^2 \mod[N]$ . On peut imaginer que Fermat avait eu l’intuition de cette méthode déjà à l’époque.

Hypothèse n°3: la méthode de Daniel Perrin

Daniel Perrin a donné une autre explication possible, mais je ne vais pas rentrer dans les détails de celle-ci (car cet article commence à devenir un peu long !). Vous pouvez lire cette explication très intéressante (qui est un raffinement de la méthode de Fermat) en annexe de ce document qu’il a posté sur sa page.

Quelques notes en guise de conclusion:

■ En pratique, la méthode de factorisation de Fermat est plutôt longue, et le nombre d’étapes nécessaires est en moyenne souvent très élevé. Elle n’est donc quasiment pas utilisée de nos jours, mais elle a donné naissance à d’autres algorithmes comme la méthode de Dixon et la très efficace méthode du crible quadratique.

■ Dans sa réponse, Fermat affirmait que 898 423 et 112 303 sont des nombres premiers. Pour le vérifier, Fermat a sans doute utilisé la méthode du crible d’Ératosthène. Par exemple, comme la racine carrée de 898 423 est environ 947, il suffit de montrer que 898 423 n’est divisible par aucun des nombres premiers inférieurs ou égaux à 947 (en faisant une bête division euclidienne). Sachant qu’il n’y a que 161 tels nombres premiers, cela pouvait se faire à la main en l’espace d’une journée. Dans le cas de 112 303, il n’y a que 67 nombres premiers à tester.

■ Ce problème de la factorisation de N=100 895 598 169 est cité dans l’article Wikipédia sur le petit théorème de Fermat:Contrairement à ce qui est suggéré, le petit théorème de Fermat n’a pas du tout été utilisé et ne permet certainement pas de donner les facteurs de la décomposition d’un nombre qui n’est pas premier ! Tout au plus il permet de montrer que N n’est pas premier mais utiliser ce théorème pour cela serait une douce folie car il faudrait montrer que:

$\exists a : a^{100895598168} \not\equiv 1 \mod [100895598169]$

ce qui du point de vue du calcul, serait plutôt long…. surtout si, comme Fermat, vous n’avez pas de calculatrice ! (Heureusement, de nos jours on possède de rapides ordinateurs et on peut voir en une fraction de seconde que si a=2 alors le reste n’est pas 1).

Références:

✓ Voici un article détaillant la note de l’éditeur qui donnait la méthode probable utilisée par Fermat. (c’est de cet article que je me suis inspiré pour rédiger l’hypothèse n°1 et, pour ça, j’ai dû me mettre à l’italien… Faut être polyglotte pour faire des maths, je vous jure…):
Giuseppe Palamà – Su di una regola di Fermat per la fattorizzazione dei numeri e su di una sua questione relativa alle parti aliquote.

✓ Pour l’aspect historique de l’étude des nombres multiples parfaits (y compris le résumé des correspondances entre Fermat, Descartes, Mersenne et d’autres), vous pouvez consulter le chapitre I de:
L.E. Dickson – History of the Theory of Numbers, Volume I: Divisibility and Primality

Cet article, publié dans Arithmétique, est tagué 100895598169, 112303, 898423, factorisation, Fermat, Mersenne, nombre premier. Ajoutez ce permalien à vos favoris.

16 commentaires pour Savez-vous factoriser à la mode de Fermat ?

Céline dit :

18 Mai 2014 à 10 h 13 min

Merci, c’est toujours un plaisir de lire vos articles

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  18 Mai 2014 à 10 h 50 min
  
  Merci, content de voir que ça plait 🙂
  
  J’aimeJ’aime
  
  Réponse
Dr. Goulu dit :

18 Mai 2014 à 13 h 50 min

Merci beaucoup et bravo d’avoir répondu à la question que je me posais depuis plus de deux ans dans http://www.drgoulu.com/2012/04/15/comment-produire-des-nombres-premiers/ !

Je suis toujours épaté par l’ingéniosité des cerveaux humains lorsqu’ils ne pouvaient utiliser que du papier et un crayon en lieu et place d’ordinateur…

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  18 Mai 2014 à 20 h 29 min
  
  Je suis bien d’accord, et on le voit même de nos jours, les limites des ordinateurs pour factoriser des grands nombres a poussé les mathématiciens à trouver des méthodes de plus en plus performantes !
  
  J’aimeJ’aime
  
  Réponse
Vαλεnτιn (@Shadowval) dit :

27 Mai 2014 à 20 h 50 min

Vraiment très intéressant comme article, très complet et bien rédigé ! C’est assez impréssionnant de comprendre ceci, je cherchais depuis pas mal de temps un article sur le sujet.

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  6 juin 2014 à 17 h 47 min
  
  Merci 🙂
  
  J’aimeJ’aime
  
  Réponse
MEHAYE Olivier dit :

4 juin 2014 à 15 h 29 min

Merci pour vos explications qui sont claires et bien détaillées… un véritable plaisir de vous lire.
Pour ma part, je souhaiterais modestement vous faire part d’une méthode que je viens d’élaborer dans des conditions que l’on pourrait qualifier de rocambolesques… Je n’en dis pas plus (ça s’appelle du teasing…) mais je serais sincèrement honoré si vous preniez le temps de l’examiner car il s’agit, j’ose le penser, d’une méthode inédite qui ne manque pas d’intérêts… Si FERMAT l’avait eu (pour reprendre l’anecdote du « challenge » de MERSENNE), je pense qu’il aurait sûrement mis moins de temps pour obtenir le résultat escompté. Peut-être que je m’avance… Ça serait super sympa de me donner votre avis sur la chose… Par avance merci à tous ! Olivier
Voici le lien qui vous conduira à mon blog : http://factorisation2014.over-blog.com/2014/05/factorisation-ou-le-big-bang-des-nombres.html
A+

J’aimeJ’aime

Réponse
- Dr. Goulu dit :
  
  4 juin 2014 à 16 h 12 min
  
  J’ai parcouru en diagonale et en vitesse votre page. Bien qu’elle ne soit pas formatée comme un article de maths ni comme un blog (pourquoi avez vous écrit une si longue page plutôt que plusieurs articles qui se suivent ?), je trouve votre approche « naïvement intéressante ».
  
  Certains mots clés (modulo) m’ont fait me demander si vous connaissiez les méthodes modernes de factorisation comme le https://fr.wikipedia.org/wiki/Algorithme_de_factorisation_par_crible_sur_les_corps_de_nombres_g%C3%A9n%C3%A9ralis%C3%A9 , qui est à ma connaissance la méthode actuelle la plus efficace. Cette méthode a été utilisée pour cracker RSA-768 en 2009 (avec de gros moyens de calcul)
  
  A mon humble avis vous devriez écrire votre algorithme sous forme de code et évaluer sa complexité O(n) (sans oublier la complexité de la construction d’une éventuelle table…) et la comparer à celle de cette méthode. Pour factoriser un nombre de 10 chiffres, la factorisation par crible sur les corps à besoin d’environ 14000 opérations, soit beaucoup moins que la racine du nombre qui vaut au minium 100’000 …
  
  J’aimeJ’aime
  
  Réponse
  - MEHAYE Olivier dit :
    
    4 juin 2014 à 17 h 04 min
    
    Je suis bien incapable d’écrire la moindre ligne sous forme de code ! Il y a seulement deux ans de cela, je ne connaissais même pas le terme « algorithme » que je veux d’ailleurs toujours écrire avec un « y » ! J’ai passé une bonne partie de ma vie la tête dans les précis de Droit… Ma culture scientifique se résume à quelques cours de math (avec accent québecois) sur You Tube, trois ou quatre lectures de blogs (dont celui-ci qui est vraiment super intéressant) et des heures passées à me prendre les pieds dans de modestes systèmes d’équations que je n’avais pas revus depuis ….houuu, bien longtemps. En bref, je suis une hérésie à moi tout seul !! Ceci dit (et j’en ai été le premier surpris), la méthode que je propose, en dépit de ses contours très… approximatifs, fonctionne le plus souvent… Tout du moins a-t-elle fonctionné jusqu’à présent sur la grande majorité des semi-premiers testés et en particulier -pour en revenir au présent article- pour le défi lancé à FERMAT par MERSENNE : 12 chiffres / Moins de 100 calculs. Par ailleurs, comme je l’écris dans mon Blog…pourri (Je vais revoir cela ! désolé !), je pense qu’en l’état, cette méthode est loin d’être aboutie et de ce fait offre à mon sens, de par les premiers résultats obtenus, de bonnes perspectives pour la recherche… Mais en disant cela, je fais déjà preuve d’arrogance ! Si cela pouvait inspirer un tant soit peu un VRAI matheu, j’en serais assez fier et quelque part j’aurais déjà un petit peu gagné mon pari… Pour l’heure, je poursuis cette démarche empirique en explorant le plus souvent possible cette table factorielle qui est, pour moi, une source permanente d’inspiration (y a quand même beaucoup de déchets !). Comme je le laisse entendre in fine dans mes explications, je suis sincèrement convaincu que la Solution au problème de la factorisation peut être révélée grâce à cette table. Je pense d’ailleurs avoir trouvé quelques pistes très intéressantes dans la continuité de la méthode que je présente. Je les exposerai prochainement… Encore merci
    
    J’aimeJ’aime
    
    Réponse
- blogdemaths dit :
  
  6 juin 2014 à 17 h 46 min
  
  Bonjour Olivier,
  
  Tout d’abord je vous remercie de vos compliments sur mon blog et mes articles et je suis heureux de voir que mes articles vous plaisent.
  
  Concernant votre méthode, je dois dire que cela fait trois jours que j’essaye de lire votre explication mais je n’arrive toujours pas à comprendre comment appliquer votre méthode pour factoriser un nombre aussi petit que 21 par exemple. Je ne pourrais donc pas vous dire grand chose sur celle-ci… Mon avis serait donc que vous puissiez expliquer comment factoriser 21 sans utiliser de tableur, juste à la main, en détaillant chaque calcul ! (je n’ai pas non plus compris cette histoire de parabole à deux têtes ou parabole sommet non plus je dois dire…)
  
  Donc, désolé !
  
  J’aimeJ’aime
  
  Réponse
Olivier MEHAYE dit :

6 juin 2014 à 20 h 50 min

C’est en fait très simple…juste très mal expliqué…Pourtant je me suis appliqué !! J’ai fait de jolis graphiques… Décidément la planète Math n’est pas la mienne…Pas facile de faire coutume ! Je maudis parfois le jour où j’ai fait ce pari !!
Je vais essayer de laisser tomber l’aspect « romantique » de cette méthode pour en aborder directement la partie calcul. Si vous me le permettez, je me garde quelques petites astuces pour la prochaine page de mon blog (que je vais remanier dès que j’aurai deux minutes… pour faire plaisir au malicieux Dr GOULU !). Donc comment est-ce que je procède, de manière basique ? Prenons l’exemple de 21 :
1/ Je calcule la racine carrée de 21 : 4.5825….
2/ Je calcule l’arrondi supérieur de cette valeur : 5
3/ J’élève au carré 5 : 25
4/ Je considère le point de coordonnées (5,25) comme sommet d’une parabole d’équation
Y = -X²+2*5*X (ce que j’appelle la parabole à sommet unique. Laissons tomber l’autre type de paraboles… Parabole « double-tête… Je vais au plus simple)
5/ Je calcule, grâce à un modeste système d’équations, les deux points d’intersection de cette parabole avec la droite Y=21.
6/ Pour 21, miracle (muum…), nous trouvons les deux facteurs premiers de 21 que sont 7 et 3. En fait, coup de bol, car l’on est tombé sur la bonne parabole « distributive » des facteurs de 21. Mais c’est assez rare car naturellement il faut que l’abscisse du sommet de parabole soit égal à (X+Y)/2—-> pour 21 : (7+3)/2 = 5. En gros, si X et Y sont relativement proches en valeur, cela peut fonctionner… Muuummm… On peut également prendre la parabole suivante et puis l’autre…Non, ce n’est pas du tout efficace…
Concernant le semi-premier proposé par VERSENNE à FERMAT (100 895 598 169), bien entendu cette première parabole ne fonctionne pas, puisque les valeurs en abscisse des deux points d’intersection sont 318095,655913851et 317186,344086149. Alors, je poursuis…

7/ Pour ce deuxième calcul, je ne prends plus en compte la droite Y= 100 895 598 169 mais Y= 2*100 895 598 169 (dans certains cas, comme celui-ci, pour réduire le nombre de calculs sans intérêt, je ne multiplie le semi-premier que par un nombre pair ou impair… En fait cela dépend de la valeur modulo 9 du semi-premier). Et je procède de la même manière en calculant les deux points d’intersection de cette droite avec la parabole dont le sommet se situe « juste au dessus », comme pour 21. Là encore, aucun entier naturel n’est révélé par cette opération : 449685,926154585 et 448738,073845415… Bof…

8/ Et je continue ainsi…jusqu’à 32 (la 16ème ligne)… et là très intéressant puisque nous obtenons deux valeurs qui sont deux entiers naturels : 1796848 et 1796846. Sachant que 1796848 * 1796846 / 32 = 100 895 598 169 et que 32 = 2*2*2*2*2, pour le cas présent (ce n’est pas toujours le cas, il y a d’autres astuces), il suffit de prendre les valeurs révélées et de les diviser par 2 jusqu’à plus soif. Ainsi 1796848/2/2/2/2 = 112303 et 1796846/2 = 898423… les deux facteurs premiers du nombre de VERSENNE. Au total, moins de 100 calculs.

Comme je l’explique, ce n’est pas toujours aussi idyllique mais la base est toujours la même. En réalité, ces points d’intersection (et en particulier les entiers que nous recherchons) sont tous des multiples de X et de Y et c’est la valeur que l’on multiplie au semi-premier qui en « contient » les facteurs. A nous de savoir les distinguer (avec un nombre pair c’est plutôt facile) ou bien alors, repasser l’une des valeurs dans la machine… mais d’une certaine manière.

Bon, je crois que je me suis encore embourbé dans mes explications… Vous me dîtes ? Merci de votre compréhension !

Désolé, en plus, pour tout vous dire, je suis très pressé. En ce moment, je n’ai que très peu de temps à consacrer au math ! Pardon pour les fautes d’orthographe…Pas le temps de relire….A+

Olivier

J’aimeJ’aime

Réponse
Olivier MEHAYE dit :

11 juin 2014 à 21 h 09 min

Je suppose que tout le monde est parti en vacances…

J’aimeJ’aime

Réponse
Damide dit :

1 avril 2015 à 16 h 53 min

Bonjour,
Bravo pour votre démonstration.
Juste une petite remarque qui me semble sympa:100 895 598 169 +2= 100 895 598 171premier

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  1 avril 2015 à 18 h 32 min
  
  Merci !
  
  Par contre, il me semble que 100 895 598 171 n’est pas premier car il est divisible par 3…
  
  J’aimeJ’aime
  
  Réponse
Ping : Comment trouver des nombres premiers | Pourquoi Comment Combien
Este Ban dit :

23 mars 2022 à 0 h 00 min

« il faudrait montrer que:

\exists a : a^{100895598168} \not\equiv 1 \mod [100895598169]

ce qui du point de vue du calcul, serait plutôt long…. surtout si, comme Fermat, vous n’avez pas de calculatrice ! (Heureusement, de nos jours on possède de rapides ordinateurs et on peut voir en une fraction de seconde que si a=2 alors le reste n’est pas 1). »

Heu… Je ne suis pas mathématicien (je suis informaticien) mais ce truc tu le fais en moins de 10 minutes à la main. Pas besoin d’ordinateur ou de calculatrice

J’aimeJ’aime

Réponse

Laisser un commentaire Annuler la réponse.

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.