Quels sont les derniers chiffres du nombre de Graham ? 2ème partie : les 5 derniers chiffres

Publié le 25 avril 2021 par blogdemaths

Dans la première partie de cette trilogie d’articles sur les derniers chiffres du nombre de Graham, nous avions dit, et même prouvé, que le dernier chiffre de Graham est 7. Je vous conseille de lire cette première partie avant de lire la suite :

Quels sont les derniers chiffres du nombre de Graham ? 1ère partie : le dernier chiffre

Savoir que ce nombre se termine par un 7 est très bien mais pourquoi s’arrêter en si bon chemin ? Pourquoi ne pas déterminer les deux derniers chiffres du nombre de Graham ? Et les trois derniers ? Je vous annonce tout de suite la couleur : on va en fait voir une méthode permettant théoriquement de déterminer autant des derniers chiffres du nombre de Graham que l’on souhaite.

Le théorème d’Euler

Pour déterminer le dernier chiffre d’un nombre, nous avions dit qu’il suffisait de trouver le reste de ce nombre modulo 10. De la même façon, si vous souhaitez les deux derniers chiffres, il suffit d’étudier ce nombre modulo 100 et, plus généralement, si vous voulez les d derniers chiffres, il suffit de regarder ce nombre modulo 10^d.

Pour calculer le reste modulo 10^d du nombre du Graham (ou de tout autre nombre d’ailleurs), on peut utiliser un théorème fort utile qu’on appelle le théorème d’Euler. Celui-ci dit que si a est un nombre premier avec n alors

a^{\varphi(n)} \equiv 1 \mod[n]

Ici, \varphi est ce qu’on appelle la fonction indicatrice d’Euler, c’est-à-dire que \varphi(n) est le nombre de nombres inférieurs ou égaux à n qui sont premiers avec n. Par exemple, les seuls nombres compris entre 1 et 10 qui sont premiers avec 10 sont 1, 3, 7 et 9. Puisqu’il y en a quatre, alors \varphi(10)=4.

Revenons au théorème d’Euler et donnons-en une illustration : comme 3 est premier avec 10, on a donc 3^{\varphi(10)} \equiv 1 \mod[10]. Ainsi,

3^{4} \equiv 1 \mod[10]

Le théorème d’Euler va permettre de calculer des nombres de la forme a^m modulo n à partir de la division euclidienne de m par \varphi(n) : en effet, si m = q \times \varphi(n) + r alors

a^{m} = a^{ q \times \varphi(n) + r} = \left(a^{\varphi(n)} \right)^q \times a^r \equiv 1^q \times a^r = a^r \mod[n]

Ce qu’il faut retenir de tout cela c’est que

\boxed{a^m \equiv a^{m \mod [\varphi(n)]} \mod[n]}

où m \mod[\varphi(n)] est le reste de la division de m par \varphi(n).

Pour bien comprendre , prenons un exemple : si vous souhaitez déterminer 3^{27} modulo 10 alors, puisque \varphi(10) = 4, et que le reste de la division euclidienne de 27 par 4 est 3 (autrement dit, 27 \mod[4] = 3), on a donc

3^{27} \equiv 3^{27 \mod[4]} = 3^{3} = 27 \equiv 7 \mod[10]

Le théorème d’Euler répété

On peut répéter l’utilisation du théorème d’Euler lorsqu’on souhaite étudier une tour de puissances. Par exemple, pour déterminer a^{b^{c}} \mod[n], on calculera :

a^{(b \mod \varphi(n))^{c \mod[\varphi(\varphi(n}))]} \mod [n]

Exemple pratique : pour calculer 3^{3^3} modulo 10, on écrit

3^{3^3} \equiv 3^{(3 \mod \varphi(10))^{3 \mod[\varphi(\varphi(10}))]} \mod [10]

Comme \varphi(10)=4 alors \varphi(\varphi(10)) = \varphi(4) = 2 (il n’y a que deux nombres inférieurs ou égaux à 4 qui sont premiers avec 4, à savoir 1 et 3). Par conséquent,

3^{3^3} \equiv 3^{(3 \mod[4])^{3 \mod[2]}} = 3^{3^{1}} = 3^3 = 27 \equiv 7 \mod [10]

Ainsi, pour calculer a^{a^{a^{\dots}}} modulo n, il suffit de connaître la suite de nombres \varphi(n), \varphi(\varphi(n)), \varphi(\varphi(\varphi(n))), …

Les derniers chiffres du nombre de Graham

Commençons par essayer d’obtenir les deux derniers chiffres du nombre de Graham. Dans ce cas, il suffit calculer ce nombre modulo 100 et, pour utiliser le théorème d’Euler répété, il faut d’abord calculer \varphi(100), \varphi(\varphi(100)), \varphi(\varphi(\varphi(100))), etc. Le calcul de ces valeurs donne

