Des 0 et des 1

Je suis tombé récemment sur un énoncé qui a égayé ma curiosité. Avant de le donner, voici quelques constatations:

  • 3 divise le nombre 10101 (dix mille cent un)
  • 7 divise le nombre 10101 aussi
  • 9 divise 10101010101010101
  • 11 divise 101010101010101010101
  • 13 divise 10101

(Pour vérifier ces affirmations, vous pouvez vous rendre sur ce site. Sinon, faites-moi confiance. Ou pas.)

Nous allons donc nous intéresser aux nombres de la forme 10101…..0101. Ce sont les nombres dont l’écriture décimale est une succession de 0 et de 1, commençant et finissant par 1.

Voici l’énoncé de l’exercice:

Tout entier naturel dont l’écriture décimale se termine par le chiffre 1, 3, 7 ou 9 divise un nombre du type 1010101….101.

Dans un premier temps, nous allons résoudre cet exercice, puis, étant donné un entier n vérifiant les conditions de l’énoncé, nous donnerons une construction explicite de 10101….101 (c’est-à-dire que nous donnerons une longueur explicite de ce nombre, qui dépendra de l’entier n bien sûr). Mais avant cela, je vous laisse plancher sur cet exercice pendant quelques heures, histoire de bien vous imprégner du sujet. Prenez un papier et un crayon, et ne revenez que quand vous séchez vraiment. Je vous surveille !

Saute-mouton

Commençons par comprendre l’énoncé. Voire le retraduire.

  • L’écriture décimale 101 signifie 10^2 + 10^0. De même, 10101 = 10^4 + 10^2 +10^0. J’ai honte d’écrire la suite, mais je le fais par pure conscience professionnelle: 1010101 = 10^6 + 10^4 + 10^2 + 10^0. Toutes les puissances de 10 impaires ont donc été sautées. Pour simplifier les notations (et pour pouvoir généraliser plus tard), je vais poser a=10^2. Ainsi, 101 = a^1 + a^0, 10101 = a^2+a^1+a^0 et 1010101 = a^3 + a^2 + a^1+a^0. Un nombre du type 1010101….101 est donc un nombre qui peut s’écrire sous la forme \sum_{k=0}^{p}a^k pour un certain entier naturel p.
  • Continuons et voyons ce que signifie un nombre dont le dernier chiffre est un 1, un 3, un 7 ou un 9. C’est un nombre dont le dernier chiffre n’est pas 0, 2, 4, 6, 8 (je viens de réinventer l’eau tiède là) c’est-à-dire un nombre impair. C’est aussi un nombre dont le dernier chiffre n’est pas 5, donc c’est un nombre qui n’est pas divisible par 5.

Soit donc n un entier naturel qui n’est divisible ni par 2, ni par 5. Nous allons raisonner modulo n et montrer qu’il existe nécessairement un entier p tel que la somme \sum_{k=0}^{p}a^k est congrue à 0 modulo n. Le principe de la solution est de dire que, tout comme lorsqu’on fait une division décimale, il y aura des blocs qui vont se répéter périodiquement modulo n. Il suffira de choisir p de telle sorte qu’on ait n blocs similaires (modulo n), et ainsi le nombre 101010….101 sera bien divisible par n. Mais écrivons cela plus proprement.

La suite de nombres a^k modulo n a une infinité de termes (k se balade dans \mathbb{N}). Or, il y a un nombre fini de valeurs possibles pour cette suite à savoir les restes dans la division par n (donc les nombres de 0 à n-1). D’après le principe des tiroirs (principe tellement beau et simple qu’il fera sans doute l’objet d’un article un jour sur ce blog….), il existe alors deux entiers r> s tels que a^r \equiv a^s [n] ce qui donne a^{s}(a^{r-s}-1) \equiv 0 [n]. Mais, puisque l’entier n n’est divisible ni par 2, ni par 5, il est donc premier avec a=10^2. D’après le théorème de Gauss, on peut « simplifier » par a, ce qui donne a^{r-s}-1 \equiv 0 [n]. De manière plus simple, on vient de prouver qu’il existe un entier naturel non nul q tels que a^q \equiv 1 [n].

Cela veut dire que le bloc 1 + a ^1 + a^2 + \cdots + a^{q-1} sera égal au bloc a^{q} + a^{q+1}+\cdots+a^{2q-1} modulo n. Si on prend n de ces blocs consécutivement, la somme sera ainsi divisible par n. Formalisons tout cela.

