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

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 :

L’article Une démonstration du théorème d’Euler que j’avais écrit sur ce même blog.

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

Ping : Quels sont les derniers chiffres du nombre de Graham ? 1ère partie : le dernier chiffre | Blogdemaths
Christophe Bal dit :

25 avril 2021 à 14 h 05 min

Bonjour.

Le modulo 16 a « oublié » de changer 27 en 11.

J’aimeJ’aime

Réponse

Votre commentaire Annuler la réponse.

Entrez votre commentaire...

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

E-mail (adresse strictement confidentielle)

Nom

Site web

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

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

Annuler

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.