\begin{array}{ccc} \varphi(100) & = & 40 \\ \varphi(40) & = & 16 \\ \varphi(16) & = & 8 \\ \varphi(8) & = & 4 \\ \varphi(4) & = & 2 \\ \varphi(2) & = & 1 \\ \varphi(1) & = & 1 \\ \varphi(1) & = & 1 \\ \end{array}

etc.

On calcule ensuite 3^{(3 \mod[40])^{(3 \mod[16])^{\cdots}} } \mod[100]. Mais comme 3 \mod 1 vaut 0,  on se rend compte qu’il n’y aura en fait qu’un petit nombre de calculs à faire. Nous allons effectuer alors les calculs en partant de la fin. Puisque la suite inversée des itérées de \varphi est 1, 2, 4, 8, 16, 40, 100, on calcule les nombres suivants :

3\mod [1] = 0

(3  \mod [2])^0 = 1^0 = 1

(3 \mod [4])^1 = 3^1 = 3

(3  \mod [8])^3 = (3^3 \mod [8]) = 27 \mod [8] = 3

(3\mod [16])^3 = 3^3 = 27

(3 \mod [40])^{27} = 3^{27} \mod[40] = 7625597484987 \mod [40] = 27

(3 \mod [100])^{27} = 3^{27} \mod [100] = 87

Cela montre donc que les deux derniers chiffres du nombre de Graham sont 87.

Remarque : dans ces calculs, vous aurez noté qu’on a parfois utilisé la propriété disant que (a \mod [b])^c = a^c \mod [b] (où l’égalité est à considérer modulo b).

Un programme informatique

On peut programmer cette méthode pour obtenir autant de chiffres du nombre de Graham que l’on souhaite. Voici un exemple de programme possible :

Programme de calcul des derniers chiffres du nombre de Graham

Par exemple, on trouve avec ce programme que les cinq derniers chiffres sont :

...95387

Théoriquement, on pourrait donc obtenir autant de chiffres du nombre de Graham que l’on souhaite, ce qui est tout simplement incroyable quand on y pense. Le seul problème est qu’en pratique le calcul des \varphi(n) peut être assez long et ce programme met beaucoup de temps à trouver ne serait-ce que les dix derniers chiffres du nombre de Graham… (essayez par vous-même !) Heureusement, il y a une autre méthode pour calculer ces chiffres et c’est ce que nous verrons dans la troisième partie !

Lien vers la troisième partie : (à venir bientôt !)

A voir :

Publié dans Nombres | Tagué , , , , , | 2 commentaires

Quels sont les derniers chiffres du nombre de Graham ? 1ère partie : le dernier chiffre

Publié le 7 mars 2021 par blogdemaths

Il y a quelques mois de cela, j’ai fait une vidéo traitant du nombre de Graham, ce fameux nombre gigantesque qui détint pendant plusieurs années le titre de « plus grand nombre utilisé dans une démonstration mathématique » :

Ce nombre a beau être gigantesque, on connaît pourtant son dernier chiffre et même ses derniers chiffres. Quels sont donc ces chiffres et comment les calculer ? C’est ce que je vous propose de voir dans une série de trois articles. Dans ce premier article, nous allons commencer modestement puisque nous ne nous occuperons que de calculer le dernier chiffre du nombre de Graham.

Le nombre de Graham et la notation de Knuth

Comme expliqué dans la vidéo, la notation fléchée de Knuth permet de définir des grands nombres de la façon suivante : tout d’abord, a \uparrow b = a^b puis

a \uparrow \uparrow b = a \uparrow a \uparrow \dots \uparrow a = a^{a^{a^{\cdots ^{a}}}}

avec b exemplaires du nombre a. Plus généralement, on définit

$latex \begin{matrix}
a\ \underbrace{\uparrow_{}\uparrow\!\!\dots\!\!\uparrow}\ b=
a\ \underbrace{\uparrow\!\!\dots\!\!\uparrow}
\ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}
\ a\ \dots
\ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}
\ a
\\
\quad\ \ \,n\qquad\ \ \ \underbrace{\quad n_{}\!-\!\!1\quad\ \,n\!-\!\!1\qquad\quad\ \ \ \,n\!-\!\!1\ \ \ }
\\
\qquad\qquad\quad\ \ b\mbox{ exemplaires de }a
\end{matrix}$

ce qui fait que, par récurrence, on peut toujours écrire :

a \underbrace{\uparrow \uparrow \dots \uparrow}_{n} b = a \uparrow a \uparrow a \uparrow \dots \uparrow a = a^{a^{a^{\dots ^{a}}}} = a \uparrow \uparrow k

pour un certain entier k.

Le nombre de Graham, défini à l’aide de la notation de Knuth.

Tout cela pour dire que, si vous avez bien suivi la vidéo, vous avez compris que le nombre de Graham, que nous noterons G, s’écrit en fait :

