À propos des puissances de 2

JLapin

stfj a dit :

@JLapin: peut-être ai-je mal recopié. N'a-t-on pas, en base dix, $864199883=7\times1234571269$ ?

Tu as oublié un 8.

Et pourquoi serait-il si évident pour un écolier de 10 ans que 8641998883 est un multiple de 7 (en tout cas plus simplement qu'en posant la division et en calculant le reste) ?

stfj

@JLapin : bonjour . Oui, désolé, j'avais oublié un $8$. Je te propose de me faire un peu confiance. C'est une numération que j'ai pratiquée.
En numération primorielle, $8,641,998,883$ s'écrit $$1\times29\#+9\times23\#+16\times19\#+18\times510510+2\times30030+11\times2310+0\times210+4\times30+2\times6+0\times2+1\times1$$, ce que l'on écrit en adoptant la notation de l'On line Encyclopedia of Integer Sequences, $(1:9:23:16:18:2:11:0:4:3:2:0:1)$ [remarque : par définition, $17\#=510510\text{    }; 19\#=9,699,690\text{    }; 23\#=223,092,870\text{    }; 29\#=6,469,693,230$]
Je te rappelle qu'un entier existe indépendamment de la numération que l'on choisit pour l'écrire. On peut donc parler de l'entier écrit en numération primorielle $$(1:9:23:16:18:2:11:0:4:3:2:0:1)$$cela le définit entièrement, indépendamment de son écriture en base dix donnée plus haut, le passage de la numération en base dix à la numération primorielle et inversement se faisant simplement, en particulier de façon immédiate pour un calculateur d'une machine ( ordinateur, ordinateur personnel, assistant personnel intéractif, calculatrice de poche,...)
   Revenons alors à notre écolier de 11/12 ans(10 c'est sans doute un peu prématuré) : 
On apprend très vite, disons après 4 heures sur la numération primorielle que
* les entiers pairs sont ceux qui se terminent par $(...:0)$;
* les entiers multiples de trois qui ne le sont pas par deux sont ceux qui se terminent par $(1:1)$;
* les entiers multiples de cinq qui ne le sont ni par deux ni par trois sont ceux qui se terminent par $(....:0:2:1)$ ou $(...:4:0:1)$;
Vient alors le critère de divisibilité similaire par sept. Je vais aller vite : l'idée est que ce sont ceux qui sont congrus à $7, 49,  77, 91, 119, 133, 161, 203$ modulo $210$. Autrement écrit en numération primorielle $(0101), (1301), (2221), (3001), (3421), (4201), (5121), (6321)$. Aucun grand mystère dans tout cela, c'est juste l'étude classique de $(\Z/210\Z)^\times$
Et là, je me rends compte que je me suis forcément trompé dans l'écriture de notre entier en numération primorielle. Mais cela peut constituer un bon exercice, n'est-ce pas? (juste quelque divisions euclidiennes à la calculatrice de poche)

JLapin

Merci pour ta réponse.

J'espère que tu reconnais tout de même que ton système ne permet pas de démontrer plus facilement/rapidement qu'avant que le nombre 8641998883 est multiple de 7 ni que 641 divise $2^{32}+1$.

stfj

Voilà, j'ai trouvé mon erreur : l'entier qu'on propose d'examiner à notre écolier de 11/12 ans qui dispose de tables contenant $$(0101), (1301), (2221), (3001), (3421), (4201), (5121), (6321),$$ nous allons lui proposer l'entier : $$(1:9:16:18:2:11:4:2:0:1).$$
Que répondra-t-il ?

stfj

@JLapin : en ce qui concerne $8641998883$, "mon" système EST plus rapide : en un coup d'oeil, même à 10 ans, on reconnaît dans la terminaison$$(4:2:0:1)$$ un multiple de $7$. C'est à peine plus difficile avec un peu d'habitude que de reconnaître un nombre pair d'un impair. Je ne comprend pas ton  "J'espère que tu reconnais tout de même que...". C'est objectivement plus rapide. 
Par ailleurs, je n'ai personnellement cure que ce système soit adopté un jour massivement. Par contre, c'est déjà un outil mathématique validé par la communauté mathématique. C'est peut-être encore l'affaire de quelques spécialistes des numérations, je ne sais pas. Mais en tout cas, c'est valide.

lourrran

Tu as parlé d'une expérience faite avec 26 enfants de 10-12 ans.
Je pense que c'est totalement biaisé.
Un prof qui enseigne sa découverte, ou plus généralement un prof qui cherche à faire partager sa passion, est un prof 100 fois plus intéressant qu'un prof quelconque, qui fait son boulot par obligation.
Il va réussir à intéresser les gamins.
Je m'intéresse beaucoup (sans participer) aux expériences de type 'Enseignement via le jeu d'échecs'. Souvent, les profs qui pilotent ça sont passionnés, et du coup, le bénéfice est double. 
Le jeu d'échecs a certainement des vertus pour apprendre à réfléchir, apprendre à ce concentrer, apprendre à raisonner. Et en plus, double effet kiss-cool, le projet est généralement porté avec passion.

Pour vérifier si un nombre écrit en base 10 est divisible par 7, on mémorise 1,3,2,-1,-3,-2 
Les 3 derniers chiffres sont cdu (centaines, dizaines, unités) , on calcule u+3d+2c 
Les 3 précédents sont cdu aussi (centaines de milliers, dizaines de milliers, milliers), on calcule  -(u+3d+2c) 
etc etc, on additionne tout ça et on regarde le résultat modulo 7. 
8641998883 -->8 641 998 883 -->-8 + (2.6+3.4+1.1)-(2.9+3.9+1.8) + (2.8+3.8+1.3) = -8+ 25-53+43=7
Ce nombre est un multiple de 7.

stfj

@lourrran : il y a une autre méthode : on regroupe à partir de la droite les chiffres de $8,641,998,883$ par paquets de trois chiffres puis on fait $$883-998+641-008=518=74\times7$$ 
donc $7|8641998883$. Cela est lié au fait que $1001=7\times11\times13$ et donne par conséquent un critère par $13$ également.
Ceci étant dit, c'est bien moins rapide que de constater que $(1:9:16:18:2:11:{\color{Blue}4:2:0:1})$ se termine par $(4:2:0:1)$. 

JLapin

@stfj Dans ce cas, il est encore plus rapide d'utiliser l'écriture en base 7 du nombre si tu veux reconnaître/faire reconnaître un multiple de 7.

La recherche de l'écriture de 8641998883 sous la forme que tu proposes avec la terminaison qui va bien nécessite beaucoup plus de calculs que la simple réduction modulo 7.

Et non, je ne crois pas qu'il existe de système magique permettant de voir que $2^{32}+1$ est un multiple de 641 ou de trouver à la main la décomposition en facteurs premiers de $2^{64}+1$ ou $2^{128}+1$.

stfj

@JLapin : je peux expliquer à quel point il est simple de montrer que $641|F_5$ dans le cadre d'une démarche rationnelle où l'on ne saurait pas évidemment d'avance ce que l'on cherche, en l'occurrence le facteur $641$ qui n'est jamais que le $116-$ième nombre premier, je crois. Et je maintiens que Fermat aurait sans doute trouvé ce diviseur s'il avait connu cette numération somme toute assez naturelle. $2=(1:0)$ c'est une paire; les insectes ont $6=(1:0:0)$ pattes; dans une heure, il y a deux fois $30=(1:0:0:0)$ minutes; dans une semaine, il y a $7$ jours; en breton, dix-huit se traduit pas triwec'h ($3-6$, $3$ fois $6$, ce qui s'écrit en numération primorielle $(3:0:0)$...
   Néanmoins, comme je l'ai déjà dit, AVANT de nous pencher sur ce sujet, je pense qu'il est souhaitable de nous arrêter sur l'écriture des puissances de $2$ en numération primorielle : c'est un sujet à lui tout seul, où il peut être question de la notion d'ordre multiplicatif, de tables de l'OEIS où ces ordres sont tabulés, du fait que $F_6=18446744073709551617\equiv17[\text{modulo }30030]$ et qu'il suffit de regarder son écriture en numération primorielle pour s'en convaincre. Bref une foule de jolis résultats avant de nous pencher sur la tombe de Fermat

lourrran

Un nombre est un nombre.
Sa représentation dans une base décimale (ou binaire ou hexadécimale, c'est le même concept), ou primorielle ou autre n'est qu'une représentation.
Ce système d'écriture primorielle est valide. Il fonctionne, il ne mène pas à des erreurs.
Ok.
 
On parle ici de tester des nombres, pour vérifier s'ils sont premiers. 
Aujourd'hui, les nombres 'intéressants' pour ces questions ont combien de chiffres en écriture décimale ?  Je crois qu'on parle de nombres qui ont 2000 chiffres en écriture décimale.
Donc en gros, disons 1000 chiffres en écriture primorielle, pour fixer les idées. (ça doit être beaucoup moins en fait)
Et donc, pour ces nombres, l'écriture primorielle permet de tester très facilement s'ils ont un diviseurs premier parmi les 1000 plus petits nombres premiers.
Mais il reste à tester quelques centaines de milliards de diviseurs premiers potentiels.

stfj

@lourrran : ce que tu écris est juste. En ce qui me concerne, en utilisant la numération primorielle, j'ai créé un programme qui me décompose des nombres entiers jusqu'à $19$ chiffres je crois. Je sais que c'est ridiculement peu par rapport aux logiciels existants mais au moins je l'ai fait tout seul . Malheureusement à partir de 20 chiffres, le programme peut tourner pendant toute une journée pour casser un entier. Par contre, ça fait longtemps que je m'y suis pas replongé, mais je me rappelle qu'il cassait certains entiers à $100$ ou $200$ chiffres. Je me demande si ces entiers particuliers ont été considérés comme des failles à boucher par les systèmes de protection Peu de littérature sur le sujet évidemment. Récemment une somme récapitulative d'une équipe d'australiens parmi lesquels Anthony Overmars si je me rappelle bien.

stfj

Pour ceux que ça intéresse, suite aux discussions précédentes, ici,  §§$13$ et $14$.

stfj

Pour ceux qui le souhaitent, il y a un sujet similaire à traiter : l'écriture des puissances de $10$ en numération primorielle. Vous pourrez observer simplement des résultats similaires, de façon encore plus frappante peut-être.