Comment factoriser F5 ?

Bonsoir

Connaissez-vous une autre méthode arithmétique que celle d'Euler pour factoriser F5 = 4 294 967 297,
sans calculatrice programmable (donc autre que le crible d’Ératosthène, et autre que les divisions jusqu'à la racine carrée) et sans savoir a priori que l'un des facteurs est "petit" ?

Merci d'avance, bonne soirée.

Réponses

  • Bonsoir.

    Quand on sait que \( 4294967297 = 2^{2^5}+1 \) (et qu'on s'appelle Euler), on sait que les facteurs premiers s'écrivent \( p = k\times2^7 + 1\) avec \( k \) entier.
    On essaye jusqu'à \( k = 5 \), ce qui donne \( p = 641 = 625 + 16 = 5^4 + 2^4 \). Un petit calcul de congruences permet de conclure.

    e.v.
    Personne n'a raison contre un enfant qui pleure.


  • Je rapporte ce que j'ai vu un jour dans un exercice de Bourbaki. D'abord, il bien connu (sic) que l'on a la factorisation :
    $$
    1 + a^4(1+ab-b^4) = (1 + ab) \times (1 - ab + a^2b^2 - a^3b^3 + a^4)
    $$
    Je corrige mon mensonge : il s'agissait de dire pourquoi le membre de gauche est divisible par $1+ab$. Justification : quand on raisonne modulo $1+ab= 0$ i.e. modulo $ab = -1$, on voit que $a^4(1+ab-b^4) = a^4 \times (-b^4) = -1$, ce qui, ajouté à $1$ donne bien $0$. J'ai tenu ici à expliciter la factorisation.

    Le rapport avec la choucroute ? Quand on fait $a = 2^7$, $b = 5$, on obtient, comme par miracle :
    $$
    1 + ab - b^4 = 1 + 128 \times 5 - 25^4 = 1 + 640 - 625 = 16 = 2^4
    $$
    Dingue, non ? Car alors :
    $$
    1 + a^4(1+ab - b^4) = 1 + (2^7)^4 \times 2^4 = 1 + 2^{28} \times 2^4 = 1 + 2^{32} \qquad \hbox {the so called} \quad F_5 = 2^{2^5}
    $$
    Re-dingue, non ? J'avoue ne pas avoir compris d'où l'auteur de l'exercice sortait ce machin. J'en ai juste déduit que nous n'étions pas tous faits du même moule.
  • Merci pour vos réponses,

    Je vais essayer de comprendre la méthode d'Euler (géniale et un peu difficile pour moi...)

    Pour l'exo de Bourbaki, il me semble que c'est la division euclidienne de F5 par 1 + ab...

    avec un choix heureux de a et b ( ce qui en effet s'appelle avoir de la moule!)

    Bonne soirée.
Connectez-vous ou Inscrivez-vous pour répondre.