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]}

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 :

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

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

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

  2. Christophe Bal dit :

    Bonjour.

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

    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.