G = 3 \uparrow \uparrow \uparrow \cdots \uparrow  \uparrow  3

avec un très grand nombre de flèches et que, d’après ce qu’on vient de dire, on peut donc écrire G comme G = 3 \uparrow\uparrow k où k est un très grand nombre. Au passage, cela veut dire que le nombre de Graham n’est en fait finalement rien d’autre qu’une tour de 3 :

G = 3^{3^{3^{3^{\cdots}}}}

Des calculs modulo 10

Pour calculer le dernier chiffre d’un nombre, il suffit de calculer le reste de ce nombre dans la division par 10. Autrement dit, cela revient à raisonner modulo 10.

Avant de pouvoir trouver le dernier chiffre du nombre de Graham, commençons par calculer le reste modulo 10 des nombres 3\uparrow \uparrow k = 3^{3^{3^{3^{\cdots}}}} pour quelques valeurs de k.

• 3 \uparrow\uparrow 1 = 3 donc 3 \uparrow\uparrow 1 \equiv 3 \mod[10].

• 3 \uparrow\uparrow 2 = 3^3 = 27 donc 3 \uparrow\uparrow 2 \equiv 7 \mod[10].

• 3\uparrow\uparrow 3 = 3^{3^{3}} = 3^{27}. Le nombre 3^{27} est très grand et pour calculer son reste modulo 10, on peut utiliser le fait suivant : 3^{4} \equiv 1 \mod[10]. Ainsi,

3^{27} = 3^{4 \times 6 + 3} = \left(3^4\right)^6 \times 3^3 \equiv 1^6 \times 3^3 = 27 \equiv 7 \mod[10]

donc 3\uparrow\uparrow 3 \equiv 7 \mod[10].

• 3\uparrow \uparrow 4= 3^{3^{3^{3}}}. On pourrait faire comme précédemment et essayer d’écrire la division euclidienne de l’exposant 3^{3^{3}} par 4 pour pouvoir utiliser le fait que 3^4 \equiv 1 \mod[10] mais ce nombre est un peu trop grand pour cela. Cependant, si on regarde les puissances de 3 modulo 4, on se rend compte de quelque chose :

3^1  =3\equiv 3 \mod[4]

3^2 = 9 \equiv 1 \mod[4]

3^3 = 27 \equiv 3 \mod[4]

3^4 = 81 \equiv 1 \mod[4]

3^5 = 243 \equiv 3 \mod[4]

Plus généralement,

3^{2p} = \left(3^2\right)^p = 9^p \equiv 1^p = 1 \mod[4]

3^{2p+1} = \left(3^2\right)^p \times 3^1 = 9^p \times 3 \equiv 1^p \times 3 = 3 \mod[4]

On voit donc que si n est un nombre pair alors 3^{n} \equiv 1 \mod[4] et si n est un nombre impair alors 3^{n} \equiv 3 \mod[4].

Comme le nombre 3^{3^{^{3}}} est un nombre impair (ce n’est rien d’autre qu’une puissance de 3 c’est-à-dire 3 \times 3 \times \cdots \times 3) alors 3^{3^{^{3}}} \equiv 3 \mod[4] c’est-à-dire qu’il est de la forme 3^{3^{^{3}}} = 4p +3. Ainsi,

3^{3^{3^{3}}}= 3^{4p+3} = \left({3^4}\right)^p \times 3^3 \equiv 1^p \times 27 = 27 \equiv 7 \mod[10]

Cela prouve que 3\uparrow \uparrow 4= 3^{3^{3^{3}}} \equiv 7 \mod[10].

Et le dernier chiffre du nombre de Graham est …

Plus généralement,  3^{3^{3^{^{3^{\dots^3}}}}} est un nombre impair donc il est de la forme 4p+3. Si on prend 3 puissance ce nombre, on aura :

3^{3^{3^{3^{^{3^{\dots^3}}}}}}= 3^{4p+3} = \left({3^4}\right)^p \times 3^3 \equiv 1^p \times 27 = 27 \equiv 7 \mod[10]

Cela montre qu’on trouvera toujours 7 comme dernier chiffre des nombres 3 \uparrow \uparrow k dès que k \geqslant 2. Comme le nombre de Graham est justement un nombre de la forme 3 \uparrow \uparrow k, vous avez donc la réponse : il se termine par le chiffre 7.

Je répète : on sait donc que ce gigantesque nombre que personne ne pourra jamais calculer complètement se termine par un 7. Il y a des milliers de façons de s’émerveiller devant les mathématiques et nous venons d’en voir une de plus.

Pour lire la deuxième partie de cet article :

Les derniers chiffres du nombre de Graham : 2ème partie : les cinq derniers chiffres

Publié dans Arithmétique | Tagué , , , , , , , , , | 7 commentaires

La spirale d’Ulam

