Arithmétique avec xcas

mercredi 4 avril 2012
par  Christian Mercat

Considérons la suite $(u_n)$ définie par $u_{n+3}=u_{n+1}+u_n$ avec $u_0=3$, $u_1=0$ et $u_2=2$.

Théorème : Si $p$ est premier, $u_p$ est multiple de $p$.

Preuve : Soit $\lambda_1$, $\lambda_2$, $\lambda_3$ les racines du polynôme $X^3-X-1$, les suites vérifiant la relation de récurrence sont l’espace vectoriel engendré par les trois suites géométriques de raison $\lambda_i$. La combinaison linéaire adéquate, étant donné que $\lambda_1\lambda_2\lambda_3=-1$, $\lambda_1\lambda_2+\lambda_2\lambda_3+\lambda_3\lambda_1=-1$ et $\lambda_1+\lambda_2+\lambda_3=0$, est $u_n=\lambda_1^n+\lambda_2^n+\lambda_3^n$. Ces racines sont a priori complexes, mais on peut considérer la suite dans $Z/pZ$ pour $p$ premier et on a alors $u_p=\lambda_1^p+\lambda_2^p+\lambda_3^p$ $\equiv\lambda_1+\lambda_2+\lambda_3[p]$ $\equiv 0[p]$, donc $u_p$ est multiple de $p$.

Une conjecture qui a tenu longtemps prétendait que cette condition $u_p$ est multiple de $p$ fournissait un critère de primalité de $p$. Testons la avec xcas et observons pourquoi elle a tenu si longtemps car c’est effectivement un critère de primalité pour des entiers $p$ 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 $\forall k\in N, \exists m,n\in N, 2011\times m+1=n\times 10^k$ où $k$ est le nombre de 9 recherché.

Il suffit pour cela de calculer les entiers de Bézout associés à 2011 et $10^k$ :

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, $a=b\times q+r$, $r

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

Brèves

18 octobre 2015 - Questionnaires de la CII Université

L’objectif est de collecter de nouvelles réponses pour mieux mesurer l’impact de la réforme du (...)

27 janvier 2010 - Travailler par compétences et avec le socle commun

Conférence le 10 février au CRDP de Lyon de 9 h à 12 h, avec Jean Michel Zarkhartchouk

13 novembre 2008 - Probabilités en 3e

Texte issu d’une formation aux probabilités pour les professeurs de troisième faite par Y. Ducel (...)