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

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 kk 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

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

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

  1. Ping : Quels sont les derniers chiffres du nombre de Graham ? 2ème partie : les 5 derniers chiffres | Blogdemaths

  2. Christophe Bal dit :

    Bonjour.

    Comment ont été faites les animations de la vidéo ?

    J'aime

  3. Ping : Quels sont les derniers chiffres du nombre de Graham ? 2ème partie : les 5 derniers chiffres | Actumaths

  4. The Dude dit :

    Bonjour !

    La qualité de la vidéo est époustouflante. Il y a de la graine de 3Blue1Brown 😉 Je me suis abonné à la chaîne.

    Franchement, bravo !

    Un lecteur de longue date.

    PS. J’ai un petit ennui d’affichage LaTeX au début, « Plus généralement, on définit […] »

    J'aime

  5. JAL dit :

    A 1mn55 dans la vidéo, vous dites que 2 | | 2 = 16
    Or c’est 4

    J'aime

  6. Bonjour,
    Très sympa cet article ! Et tous les autres 🙂

    J'aime

Votre 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 )

Photo Google

Vous commentez à l’aide de votre compte Google. 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 )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.