0.3.1 Le lemme de la pompe et les nombres premiers

Commençons par exploiter le lemme de la pompe.

Proposition 0.3.1   Si $X$ est infini et si $r_k(X)$ est régulier, alors il existe des entiers $a,b,c$ et $t$ tels que

$$\forall n\in {\rm I\! N}: ak^{tn}+b\frac{k^{tn}-1}{k^t-1}+c\in X,$$

$a$ et $b$ n'étant pas simultanément nuls et $t$ étant positif. En particulier, il existe alors des rationnels $\alpha>0$ et $\beta$ tels que

$$\forall n\in {\rm I\! N}: \alpha k^{tn}+\beta \in X.$$

Preuve. En effet, d'après le lemme de la pompe, $r_k(X)$ contient un mot de la forme $uvw$, où $v$ n'est pas vide, tel que $uv^nw\in r_k(X)$ pour tout $n\in {\rm I\! N}$. Ainsi, $X$ contient les nombres

$$val_k(uv^nw)=val_k(u)k^{tn+s}+val_k(v)k^s(k^{t(n-1)}+\cdots+k^t+1)+val_k(w),$$

où $t$ et $s$ désignent les longueurs respectives de $v$ et de $w$. On peut donc prendre $a=val_k(u)k^s$, $b=val_k(v)k^s$ et $c=val_k(w)$.$\qed$

Cette proposition va nous permettre de vérifier que l'ensemble des nombres premiers n'est pas $k$-reconnaissable.

Corollaire 0.3.2   Si les éléments de $X$ sont des nombres premiers et si $r_k(X)$ est régulier, alors $X$ est fini.

Preuve. On raisonne par l'absurde. Avec les notations de la proposition précédente, si $X$ est infini, il contient les nombres

$$p_n=ak^{tn}+b\frac{k^{tn}-1}{k^t-1}+c, \ n\in {\rm I\! N},$$

qui sont tous premiers. On a

$$p_{n+u}=p_n+ak^{tn}(k^{tu}-1)+bk^{tn}\frac{k^{tu}-1}{k^t-1}\cdot$$

Nous allons voir que l'on peut choisir $n$ et $u$ pour que

$$ak^{tn}(k^{tu}-1)+bk^{tn}\frac{k^{tu}-1}{k^t-1}$$

soit divisible par $p_n$, ce qui est absurde car alors $p_n$ divise aussi $p_{n+u}$. Pour $n$ assez grand, $k^t$ et $k^t-1$ sont premiers avec $p_n$: il suffit de rendre $p_n$ plus grand que le plus grand des diviseurs premiers de ces deux nombres. D'après le petit théorème de Fermat(^0.18), $p_n$ divise $k^{t(p_n-1)}-1$ et, comme il est premier avec $k^t-1$, il divise aussi

$$\frac{k^{t(p_n-1)}-1}{k^t-1}\cdot$$

Le nombre $u=p_n-1$ convient donc.$\qed$