Publié le 25 Mai 2020 par blogdemaths

La spirale d’Ulam est une de ces curiosités qui font sentir la beauté des mathématiques. C’est le thème que j’ai traité dans la dernière vidéo postée sur ma chaîne Youtube et que je vous invite à regarder :

Dans cet article, nous allons préciser certaines choses sur les polynômes du second degré dont il est fait mention dans cette vidéo.

« Oh, la belle bleue ! »

Une spirale à prendre au second degré

Vous l’aurez donc compris, l’existence de nombres premiers sur des diagonales est intimement liée à l’existence de polynômes du second degré P à coefficients entiers dont les images des entiers naturels P(n) sont souvent des nombres premiers.

Même si cela est illustré sur un exemple dans la vidéo, il serait tout de même bon de préciser pourquoi chaque diagonale peut être représentée à l’aide d’un de ces polynômes du 2nd degré car cela peut sembler sortir de nulle part.

Remarquons que, lorsqu’on écrit les entiers naturels non nuls en spirale, nous pouvons constater que cette spirale est constituée de plusieurs carrés concentriques :

Cette spirale peut donc être découpée en plusieurs « anneaux ». Le premier anneau contient uniquement le nombre 1 et possède donc un seul élément.

Le second anneau, qui contient les nombres 2, 3, 4, 5, 6, 7, 8 et 9, possède 8 éléments. Une façon de calculer cela serait de dire qu’on fait la différence entre le nombre d’éléments dans le carré intérieur qui est de côté 1 (1² éléments) et le nombre d’éléments dans le carré extérieur qui est de côté 3 (3² éléments) c’est-à-dire 3²-1² = 8 éléments.

De cette façon, on voit donc que le nombre d’éléments du troisième anneau (celui qui contient les nombres de 10 à 25) s’obtient en faisant la différence du nombre d’éléments d’un carré de côté 5 (ce qui donne 5² éléments) et du nombre d’éléments d’un carré de côté 3 (ce qui donne 3²). Le troisième anneau possède donc 5² – 3² = 16 éléments.

De même, le 4ème anneau possédera 7² – 5 ² = 24 éléments et, plus généralement, si n>1, le n-ème anneau contiendra (2n-1)² – (2(n-1)-1)² = 8(n-1) éléments.

Autrement dit, et c’est ce qu’il faut retenir ici, chaque anneau possède 8 éléments de plus que l’anneau précédent (hormis pour les 1er et 2ème anneau, mais il fallait bien qu’il y ait un cas casse-pieds…).

Le seigneur des anneaux

A présent, nous sommes en mesure de comprendre pourquoi les diagonales sont représentées par des polynômes du second degré. On considère des nombres a_1, a_2, a_3, \dots , a_n, a_{n+1}, a_{n+2}, \dots de cette spirale situés sur une même ligne diagonale.

Si on part du nombre a_n pour aller, en suivant la spirale, au nombre a_{n+1}, on parcourra a_{n+1} - a_n nombres.

De même, en partant de a_{n+1} pour aller à a_{n+2}, on parcourra a_{n+2} - a_{n+1} nombres mais on peut aussi dire qu’on parcourra 8 nombres de plus que pour aller de a_n à a_{n+1} puisque nous avons vu que chaque anneau possède 8 nombres de plus que l’anneau précédent. On a donc la relation

a_{n+2} - a_{n+1} = a_{n+1} - a_n + 8

Si on note u_n le nombre a_{n+1} - a_n alors u_{n+1} = u_n + 8. Autrement dit, (u_n) est une suite arithmétique de raison 8, d’où

u_n = u_1 + 8(n-1)

Autrement dit, u_n est de la forme u_n = 8n + m où m est un nombre entier constant (en fait, m=a_2 - a_1 - 8). Ainsi, a_{n+1} - a_n = 8n + m. Par somme télescopique,

\displaystyle a_{n+1} - a_1 = \sum_{k=1}^{n} (8k + m)

En utilisant des résultats classiques sur la somme des entiers, on a alors

a_{n+1} - a_1 = 8 \times \dfrac{n(n+1)}{2} + m \times n

On en déduit que

a_{n+1} = 4(n^2+ n) + mn + a_1

D’où:

a_{n+1} = 4n^2 + bn + c avec b = 4+m et c=a_1

Ainsi, a_{n+1} = P(n) avec P un polynôme du second degré à coefficients entiers. Cela veut bien dire que les nombres sur une diagonale sont des images par les entiers naturels de polynômes du second degré à coefficients entiers.

Un dernier exemple pour la route

Si on reprend les calculs précédents, nous pouvons même trouver explicitement le polynôme associé à une diagonale donnée. Par exemple, si on prend la diagonale a_1 = 4, a_2 = 14, a_3 = 32, a_4 =58,… montrée dans la vidéo:

