Des critères de divisibilité semblent pouvoir être élaborés à l’envi. Contentons-nous de ceux qui ont été rencontrés au cours de pages précédentes, et essayons de voir comment les mobiliser sur quelques petits problèmes arithmétiques.
La suite de Fibonacci revisitée
À tout seigneur, tout honneur : commençons par la suite de Fibonacci, débutant par 0 puis 1, dans laquelle chaque terme est la somme des deux qui le précèdent. La suite se construit donc élément après élément : 0, 1, 1 (= 1 + 0), 2 (= 1 + 1), 3 (= 1 + 2), 5 (= 2 + 3), 8 (= 3 + 5), 13 (= 5 + 8)…
Partons du premier terme, multiplions-le par 10 et ajoutons le deuxième. Multiplions le résultat obtenu par 10 et ajoutons le troisième. Poursuivons ainsi. On obtient successivement 1, 11, 112, 1 123, 11 235, 112 358, 1 123 593… En continuant, des grands nombres apparaissent, dont l’écriture est périodique (des blocs de chiffres se répètent à la suite les uns des autres). N’hésitez pas à poursuivre le procédé pour vous en convaincre. Combien de chiffres une période compte-t-elle, au minimum ?
Désignons par (Ni)i ≥0 les termes successifs de la suite de Fibonacci. On a N0 = 0, N1 = 1, N2 = 1, et Ni+2 = Ni+1 + Nilorsque i ≥ 0. Or, 89 (10–2 × N1 + 10–3 × N2 + 10–4 × N3) est égal à 100 (10–2 N1 + 10–3 N2 + 10–4 N3 +…) – 10 (10–2 N1 + 10–3 N2 + 10–4 N3 + …)
– (10–2 N1 + 10–3 N2 + 10–4 N3 + …),
soit encore à N1 + (N2 – N1)10–1 + (N3 – N2 – N1)10–4 + …
Cette dernière quantité vaut simplement 1 + 0 + 0 + …, c’est-à-dire 1. Autrement dit, l’écriture des grands nombres obtenus commence par les parties entières des produits des grandes puissances de 10 par 1 / 89 = 0,0112359550… Le problème posé revient donc à chercher le plus petit entier p tel que (10p – 1) soit divisible par 89.
Écrivons (1 × 2 × 3 × … × 88) × 1 = 1 × 2 × 3 × … × 88. L’entier 89 étant premier, cette quantité est congrue, modulo 89, à (1 × 10) × (2 × 10) × (3 × 10) × … × (88 × 10), qui vaut (1 × 2 × 3 × … × 88) × 1088 modulo 89.
Donc 1088 – 1 est divisible par 89 et p divise 88, qui s’écrit 23 × 11. Toujours modulo 89, 101 = 10, 102 = 100 ≡ 11, 104 ≡ 112 ≡ 32, 108 ≡ 322 ≡ 45, 1011 = 108 × 102 × 101 ≡ 4 950 ≡ 55, 1022 ≡ 552 ≡ – 1, 1044 ≡ (–1)2 = 1. Donc 1044 – 1 est divisible par 89. Comme on a, dans le processus, testé au passage les cinq diviseurs propres de 44 (à savoir 1, 2, 4, 11 et 22), le plus petit p est 44. Un période compte donc au moins quarante-quatre chiffres.
En remarquant que 26 = 13 × 2
L’entier de quatre chiffres 9 876 est tel que 9 est divisible par 1, 98 par 2, 987 par 3 et 9 876 par 4. De même, 1 020 est tel que 1 est divisible par 1, 10 par 2, 102 par 3 et 1 020 par 4. Vous vérifierez de même que l’entier de vingt-cinq chiffres
N = 3 608 528 850 368 400 786 036 725
est tel que les nombres constitués successivement par ses j premiers chiffres, où j varie de 1 à 25, sont divisibles par j. On admettra ici que c’est le seul entier ainsi constitué.
Est-il possible de satisfaire cette propriété au-delà de 25 ? La réponse est négative. En effet, il est impossible d’écrire un nouveau chiffre X à droite de N afin d’obtenir un entier 1026 X + N divisible par 26. Pour s’en convaincre, reprenons ce critère de divisibilité par 13 : on considère les tranches de trois chiffres à partir de la droite, on les additionne et on les soustrait alternativement ; si le résultat est divisible par 13, c’est que le nombre de départ l’est aussi. On obtiendrait ici
36 – 85 + 288 – 503 + 684 – 7 + 860 – 367 + 25X, soit 906 + 25X, qui s’écrit 13 × 88 + 12 + X. Pour que ce nombre soit divisible par 13, il faudrait que X = 1, alors que X devrait également être pair.
Des puissances très proches
Le scientifique et philosophe Levi Ben Gerson (1288–1344) a cherché tous les couples d’entiers naturels consécutifs constitués d’une puissance de 2 et d’une puissance de 3. Suivons son raisonnement.
Si l’on considère la relation 2q – 1 = 3r avec q ≥ 1, trois cas se présentent. Si q = 1, alors r = 0 et l’on obtient le couple (1, 2). Si q = 2, alors r = 1, ce qui conduit à la solution (3, 4). Si q ≥ 3, alors 3r + 1 = 2q est divisible par 8, d’où une contradiction car 32 ≡ 1 modulo 8, donc 3r + 1 ≡ 2 modulo 8 si r est pair et 3r + 1 ≡ 4 modulo 8 si r est impair. On n’obtient donc aucune nouvelle solution.
Si maintenant l’on considère la relation 2q + 1 = 3r avec q ≥ 1, deux cas sont à regarder. Si q = 1, alors r = 1 et l’on obtient (2, 3). Si q ≥ 2, alors 3r–1 + … + 1 = (3r – 1) / (3 – 1) = 2q–1 est un entier pair, donc r lui-même est pair. Posons r = 2r ’. On a
2q = 32r ’ – 1 = (3r ’ + 1)(3r ’ – 1).
Ces facteurs sont deux puissances de 2 dont la différence est 2.
Donc (3r ’+ 1) = 4 et (3r ’– 1) = 2.
On en déduit r ’ = 1, soit r = 2, puis q = 3. On obtient la dernière solution du problème, le couple (8, 9).
Factorisons la factorielle
La factorielle n! d’un entier n est le produit des entiers non nuls qui lui sont inférieurs (voir notre dossier dans Tangente 131, 2009), et l’on définit 0! = 1. Essayons alors de résoudre l’équation a! + b! = c!. On peut supposer a ≤ b < c.
Si a = b, après division par a!, on obtient 2 = (a + 1) × … × c, qui est divisible par (a + 1). Donc a = b = 0 et c = 2, ou a = b = 1 et c = 2.
Si a < b, après division par a!, on trouve :
1 + (a + 1) × … × b = (a + 1) × … × b × (b + 1) × … × c = ((a + 1) × … × b) × ((b + 1) × … × c).
Cela conduit à :
1 = ((a + 1) × … × b) × ((b + 1) × … × c – 1).
Le membre à droite étant au moins égal à a + 1, on obtient a = 0, puis b = 1 et c = 2. Toutes les solutions du problème correspondent à 0! + 0! = 2!, 1! + 1! = 2! ou 0! + 1! = 1!.
Hommage au PGCD
Le plus grand commun diviseur (ou PGCD) d’un ensemble de nombres est le plus grand entier qui divise chacun des nombres. Si le PGCD est égal à 1, les nombres de départ sont dits premiers entre eux. Quel est le PGCD des nombres v17 – v, où v parcourt l’ensemble des entiers naturels supérieurs à 1 ?
Observons déjà que :
217 – 2 = 2 × (216 – 1) = 2 × (28 – 1) × (28 + 1) = 2 × (24 – 1) × (24 + 1) × (28 + 1)
= 2 × (22 – 1) × (22 + 1) × (24 + 1) × (28 + 1) = 2 × 3 × 5 × 17 × 257.
Le PGCD demandé ne doit donc contenir que ces nombres premiers.
Observons également que v17 – v = v (v – 1)(v + 1)(v2 + 1)(v4 + 1)(v8 + 1). Le produit des deux premiers termes est forcément divisible par 2, et celui des trois premiers termes par 3.
Maintenant, d’après le petit théorème de Fermat, soit 5 divise v, soit 5 divise v4 – 1. Donc 5 divise le produit des cinq premiers termes.
De même, 17 divise le produit des six premiers termes.
Il reste à traiter le facteur 257. On a 35 = 243 ≡ –14 modulo 257, donc (35)3 ≡ 83 modulo 257. On écrit 317 – 3 = 9 × (35)3 – 3 ≡ 747 – 3 ≡ 230 modulo 257, qui est donc non nul modulo 257. Le PGCD demandé est alors 2 × 3 × 5 × 17, soit 510.
On vous le disait : les récréations mathématiques reposant sur la divisibilité sont innombrables !
Lire la suite