Arithmétique avec xcas
par
Considérons la suite 
définie par 
avec 
, 
et 
.
Théorème : Si 
est premier, 
est multiple de .
Preuve : Soit 
, 
, 
les racines du polynôme 
, les suites vérifiant la relation de récurrence sont l’espace vectoriel engendré par les trois suites géométriques de raison 
. La combinaison linéaire adéquate, étant donné que 
, 
et 
, est 
. Ces racines sont a priori complexes, mais on peut considérer la suite dans 
pour premier et on a alors 
![\equiv\lambda_1+\lambda_2+\lambda_3[p]](local/cache-TeX/98d7b21b7cc36033585ef8d18392f7da.png "\equiv\lambda_1+\lambda_2+\lambda_3[p]"){kind=small}
![\equiv 0[p]](local/cache-TeX/3dcfed8db96438304e95272334a821ed.png "\equiv 0[p]"){kind=small}
, donc est multiple de .
Une conjecture qui a tenu longtemps prétendait que cette condition est multiple de fournissait un critère de primalité de . Testons la avec xcas et observons pourquoi elle a tenu si longtemps car c’est effectivement un critère de primalité pour des entiers raisonnables.
Si on implémente la suite de manière naïve avec un double appel récursif, comme la suite de Fibonacci, on arrive rapidement à un dépassement des capacités de l’ordinateur avec une complexité exponentielle en mémoire. Voici une manière de gérer efficacement la mémoire à l’aide d’un tableau dynamique :
l:=[3, 0, 2];
u(n):={
local i;
if(n<size(l)) return l[n];
for(i:=size(l); i<=n; i++) l := append(l, l[i-2]+l[i-3]);
return l[n];
} Si la réponse est déjà dans la liste, on la lit. Sinon, on calcule tous les termes jusqu’à celui demandé et on les stocke dans la liste.
On peut alors vérifier que cela fournit un test de primalité pour les "petits" entiers :
for(k:=3; k<10000; k+=2) { if((irem(u(k),k)==0) et (non(est_premier(k)))) afficher(" "+k+" divise "+u(k));}Des multiples de 2011 avec des 9
Théorème : Il existe des multiples de 2011 qui se finissent par autant de 9 qu’on veut en base dix.
Cela signifie que 
où 
est le nombre de 9 recherché.
Il suffit pour cela de calculer les entiers de Bézout associés à 2011 et 
:
aubvd(a,b):={local u,v,d,(r:=irem(a,b)),q;
if(r==0) return [0,1,b];
[u,v,d]:=aubvd(b,r);
q := iquo(a,b);
return [v,u-q*v,d];
}qui est toujours intéressant à programmer par l’algorithme d’Euclide, 
, 
, si l’égalité de Bézout pour 
et 
est 
on en déduit celle pour 
et : 
.
Cependant, pour le concours, vous pourriez aussi utiliser la fonction xcas iabcuv qui donne directement le résultat. On peut aussi utiliser la fonction double iquorem.
On a donc le résultat final avec :
multiple9(n):={local u,v,d;
[u,v,d]:=aubvd(2011,10^n);
afficher("2011*"+(10^n-u)+"="+(2011*(10^n-u)));multiple9(5) donne 2011*52909=106399999.
Commentaires