celle-ci peut être représentée par le polynôme P(n) = 4n^2 + bn + c avec

b = 4 + m = 4 + a_2 - a_1 - 8 = 4 + 14  - 4 - 8 = 6

et

c = a_1 = 4

c’est-à-dire par le polynôme P(n) = 4n^2 + 6n + 4. Vous pouvez vérifier que P(0), P(1), P(2) et P(3) valent respectivement 4, 14, 32 et 58.

Enfin, si vous vous demandez pourquoi le polynôme montré dans la vidéo est Q(n) = 4n^2 - 2n + 2 (et non pas P(n) = 4n^2 + 6n + 4), cela vient tout simplement d’un décalage d’indice. Ces polynômes sont liés par la relation Q(n) = P(n-1). Autrement dit a_1 = P(0)= Q(1), a_2 = P(1) = Q(2), etc.

Bref, tout ça pour dire que les diagonales de la spirale d’Ulam sont bien représentées par des polynômes du second degré !

Publié dans Arithmétique | Tagué , , , , , , , | 2 commentaires

Fabriquez vos propres critères de divisibilité

Publié le 11 avril 2020 par blogdemaths

Tout le monde connaît les critères de divisibilité par 2, par 3, par 4, par 5 ou par 6. Je vous les rappelle : un nombre est divisible par

  • 2 si son dernier chiffre est 0, 2, 4, 6 ou 8
  • 3 si la somme de ses chiffres est elle-même divisible par 3
  • 4 si ses deux derniers chiffres forment un nombre divisible par 4
  • 5 s’il se termine par 0 ou 5
  • 6 s’il est divisible par 2 et par 3

Cependant, si on demande de dire si un nombre est divisible par 7, je ne suis pas sûr que tout le monde sache répondre. En Novembre 2019, un jeune Nigérian vivant au Royaume-Uni du nom de Chika Ofili a reçu un « TruLittleHero Awards » pour avoir découvert un critère de divisibilité par 7.  Voici l’énoncé du test de Chika (comme il l’a nommé) pour lequel il a été récompensé:

Un nombre est divisible par 7 si, et seulement si, la somme de son nombre de dizaines et de 5 fois son nombre des unités est divisible par 7.

Même si ce critère n’était en fait pas du tout nouveau et qu’il était déjà connu depuis longtemps, c’est une belle performance pour un jeune de cet âge de l’avoir trouvé.

Le test de Chika permet en particulier de savoir si les Sept nains sont bien au complet.

Un exemple

Voyons comment utiliser ce critère pour déterminer si 651 est divisible par 7. Le nombre de dizaines est 65 et le nombre des unités est 1. On calcule:

65+ 5 \times 1 = 70

Comme 70 est un multiple de 7, il en va de même pour 651 qui est donc divisible par 7. Bien entendu, on peut répéter cette opération si l’on tombe sur un nombre dont on ne voit pas tout de suite qu’il est divisible par 7. Par exemple, pour savoir si  4826 est divisible par 7, on calcule successivement:

482 + 5 \times 6 = 512

51 + 5 \times 2 = 61

6 + 5 \times 1 = 11

Comme 11 n’est pas divisible par 7,  4826 non plus n’est pas divisible par 7. Facile, non ?

Une démonstration

Ce critère ayant quand même été parachuté brutalement, il serait de bon ton de le démontrer afin de comprendre pourquoi il marche et, pour cela, nous allons utiliser le très élégant langage des congruences inventé par Gauss. On considère un nombre n dont le nombre de dizaines est a et le nombre d’unités est b. Autrement dit, n= 10a +b.

• Si n est divisible par 7, alors n \equiv 0 \mod[7] donc

10a+b \equiv 0 \mod[7]

En multipliant les deux membres par 5, on obtient:

50a + 5b \equiv 0 \mod[7]

Comme 50 \equiv 1 \mod[7] (car 50 = 7 \times 7 + 1) alors

a + 5b \equiv 0 \mod[7]

ce qui montre que la somme du nombre de dizaines et de 5 fois le nombre des unités est divisible par 7.

• Réciproquement, si a + 5b \equiv 0 alors en multipliant par 10 de chaque côté,

10a+50b \equiv 0 \mod[7]

d’où

10a+b \equiv 0 \mod[7]

ce qui veut bien dire que n=10a+b est divisible par 7.

Analyse de la démonstration

Le point clé de cette démonstration est d’avoir multiplié les deux membres par 5 pour le sens direct et par 10 pour la réciproque. Les nombres 5 et 10 ne sont pas là par hasard et un lien les unis modulo 7 : le nombre 5 \times 10 est un multiple de 7 augmenté de 1, c’est-à-dire que 5 \times 10 \equiv 1 \mod[7]. On dit aussi que 5 est inversible modulo 7 et que « son » inverse est 10 (et, inversement si je puis dire, le nombre 10 est inversible modulo 7 et « son » inverse est 5).

