gégé a publier un code pour vérifier sur l'autre fil du dimanche qu'il n'y avait pas d'autres Nombre de carmichaël multiples de 109 au-delà de la liste des presque dix nombres que j'avais imprimé.
Son code fort astucieux ressemble sous plusieurs de ces aspect à ceux que j'utilise :
gege a écrit : ↑26 avr. 2020 20:57
[…]Comme le nombre de Carmichaël cherché est multiple de 109, il est aussi de la forme 109 * (108 * L + 1), donc j'ai fait défiler un compteur L.
Si (108*L+1) n'a pas exactement deux facteurs, on l'ignore. Ensuite on vérifie les critères de divisibilité genre (N-1) divisible par (P-1) qui vont bien.
Ca donne :
Code : Tout sélectionner
EXPORT carmi3(l)
BEGIN
LOCAL c;
109*l[1]*l[3]-1▶c;
IF 0≠irem(c,l[1]-1) THEN RETURN;END;
IF 0≠irem(c,l[3]-1) THEN RETURN;END;
PRINT({SORT({109,l[1],l[3]}),c})
END;
EXPORT carmi2(n,q)
BEGIN
LOCAL d,m,f,g;
108*q+1▶d;108*n▶n;
WHILE n≥d DO
mat2list(ifactors(d))▶f;SIZE(f)▶g;
IF 4==g THEN
IF 2==f[2]+f[4] THEN
carmi3(f);END;END;
108+d▶d;END;
PRINT(".")
END;
[…]On a bien rigolé.
G.E.
Et ce n'est pas fini !
Pour trouver le Théorème de Horner nous indique qu'aucun Nombre de Carmichaël ne peut avoir de facteur premier carré.
Les Nombre de Carmichaël sont donc tous de la forme
N=a×b×c×... où
a,b,c,... sont les facteurs premiers
distincts de sa décomposition en produit.
Cette décomposition est unique d'après le théorème fondamental de la théorie des nombres.
Pour être sûr que tous ces facteurs sont distincts, je les désigne toujours dans l'ordre alphabétique tels que
a<b<c<...
Comme il ne peut y avoir de Nombre de Carmichaël pair, on a de plus
2 < a < b < c < ...
Combien de facteurs ? Je ne sais pas. mais réfléchissons ensemble:
Un seul facteur:
Ce qui est sûr c'est que les nombres
N=a ne peuvent être de Carmichaël car tous sont premiers.
Deux facteurs:
Si l'on considère les nombres N se décomposant en
N=a×b avec
a et
b premeirs vérifiant
a<b
Si N est Nombre de Carmichaël alors (a-1) divise (N-1) et (b-1) divise (N-1). Ce qui me parait possible à priori.
Mais rappelons nous le Lemme fondamental qui considère
n=p×u où
p est premier et
u quelconque et qui affirme que
(p-1) divise
(n-1) si et seulement si (p-1) divise
(u-1).
Donc,
N=a×b est un nombre de Carmichaël si et seulement si
(a-1) et
(b-1) divisent tous deux
(N-1).
D'après le lemme fondamental,
(b-1) divise
(N-1) si et seulement si
(b-1) divise
(a-1). Or c'est impossible car
a<b implique que
(b-1) > (a-1) et donc
(b-1) ne peut en aucun cas diviser
(a-1).
Et donc il n'existe pas de Nombre de Carmichaël se décomposant en uniquement deux facteurs premiers.
Trois facteurs: C'est le cas des Nombre de Carmichaël les plus simples à déterminer. Avec un peu de chance, la méthode constructive que l'on cherche appliquée aux nombres de la forme
N=a×b×c donnera un indice pour la recherche des nombres
N=a×b×c×... se décomposant en plus de trois facteurs.
On considère donc le Nombre de Carmichaël
N=a×b×c avec
a,
b et
c trois facteurs premiers distincts tels que
2 < a < b < c. On a donc
(a-1), (b-1) et
(c-1) qui divisent tous les trois
(N-1).
Comme
a,
b et
c sont tous les trois premiers, on applique le lemme fondamental et il en résulte les trois relations triangulaires suivantes:
- (a-1) divise (b×c-1),
- (b-1) divise (a×c-1) et
- (c-1) divise (a×b-1)
Il existe donc trois entiers positifs
i,
j et
k tels que :
- b×c -1 = i × (a-1)
- a×c - 1 = j × (b-1)
- a×b - 1 = k × (c-1)
Comme
a,
b et
c sont tous les trois premiers, on a nécessairement i > 1, j>1 et k>1.
En effet, si par exemple i=1, on aurait l'égalité
b×c -1 = a-1 soit
b×c = a ce qui est impossible pour a premier.
De même pour les deux autres relations.
Comme
a,
b et
c sont tous les trois premiers impairs (donc au moins distant de deux unités), la relation d'ordre
2 < a < b < c implique que :
2 ≤ a-1 < a < a+1 < b-1 < b < b+1 < c-1 < c
Mais ce n'est pas pour autant que c peut être aussi grand que l'on veut; En effet (c-1) doit diviser (a×b-1) or, a×b est le produit des deux plus petit facteurs. Il existe donc une valeur limite pour c où il devient trop grand pour que (c-1) puisse être un diviseur.
C'est sur ce constat qu'est basé ma méthode constructive :
a donne en quelque sort l'échelle (plus a est grand plus l'amplitude de la recherche s'accroit),
b est le facteur à trouver et c est en quelque sorte la conséquence des choix pour
a et
b.
D'après la relation d'ordre on a :
b < c-1 < c
Comme k >1 on en déduit que
k×b < k×(c-1) < k×c.
Or
k×(c-1) = a×b - 1 d'où
k×b < a×b-1 < k×c
Puisque
a×b - 1 < a×b et donc finalement
k×b < a×b
On a donc un encadrement fort utile à la recherche des facteurs pour a donné;
1 < k < a
L'algorithme constructif prend forme. On se donne
a et k avec
1 < k <a et l'on recherche les facteurs premiers
b et
c.
Cherchons une expression de
b ne faisant intervenir que
a et
k.
On a déjà une relation de
b en fonction
a c j et
k:
j×(b -1) = a×c-1
Or
a×c-1 = a×c -a+a -1= a×(c-1) + a -1 = a×(c-1)+(a-1)
D'où
j×(b -1) = a×(c-1)+(a-1) dont je multiplie les deux termes par k :
On a
j×k×(b -1) = a×k×(c-1)+k×(a-1) où
k×(c-1)=(a×b-1)
On a donc :
j×k×(b -1) = a×(a×b-1)+k×(a-1) relation où b apparait en présence d'uniquement a j et k.
En factorisant :
j×k×(b-1) = a×(a×(b-1)+a-1) +k×(a-1)
j×k×(b-1) = a²×(b-1)+a×(a-1) +k×(a-1)
j×k×(b-1) = a²×(b-1)+(a+k)×(a-1)
Soit
(b-1) × (j×k-a²) = (a+k) × (a-1)
Au lieu de chercher les j qui répondent à cette égalité, je pose
D = j×k-a²
D a pas mal de propriétés qui vont nous servir à établir notre algorithme de recherche.
Primo : d'après sa définition
D est un entier
De plus on a
D MOD k = -a² donc
D n'est pas un multiple de k, mais le reste de la division euclidienne de D par k fait
-a² le diviseur étant le facteur
j.
Secondo: D est un diviseur de
(a+k)×(a-1) en effet :
(b-1) = (a+k)×(a-1)/D
De plus on a
D =(a+k)×(a-1)/(b-1)
Or d'après la relation d'ordre général : a-1 < b-1 d'où
(a-1)/(b-1) < 1 et donc
D < a+k
Voilà qu'à partir de
a donné, on a des conditions pour
k (
1 < k < a ) et qu'à chaque
k un diviseur
D de
(a+k)×(a-1) borné (
D < a+k) dont le reste de la division par
k fait
-a². tout cela me semble être bien propice à un petit algo des maisons.
Prenons par exemple : a=3 la seule valeur possible est k=2 car
1 < k < a .
Calculons
(a+k)×(a-1) = 5×2 = 10
Les diviseurs de 10 sont : 1 2 5 et 10 mais les diviseurs 5 et 10 ne sont pas à retenir car trop grands (
D < 3+2 )
Le reste de -9 divisé par 2 est 1,
D est donc impair.
Donc D ne peut prendre que la valeur D=1.
On a alors
b-1 = 10/1 soit
b=11 qui est premier.
D'où on calcule
c-1 = (3×11-1)/2 = 16 soit
c=17 qui lui aussi premier
Il nous reste à vérifier que
(a-1) divise (11×17-1) ce qui est le cas car 186 est pair.
Donc, nous avons trouvé le seul Nombre de Carmichaël se décomposant en trois facteurs premiers dont le plus petit est 3.
3×11×17 = 561 qui est en fait le plus petit des Nombre de Carmichaël. Mais aussi le seul du type
3×b×c.
C'est mon doute quand à ce dernier fait qui m'a conduit à proposer la Question/Concours d'un dimanche après midi.
Pour faire plaisir à
Marge, je vous donne en exemple l'implémentation de cet algorithme pour Hewlett Packard HP-28C/S:
- Liste Carmichaëls à trois facteurs a<b<c
- HP-28S Carmichael 3 facteurs abc.gif (76.06 Kio) Consulté 2948 fois
Cette HP n'ayant pas de fonction native pour détecter les nombres premiers, il vous faudra composer votre propre fonction de détermination.
marge pourra utiliser selon son choix l'une des deux versions suivantes:
- Vérifie si l'argument est premier
- HP-28S ISPRIME (single scan).gif (44.24 Kio) Consulté 2957 fois
- Vérifie astucieusement si son argument est premier
- HP-28S ISPRIME (dual scan).gif (69.2 Kio) Consulté 2957 fois
Evidemment, je préfère la seconde qui dispose d'un perfectionnement qui la rend bien plus efficace lorsque l'on souhaite déterminer la primalité de grands nombres.
Je mets également cette version pour le modèle historique SHARP PC-1211:
- Liste Carmichaëls à trois facteurs a<b<c
- CRM3 factor SHARP PC1211.gif (32.89 Kio) Consulté 2957 fois
Comme pour l'HP-28S, la détermination de la primalité des nombres candidats est faite 'manuellement' et donc ces déterminations ne sont effectuées que quand cela est nécessaire à cause du temps que cela prend.
Malgré tout, même le SHARP PC-1211 s'en sort bien, il lui faut moins de 2'30" pour lister les Nombres de Carmichaël se décomposant en trois facteurs premier de la forme
13×b×c.
Code : Tout sélectionner
|> | MODE DEF
|13_ | 1 3 SHIFT A
|314821.=13.61.397. | 0'24"
|115921.=13.37.241. | 0'34"
|530881.=13.97.421. | 0'54"
|46657.=13.37.97. | 1'21"
|29341.=13.37.61. | 1'46"
|> | 2'23"
Bon évidemment, le même code sur HP-Prime affiche instantanément une telle liste :
Code : Tout sélectionner
EXPORT CRM3(A)
BEGIN
0►N►M1;
FOR K FROM 2 TO A-1 DO
FOR D FROM −A*A MOD K TO A+K-1 STEP K DO
1+(A+K)*(A-1)/D ► B; 1+(A*B-1)/K ► C; (B*C) MOD (A-1) ► U;
IF U==1 THEN
IF CAS.isprime(B) THEN
IF CAS.isprime(C) THEN 1+N ► N; [A,B,C,A*B*C] ► M1(N); END;
END;END;END;END;
RETURN M1;
END;
