Une histoire assez fantastique.
Il s'agit de celle de M. Raymond Parmentier, né en 1912 (95 ans !), qui après avoir gagné sa vie dans un commerce de "beurre, oeufs et fromages" s'est mis à faire des maths, essentiellement en arithmétique. Il aime à résoudre des petits problèmes et poser des casse-têtes mathématiques. Il y a 6 mois, me parvient, via un collègue de l'université qui connait le fils de M. Parmentier, deux cahiers d'écoliers, remplis de tas de calculs sur des nombres (en particulier sur les nombres premiers) et des opérations. Ces cahiers sont difficiles à lire, très difficile, il y a des tas d'exemples de calculs, exemples donnant naissance à autant d'algorithmes, mais il n'y a pas d'explications. (Combien d'heures ai-je passé pour déchiffrer une partie seulement de ces deux cahiers!)
Sur un des deux cahiers, il annonce pourtant la couleur dès le début : il veut trouver explicitement une suite infinie de nombres premiers !
Pendant un grand nombre de pages il fait des calculs sur des exemples pour trouver ce qu'il nomme la "cadence" d'un entier, cette "cadence" lui permettant de décider de la primalité possible d'un entier. Après plusieurs essais (avec maple) pour programmer correctement son calcul de cadence, puis après consultation de la bibliothèque Sloane sur les suites et bien, ce monsieur Parmentier a tout simplement redécouvert le concept de l'ordre de l'élément 2 dans le groupe multiplicatif des éléments inversibles de l'anneau Z/nZ ! (n est supposé impair car il est susceptible d'être un premier). Bravo d'autant plus que pour faire ses calculs, il n'utilise que le papier crayon et la simple calculette 4 opérations à 10 chiffres, celle de tout vendeur de fromages. Il semble ignorer la littérature.
Mais ce n'est pas tout, il utilise implicitement le fait que tout premier (>3) est de la forme 6n+-1, et que cela peut s'écrire efficacement dans un calcul modulo 24, qui permet d'améliorer considérablement le petit théorème de Femat.
Voici ce que cela donne : une session maple comparant le test de primalité de Fermat et celui qu'il semble faire fonctionner sur des exemples.
> testFer:=proc(n)
> if n mod 3 >0 and 2^(n-1) mod n=1 then return(n) fi:
> end:
> a:=time():F:=[seq(testFer(2*m+1),m=100..100000)]:time()-a;
10.563
> NF:=select(u->not(isprime(u)),F):nops(NF);
89
> testPar:=proc(n)
> local x,Lp,Lm;
> Lp:={5,11,13,19}:Lm:={1,7,17,23}:
> if n mod 3 >0 then x:=2^((n-1)/2):
> if n mod 24 in Lm and x mod n=1 then return(n)
> else if n mod 24 in Lp and (x+1) mod n=0 then return(n) fi:fi:fi:
> end:
> a:=time():P:=[seq(testPar(2*m+1),m=100..100000)]:time()-a;
6.858
> NP:=select(u->not(isprime(u)),P):nops(NP);
39
> convert(NP,set) minus convert(NF,set);
{}
Ce test est nettement plus précis (39 non premiers au lieu de 89) et rapide !
De fait, via deux astuces, c'est une version améliorée et efficace du petit théorème de Fermat.