Il se trouve qu’il existe d’autres nombres qui sont inversibles modulo 7 (en fait, tous sauf les multiples de 7 mais c’est une autre histoire). Si nous prenons par exemple le nombre 4, dont l’inverse modulo 7 est 2 (car 4 \times 2 \equiv 1 \mod[7]) alors, en reprenant la démonstration précédente, mais en multipliant par 4, on a

10a +b \equiv 0 \mod[7] \Longrightarrow 40a + 4b \equiv 0 \mod[7] \Longrightarrow 5a + 4b \equiv 0 \mod[7]

car 40 \equiv 5 \mod[7]. Réciproquement, en multipliant par 2,

5a+4b \equiv 0 \mod[7] \Longrightarrow 10a + 8b \equiv 0 \mod[7] \Longrightarrow 10a + b \equiv 0 \mod[7]

car 8 \equiv 1 \mod[7]. Nous venons donc fièrement de fabriquer un nouveau critère de divisibilité qui est le suivant:

Un nombre est divisible par 7 si, et seulement si, la somme de 5 fois son nombre de dizaines et de 4 fois son nombre des unités est divisible par 7.

Par exemple, pour voir que 105 est bien divisible par 7, il suffit de voir que 5\times 10 + 4 \times 5 = 70 est lui-même divisible par 7. Nous méritons aussi notre récompense !

Des critères de divisibilité pour d’autres nombres

Les critères de divisibilité par 7, c’est bien (quoique vous n’auriez peut-être pas dit cela avant de lire cet article) mais les triskaïdékaphobes veulent eux savoir si les nombres qu’ils manipulent sont des multiples de 13. Et bien, je leur dis de prendre un nombre inversible modulo 13 et de faire leur propre critère. Par exemple, si on prend le nombre 2 (qui est bien inversible modulo 13 car 2 \times 20 = 3 \times 13 + 1) alors

2 \times (10a + b) = 20a + 2b \equiv 7a + 2b \mod[13]

On en déduit le critère de divisibilité par 13 suivant:

Un nombre est divisible par 13 si, et seulement si, la somme de 7 fois son nombre de dizaines et de 2 fois son nombre des unités est divisible par 13.

Des critères plus simples

Vous avez probablement dû vous insurger en lisant le critère précédent (sinon, vous devriez). Multiplier un nombre de dizaines par 7 n’est clairement pas chose aisée de tête. Tous ces critères que l’on peut créer ne se valent donc pas tous, et ceux pour lesquels on doit multiplier le nombre de dizaines par un nombre supérieur ou égal à 2 sont évidemment moins pratiques. L’idéal est donc d’avoir un critère où il n’y a pas besoin de multiplier le nombre de dizaines, comme dans le critère énoncé par le jeune Chika. Reprenons donc le nombre 13 et trouvons en un critère de divisibilité plus simple.

Si l’on en croit les démonstrations précédentes,  cela revient donc à trouver un nombre k tel que k \times 10 \equiv 1 \mod[13]. Autrement dit, il s’agit de trouver un inverse de 10 modulo 13.

Pour cela, on peut utiliser un algorithme bien connu qu’on nomme l’algorithme d’Euclide étendu (que je ne détaillerai pas ici… mais il existe des calculateurs en ligne). Sachant que 4 est un inverse de 10 modulo 13, en mutlipliant n=10a +b par 4, il vient

10a + b \equiv 0 \mod[13] \Longrightarrow 40a + 4b \equiv 0 \mod[13] \Longrightarrow a + 4b \equiv 0 \mod[13]

La réciproque étant aussi vraie, on en déduit alors le critère de divisibilité par 13 suivant:

Un nombre est divisible par 13 si, et seulement si, la somme de son nombre de dizaines et de 4 fois son nombre des unités est divisible par 13.

Généralisation

Vous l’aurez compris, pour obtenir un critère de divisibilité simple par un nombre m donné, il suffit de trouver un inverse de 10 modulo m. Par exemple, comme un inverse de 10 modulo m=19 est 2, alors un nombre sera divisible par 19 si, et seulement si, la somme de son nombre de dizaines et de 2 fois son nombre des unités est divisible par 19.

Une dernière question se pose alors: que se passe-t-il si 10 ne possède pas d’inverse modulo m ? Par exemple, si m=14 ou m=420, un tel inverse de 10 n’existe pas (on peut en fait montrer qu’un inverse existe si, et seulement si, 10 et m sont premiers entre eux c’est-à-dire si, et seulement si, m n’est divisible ni par 2, ni par 5). Dans ce cas, il faut se ramener à d’autres nombres, un peu comme pour savoir si un nombre est divisible par 6 il faut et il suffit qu’il soit divisible par 2 et 3.

