Repunits

Les repunits sont des nombres formés uniquement de chiffres 1 : 11, 111, 1111, etc.

Nous nous intéressons ici à ceux qui sont multiples d'un nomnbre donné

Le plus petit repunit multiple de 3 est ainsi 111 (évident)
Mais quel est le plus petit repunit multiple de 13 ?

Un repunit est en fait (10n - 1)/9
On a donc 9×13k = 10n - 1 et la congruence 10n ≡ 1 mod 13
D'après le théorème d'Euler-Fermat, si a et b sont premiers entre eux, aφ(b) ≡ 1 mod b
avec φ(b) la fonction d'Euler de b, nombre de nombres premiers avec b et < b.
Soit ici puisque b est premier, &phi(b) = b - 1 = 12, et la congruence 1012 &equiv 1 mod 13
Mais 12 n'est pas forcément le plus petit n avec 10n ≡ 1 mod 13 ! en fait n est un diviseur de φ(13) = 12
On est ainsi amené à tester n = 2, 3, 4, 6 et 12 soit :
100 ≡ 9 mod 13
1000 ≡ 12 ≡ -1 mod 13
10000 ≡ 3 mod 13
1000000 = 1000² ≡ (-1)² ≡ 1 mod 13
et 1000000000000 ≡ 1 mod 13 bien entendu, puisque c'est 1000000²
Le plus petit n avec 10n ≡ 1 mod 13 est donc 6, ce qui donne en divisant 106 - 1 par 9 :
111111 dont on vérifie immédiatement que c'est 13×8547

Cette méthode marche et est assez simple, mais donnons en une autre.
Si on calcule 1/13 = 0.076923076923076923076923076923... on obtient une partie fractionnaire périodique, la période étant 076923,
ce que l'on écrit 1/13 = 0.076923
Et bien entendu 076923×13 = 999999 (c'est lié à 0.999999 = 0.9 = 1)
En divisant par 9, on obtient directement (76923/9)×13 = 111111

On a ainsi mis en évidence un théorème important :

la longueur de la période de 1/b est un diviseur de φ(b)

Lorsque b est un nombre premier, φ(b) = b - 1
Si la longueur de la période est précisément égale à φ(b), le nombre premier est dit "nombre premier long" (ici en base 10)
Les nombres premiers longs sont en base 10 A001913 du OEIS :
7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, ...

En particulier 23 est un nombre premier long, et la période de 1/23 est 22 et le plus petit repunit multiple de 23 est ainsi formé de 22 chiffres 1.
Sans cette table, il faudrait essayer les diviseurs de 22, ce qui ici n'est pas trop long puisque c'est 1, 2, 11 et 22.
On ne calcule pas bien sûr explicitement 1011 et 1022 mod 23, mais on opère de proche en proche par élévations au carré successives et des multiplications par 10 :
102 = 100 ≡ 8 mod 23
103 ≡ 8×10 ≡ 11 mod 23
104 ≡ 8² ≡ 18 mod 23
108 ≡ 18² ≡ 2 mod 23
Et enfin 1011 = 108×103 ≡ 2×11 ≡ 22 ≡ -1 mod 23
Puis 1022 = (1011)2 ≡ (-1)² &equiv 1 mod 23

Le calcul effectif de 1/23 est ici bien plus fastidieux, certes la calculette donne 1/23 = 0,043478260869565217391304347826087 et on peut deviner que c'est 0.0434782608695652173913 mais la deuxième période n'étant pas complète, cela tient de la boule de cristal ...

Lorque b n'est pas premier cela va encore avec la même méthode (mais il faut calculer φ(b), ou 1/b et 'voir' la période)
Le problème se complique si b n'est pas premier avec 9, c'est à dire si b est un multiple de 3.
Prenons comme exemple 123
La calculette donne directement 1/123 = 0.00813 (on calcule φ(123) = 80 et la période 5 est bien un diviseur de 80)
Certes 813×123 = 99999, mais on ne peut pas diviser aussi simplement par 9 car 813 n'est pas un multiple de 9 !
On est ainsi amené à prendre trois périodes complètes et à écrire 8130081300813×123 = 999999999999999
que l'on peut alors diviser par 9 pour obtenir (8130081300813/9)×123 = 111111111111111 soit 903342366757×123 = 111111111111111

Au pire (si b est multiple de 9) on est amené à prendre au maximum 9 périodes de 1/b.

Ainsi b = 153 donne 1/b = 0.0065359477124183
et comme 65359477124183 ≡ 2 mod 3 il faut prendre les 9 périodes pour obtenir un repunit de 144 chiffres !
La vérification est impossible à la simple calculette (sans acrobaties)

 

Accueil Arithmétiques Géométrique Divers Thèmes Scripts Jeux Exercices Sujet suivant Parent