Posons p=nq-1 (donc pour n blocs). On a

\sum_{k=0}^{p}a^k = \sum_{k=0}^{nq-1}a^k=\sum_{t=0}^{n-1} \sum_{m=0}^{q-1} a^{tq+m }

On a partitionné la somme en blocs. Or, a^{tq+m} =(a^q)^t a^m \equiv 1. a^m [n]. Donc:

\sum_{k=0}^p a^k \equiv \sum_{t=0}^{n-1} \sum_{m=0}^{q-1} a^m [n]

Donc, puisque ce qu’on somme ne dépend pas de t, on peut factoriser:

\sum_{k=0}^p a^k \equiv (\sum_{m=0}^{q-1} a^m )(\sum_{t=0}^{n-1} 1) [n]

c’est-à-dire \sum_{k=0}^p a^k \equiv (\sum_{m=0}^{q-1} a^m ) \times n \equiv 0 [n]

CQFD.

Et en pratique ?

En analysant la preuve précédente, le nombre de chiffres du nombre du type 1010101…101 qui est divisible par n est 2(nq-1)+1 où q était un entier tel que a^{q} \equiv 1 [n]. En effet, la plus grande puissance de a apparaissant dans la somme est a^{nq-1}, c’est-à-dire 10^{2(nq-1)}. Donc, si on peut trouver un tel entier naturel non nul q, on pourra en déduire un nombre 10101….101 explicitement.

Ce nombre q n’est pas unique. En fait, en langage de la théorie des groupes, on dirait que a est d’ordre fini dans le groupe (\mathbb{Z} / n \mathbb{Z})^* (logique puisque ce groupe est fini) et q est un multiple de son ordre. L’ordre étant le plus petit entier r vérifiant a^r \equiv 1 [n]. En pratique, étant donné n, on pourrait regarder les puissances successives de a modulo n pour trouver q. Mais cela peut faire beaucoup de calculs. En fait, nous n’avons pas besoin de connaître l’ordre de a pour trouver explicitement un q qui convienne. Car d’après un théorème dû à Euler (un autre oui…),  on sait que a^{\varphi(n)} \equiv 1 [n]\varphi est la fonction indicatrice d’Euler.

Nous avons donc prouvé que si n est un entier naturel qui se termine par un 1, un 3, un 7 ou un 9, il divise le nombre 101010101…101 où figurent 2(n\varphi(n)-1)+1=2n\varphi(n)-1 chiffres (dont n\varphi(n)-1 chiffres 0 et n\varphi(n) chiffres 1).

Retour aux exemples…

Prenons le cas n=3. On sait que \varphi(3)=2 donc 2n\varphi(n)-1 = 11. Le nombre 3 divise donc le nombre 10101010101  (ce qu’on vérifie facilement avec le critère de divisibilité par 3 car la somme des chiffres est bien divisible par 3). Dans l’exemple initial, nous avions dit que 3 divise 10101. Cela vient du fait que a^1=(10^2)^1 =100 \equiv 0 [3]. Le théorème d’Euler, lui, nous dit seulement que a^2=(10^2)^2 \equiv 0 [3], ce qui a donc allongé le nombre de 0 et de 1.

Prenons le cas n=7. Nous avions vu qu’il divise 10101 mais d’après notre méthode, n divise aussi un nombre du type 10101…101 à 2\times 7 \times\varphi(7)-1= 2 \times 7 \times 6 -1 = 83 chiffres !

Plus généralement, si n est un nombre premier, alors \varphi(n)=n-1 et donc n divise un nombre du type 10101…101 à 2 n (n-1) -1 chiffres. Pour n= 37, cela fait un nombre à 2x37x36-1 = 2663 chiffres. Tout de même.

Une généralisation

Nous n’avions utilisé aucune propriété du nombre a autre que le fait qu’il est premier avec n. On aurait donc pu aussi prendre a=10^3, a=10^4, etc. Nous pouvons donc affirmer que tout nombre n se terminant par 1, 3, 7 ou 9 divise un nombre de la forme 1001001001001….1001, ainsi qu’un nombre de la forme 1000100010001……10001, ainsi qu’un nombre de la forme 1000010000100001….100001. En fait, on peut mettre autant de zéros que l’on souhaite entre deux 1, et affirmer que n divisera un nombre de cette forme.

Publicités
Cet article, publié dans Arithmétique, est tagué , , , , , , . Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s