Prenons le cas de m=420: comme les plus grandes puissances de 2 et de 5 divisant 420 sont 2^2 et 5 et que 420 = 2^2 \times 5 \times 21, il suffit alors de connaitre un critère de divisibilité par 4, par 5 et par 21. Vous connaissez déjà des critères de divisibilité par 4 et 5, et vous venez d’apprendre comment créer un critère de divisibilité par 21 donc vous pouvez facilement savoir si un nombre est divisible par 420. Mieux encore: comme 21 = 3 \times 7, il suffit en fait de connaître un critère de divisibilité par 3 et par 7.

Plus généralement, pour obtenir un critère de divisibilité par un nombre quelconque, il suffit de connaître des critères de divisibilité par 2^k et par 5^k mais aussi de fabriquer des critères de divisibilité par p^k où p est un nombre premier différent de 2 et de 5. Et ça, vous savez le faire maintenant.

Notes:

Publié dans Arithmétique, Nombres | Tagué , , , , , , , , | 4 commentaires

2019, année heureuse, année chanceuse

Publié le 1 janvier 2019 par blogdemaths

Les années se suivent et ne se ressemblent pas. Comme chaque année, il est temps de voir ce que 2019 va nous réserver comme lot de surprises mathématiques. Après tout, un peu de maths pour décuver, ça n’a jamais fais de mal à personne (sans doute car personne n’a jamais essayé de décuver en faisant des maths).

Quelques propriétés de 2019

