0.2.4 Les progressions arithmétiques

Lemme 0.2.2   Soit un entier postif $d$. Si une suite d'entiers est solution d'une équation de récurrence linéaire à coefficients constants et entiers, alors la suite de ses restes par rapport à $d$ est ultimement périodique (^0.15).

Preuve. En effet, la suite des restes $r_n$ en question vérifie la même équation, modulo $d$. Notons $s$ le degré de celle-ci. Il y a exactement $s^d$ suites de $s$ éléments parmi $0,1,\cdots,d-1$. Il y a donc deux indices $p$ et $q$ pour lesquels les $s$ éléments consécutifs de la suite des $r_n$ sont les mêmes à partir de $r_p$ et $r_q$. On a donc $r_{p+i}=r_{q+i}$ pour tout $i$.$\qed$

A titre d'illustration, voici les premiers restes modulo $5$ de la suite définissant la numération de Zeckendorf.

$$1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,2,\ldots$$

On y voit la répétition de $1,2$. Avec les notations de la démonstration, $p=1$ et $q=21$. Cette suite est donc périodique de période $21$ puisque chacun de ses éléments est la somme des deux précédents.

Proposition 0.2.3   Soit un système de numération abstrait $S=(\Sigma,<,L)$. Le langage $L$ est régulier si et seulement si les progressions arithmétiques $a+b{\rm I\!N}$ sont $S$-reconnaissables.

Preuve. Comme $L=r_S({\rm I\!N})$, il est régulier si les progressions arithmétiques sont $S$- reconnaissables. Inversement, supposons que $L$ soit régulier et vérifions que $A=r_S(a+b{\rm I\!N})$ est régulier. On adopte les notations utilisées dans la Proposition . En vertu du lemme précédent, les suites $u_n(p)$ et $v_n(p)$, $p\in K$, sont ultimement périodiques modulo $b$. Notons $T$ une période commune et $N$ le maximum des longueurs des parties non périodiques. Les états de l'automate minimal de $A$ sont les ensembles

$$w^{-1}.A=\{x\in \Sigma^*\vert val_S(wx)\equiv a \mod b\}, w\in\Sigma^*.$$

En vertu de la Proposition , pour $w$ assez long(^0.16), $w^{-1}.A$ est donc un des ensembles de la forme

$$\{x\in \Sigma^*\vert val_k(x)+v_{\vert x\vert+i+N-1}(s)-v_{\vert x\vert-1}(s) +\sum_{l\in k}j_lu_{\vert x\vert}(l)\equiv a \mod b\},$$

où $k\in K$, $i\in\{0,\ldots,T-1\}$ et, pour tout $l\in K$, $j_l\in\{0,\ldots,b-1\}$. L'automate minimal de $A$ est donc fini.$\qed$

La propriété ci-dessus montre que, dans chaque numération de position classique, et en particulier en base $10$, les caractères de divisibilité sont caractérisés par des propriétés syntaxiques des mots représentant les nombres dans l'alphabet des chiffres. On peut donc détecter le fait qu'un nombre soit divisible par un autre par la forme de la suite des chiffres exprimant ce nombre, forme qui dépend du diviseur et de la base. La syntaxe des multiples de $5$ en base $10$ (se terminer par 0 ou $5$) est extrêmement simple. Pour d'autres diviseurs ou d'autres bases, elle peut être trop compliquée pour être utilisée en pratique. C'est le cas du diviseur $3$ en base $10$: les multiples de trois forment un langage régulier décrit par une expression régulière trop complexe pour que l'on puisse juger d'un simple coup d'oeil si un nombre est multiple de trois.