Contrairement à 2018, 2019 ne peut pas s’écrire comme une somme de deux carrés (#déception) mais peut en revanche s’écrire comme une somme de trois carrés:

2019 = 43^2 + 13^2 + 1^2

ce qui n’est déjà pas mal, me direz-vous, car ce n’est pas donné à tous les nombres d’être décomposable en une somme de trois carrés comme le stipule un théorème de Legendre.

Autre propriété intéressante de 2019: c’est un nombre semi-premier c’est-à-dire le produit de deux nombres premiers (2019 = 3 \times 673). Pour être honnête, il n’y a jusque là rien de bien croustillant car 2018 était aussi un nombre semi-premier et que cela se reproduira en 2021. Là où c’est étonnant, c’est que si vous prenez les facteurs premiers de 2019, à savoir 3 et 673, et si vous les concaténez (dans un sens ou dans l’autre) alors vous obtenez encore des nombres premiers car 3673 et 6733 sont aussi des nombres premiers !

Cela est plutôt amusant mais, comme nous allons le voir, toutes ces propriétés font pâle figure à côté de ce que nous réservera réellement 2019. Je peux déjà vous dire que l’année qui vient s’annonce sous les meilleures auspices parce que 2019 est un nombre heureux, mais aussi car c’est un nombre chanceux ! De la joie et de la chance, n’est-ce pas tout ce qu’on attend finalement de la nouvelle année ? Eh bien 2019 va vous l’offrir… du moins, mathématiquement.

Vous ne savez pas ce qu’est un nombre heureux, ni ce qu’est un nombre chanceux ? Lisez donc la suite pour le savoir…

Heureux qui comme 2019…

Commençons par expliquer ce qu’est un nombre heureux. Prenez un nombre entier positif non nul, élevez chacun des chiffres qui le composent au carré et faites la somme des résultats.

Par exemple, si on prend le nombre 45 au départ, le nombre obtenu avec ce processus est

4^2 + 5^2 = 41.

Rien ne vous empêche de recommencer cette opération avec le dernier nombre obtenu à chaque fois, et vous obtenez alors une suite de nombres entiers. Par exemple, avec le nombre 45 au départ, vous obtenez la suite:

45 \longrightarrow 41 \longrightarrow 17 \longrightarrow 50\longrightarrow \cdots

Avant de dire ce qu’est un nombre heureux (je sais que vous trépignez d’impatience), remarquons qu’il y a deux nombres entiers qui ont statut très particulier quand il s’agit de faire la somme des carrés des chiffres: il s’agit de 1 et de 4. En effet,

  • pour n=1, la somme des carrés des ses (!) chiffres est 1^2=1. Cela veut dire que si on tombe sur le nombre 1 à une étape donnée, on retombera uniquement sur 1 à tous les tours suivants:
    \cdots \longrightarrow 1 \longrightarrow 1 \longrightarrow 1\longrightarrow \cdots
  • pour n=4, on obtient successivement les nombres 4^2 = 16, 1^2+6^2=37, 3^2+7^2 = 58, 5^2 + 8^2 =  89, 8^2 + 9^2 = 145, 1^2 + 4^2 + 5^2 =  42 (!), 4^2 + 2^2 = 20 et finalement 2^2 + 0^2 = 4. Autrement dit, si à un moment donné on tombe sur le nombre 4, on entre alors dans un cycle qui va se répéter indéfiniment, à savoir le cycle 4, 37, 58, 89, 145, 42, 20:
    \cdots \longrightarrow 4 \longrightarrow 37 \longrightarrow 58 \longrightarrow 89 \longrightarrow 145 \longrightarrow 42 \longrightarrow  20 \longrightarrow  4 \cdots

On peut démontrer (voir en fin d’article) que quelque soit l’entier naturel n>0 depuis lequel on part, on tombera toujours soit sur 1 (et dans ce cas, à partir d’un moment la suite ne contiendra que des 1), soit sur 4 (et dans ce cas, à partir d’un moment, le cycle 4, 37, 58, 89, 145, 42, 20 se répétera).

Autrement dit, le monde se divise en deux catégories. Ceux qui tombent un jour sur 1 et ceux qui tombent sur 4.

Les nombres qui atteindront à un moment le nombre 1 par ce processus s’appellent des nombres heureux. Les autres (ceux qui tomberont sur 4) s’appellent des nombres malheureux.

Revenons à 2019. La suite des nombres obtenus en partant de 2019 est la suivante:

2019 \longrightarrow 86 \longrightarrow 100 \longrightarrow  1

Vous comprenez maintenant pourquoi 2019 est un nombre heureux. Au fait, est-ce rare une année heureuse ? Si on compte depuis l’an I alors 2019 sera la 301ème année heureuse. Ce n’est pas très fréquent mais ça n’est pas si rare que cela non plus.

Une chance au grattage, une chance au tirage

Comme nous l’avons dit, 2019 est aussi ce qu’on appelle un nombre chanceux. Pour comprendre ce que c’est, nous allons écrire à la suite tous les nombres entiers et nous allons « tuer » (sans pitié !) certains nombres en suivant les règles suivantes:

  • On épargne 1. Il ne sera pas tué.
  • On tue tous les nombres en allant de 2 en 2.
  • On épargne le plus petit nombre n restant qu’on n’a pas déjà épargné.
  • On tue tous les nombres parmi ceux qui ne sont pas encore tués en allant de n en n.
  • Et on recommence ainsi de suite.

Pour bien comprendre ces règles (momentanément) obscures, appliquons-les pas à pas:

1. On commence par écrire la liste de tous les entiers.2. On épargne 1 et, pour représenter cela, on l’entoure.3. On barre (c’est moins violent que tuer !) tous les nombres en allant de 2 en 2.4. On entoure le plus petit nombre parmi ceux n’ont pas été barrés, c’est-à-dire 3.5. Parmi les nombres restants (ceux qui n’ont pas été barrés), on barre tous les nombres en allant de 3 en 3.6. On entoure le plus petit nombre restant qui n’ pas encore été entouré, à savoir 7.7. Parmi tous les nombres restants, on barre tous les nombres en allant de 7 en 7.

8. Etc.

Si vous voulez vous amuser à faire cela pour 100 nombres, je vous ai mis ci-dessous une grille à imprimer soi-même et à barrer. Croyez-moi, c’est mieux que les mots croisés ou que les sudokus (mais moins bien que des Chiffres et des Lettres quand même). Pour la correction, voir en fin d’article.

Lorsqu’on a terminé ce processus, tous les survivants (les nombres entourés) sont appelés des nombres chanceux. Là aussi, vous comprenez maintenant d’où vient le terme (et contrairement à Highlander, à la fin, il ne doit pas forcément n’en rester qu’un).

Pour voir que 2019 est un nombre chanceux, il « suffit » de faire le tableau des nombres allant de 1 à 2019 et de barrer méthodiquement (jusqu’à ce que mort d’ennui s’en suive) tous les nombres jusqu’à voir que 2019 est épargné. Si vous ne me croyez pas, regardez donc le tableau ci-dessous et vous pourrez constater que 2019 a échappé à son destin. Une année chanceuse, je vous dis !

Cliquez sur l’image pour l’agrandir (mais je trouve qu’on arrive quand même très bien à lire comme ça).

Nous sommes donc ravis d’apprendre que 2019 est un nombre chanceux. Cependant, ce n’est pas non plus une chose si rare que cela que d’être un nombre chanceux car, depuis l’an I, il y a eu 278 années chanceuses (2019 y compris). Et pourtant…

La chance sourit aux nombres heureux

Ce qui fait la particularité de 2019 dans tout cela, c’est qu’il y a eu très peu d’années qui cumulaient à la fois le fait d’être heureuses et chanceuses. Pour tout vous dire, 2019 ne sera que la 46ème année à avoir cette particularité. La dernière fois qu’une année était heureuse et chanceuse, c’était en 1995 et cela ne se reproduira plus avant 2115 (on a donc le temps de voir venir !).

Je vous souhaite une très bonne année et j’espère qu’elle sera aussi heureuse et chanceuse pour vous qu’elle l’est pour le nombre 2019 !

Notes :

Sources :

Publié dans Nombres | Tagué , , , | 122 commentaires