Le dernier chiffre non nul de n!

Publié le 18/02/17

On se propose ici de calculer, pour tout n\in\mathbb{N}^{*}, le dernier chiffre non nul de n!.

Bien entendu, et c’est tout l’intérêt, on s’interdit d’utiliser une fonction factorielle prédéfinie…

1. Le dernier chiffre non nul f(n) d’un entier n

Soit {n} un entier strictement positif quelconque.

Notons {p} le plus grand entier tel que 10^{p} divise n.

De même, soit {10q+r} la division euclidienne de {10^{-p}\,n} par {10}.

On a alors l’écriture (unique) : {n=10^{p}(10q+r)} avec r\in[\![1,9]\!].

On note alors {f(n)=r} (dernier chiffre non nul dans l’écriture décimale de {n}).

Par exemple : {f(1357)=f(135700)=f(1357000000000)=7}.

L’objectif de cet article est donc le calcul de {f(n!)}.

En attendant, voici une version Python de la fonction f :

Ici, on calcule 20! puis f(20!) :

Évidemment, l’idée est maintenant de calculer le dernier chiffre de n! mais sans calculer n! (je ne mets pas de point d’exclamation ici :-))

2. Une propriété utile de la fonction f

Nous allons montrer que si {f(n)\ne5} et {f(n')\ne5}, alors {f(nn')\ne5}.

On écrit {\begin{cases}n=10^p(10q+r)\cr n'=10^{p'}(10q'+r')\end{cases}}(r,r')\in[\![1,9]\!]^2 et {r\ne5,\,r'\ne 5}.

Alors {nn'=10^{p+p'}\Bigl(10\bigl(10qq'+qr'+q'r\bigr)+rr'\Bigr)}.

Par hypothèse, {rr'} n’est pas divisible par {5}, donc a fortiori par {10}.

Ainsi {f(nn')\equiv rr'\;[10]}, c’est-à-dire {f(nn')\equiv f(n)f(n')\;[10]}.

On a donc prouvé : {\Big(f(n)\ne5,\;f(n')\ne5\Bigr)\Rightarrow f(nn')\ne5}

3. Un résultat arithmétique intermédiaire

On pose {\mu_k=\dfrac12(5k+1)(5k+2)(5k+3)(5k+4)}.

On va montrer {\mu_{k}\equiv 12 [500]}, donc {f(\mu_{k})=2}.

On définit le polynôme {P(X)=(X+1)(X+2)(X+3)(X+4)}.

On trouve : {P(X)-24=X(X+5)(X^{2}+5X+10)}.

Ainsi {P(5k)-24=125k(k+1)(5k^{2}+5k+2)}.

On remarque finement que {5k^{2}+5k+2\equiv (k+2)(k+3) [4]}.

Ainsi {k(k+1)(5k^{2}+5k+2)\equiv k(k+1)(k+2)(k+)\equiv 0 [8]}

Donc {P(5k)\equiv 24 [1000]}, donc {\mu_{k}\equiv 12 [500]}, donc {f(\mu_{k})=2}.

On pouvait utiliser ici les capacités de calcul symbolique du package sympy de Python.

On commence par charger ce package et on définit q comme une variable symbolique.

Les lignes suivantes confirment bien que que \mu_{k}\equiv 12\;[500] :

4. Une première réduction de f(n!)

Pour tout n\in\mathbb{N}, soit {\matn=5q_{n}+r_{n}} la division de {n} par {5}.

Posons {u_n=\displaystyle\prod_{j=1}^{r_{n}}(5q_{n}+j)\displaystyle\prod_{k=0}^{q_{n}-1}\mu_k} (un produit « vide » vaut {1}).

On va montrer {n!=10^{q_{n}}\,q_{n}!\;u_n}, donc {f(n!)=f(q_{n}!\,u_n)}.

Pour cela, on regroupe les facteurs suivants dans {n!=\displaystyle\prod_{m=1}^{5q_{n}+r_{n}}m} :

  • d’une part les {m=5k}, avec {1\le k\le q_{n}}
  • d’autre part les {m=5q_{n}+j}, avec {1\le j\le r_{n}}
  • enfin les {(5k+1)(5k+2)(5k+3)(5k+4)=2\mu_{k}}, où {0\le k\lt q_{n}}

Remarque: dans les calculs suivants, les produits éventuellement « vides » valent {1}.
{\begin{array}{rl}n!&=\displaystyle\prod_{k=1}^{q_{n}}(5k)\;\displaystyle\prod_{j=1}^{r_{n}}(5q_{n}+j)\;\displaystyle\prod_{k=0}^{q_{n}-1}\Bigl(\displaystyle\prod_{j=1}^4(5k+j)\Bigr)\\\\&=5^{q_{n}}\;q_{n}!\;\displaystyle\prod_{j=1}^{r_{n}}(5q_{n}+j)\;\displaystyle\prod_{k=0}^{q_{n}-1}(2\mu_k)=10^{q_{n}}\;q_{n}!\;u_n\end{array}}On en déduit effectivement : {f(n!)=f(q_{n}!\,u_n)}.

5. On a toujours f(n!)\ne 5

Pour tout n\in\mathbb{N}, soit {n=5q_{n}+r_{n}} sa division par {5}.

On rappelle la définition de l’entier u_n donnée dans (4).

On va montrer que {\forall n\in\mathbb{N},\;f(n!)\ne 5}, par récurrence forte sur {n}.

On sait déjà que {f(0!)=1}.

Avec {n\ge1}, on suppose {f(m!)\ne5} pour {0\le m\lt n} (en particulier {f(q_{n}!)\ne5}).

Aucun des facteurs de {u_n} n’est divisible par {5} (rappel {\mu_k\equiv 2 [10]}).

Il en est donc de même de {u_n}.

Ainsi {f(u_n)\ne5} et {f(q_{n}!)\ne5}, donc {f(n!)=f(q_{n}!\,u_n)\ne5} d’après (2).

Conclusion : {\forall\, n\in\mathbb{N},\;f(n!)\ne5}.

NB: d’après (2) et (4), on a: {f(n!)=f(q_{n}!\,u_n)\equiv f(q_{n}!)f(u_{n}) [10]}.

Enfin, puisque 10 ne divise par u_n, on a : {f(u_{n})\equiv u_{n}\; [10]}.

6. Quelques propriétés de la suite n\mapsto u_n

  • On va montrer que si {n\ge5} alors {u_{n+20}\equiv 6u_{n} [10]}.

    On a : {u_{n+20}=\displaystyle\prod_{j=1}^{r_{n}}=\displaystyle\prod_{j=1}^{r_{n}}(20+5q_{n}+j)\;\displaystyle\prod_{k=0}^{q_{n}-1}\mu_k\;\displaystyle\prod_{k=q_{n}}^{q_{n}+3}\mu_k}.

    D’une part : {\displaystyle\prod_{k=q_{n}}^{q_{n}+3}\mu_k\equiv 2^{4}\equiv 6 [10]}.

    D’autre part : {\displaystyle\prod_{j=1}^{r_{n}}(20+5q_{n}+j)\equiv \displaystyle\prod_{j=1}^{r_{n}}(5q_{n}+j) [10]}.

    Il en résulte : {u_{n+20}\equiv6\;\displaystyle\prod_{j=1}^{r_{n}}(5q_{n}+j)\;\displaystyle\prod_{k=0}^{q_{n}-1}\mu_k\equiv 6u_n [10]}.

  • On va montrer que la suite {(f(u_{n}))_{n\ge5}} est de périodique {20}.

    D’une part {u_n} est pair car divisible par {\mu_0} (effectivement présent car {q\ge1}).

    Or pour tout {x} de {\{0,2,4,6,8\}}, on a {6x\equiv x [10]}. Ainsi {u_{n+20}\equiv u_n [10]}.

    On trouve alors : {f(u_{n+20})\equiv u_{n+20}\equiv u_{n}\equiv f(u_{n})\;[10]}, pour {n\ge5}.

    Finalement : {\forall\, n\ge5,\;f(u_{n+20})=f(u_{n})}.

7. Le calcul des termes des f(u_n)

On calcule facilement les valeurs de f(u_n) quand n est un multiple de 5.

En effet, si {n=5q}, {u_{5q}=\displaystyle\prod_{k=0}^{q-1}\mu_k\equiv2^q [10]}.

En particulier {f(u_5)=2,f(u_{10})=4,f(u_{15})=8,f(u_{20})=6}.

On calcule les autres f(u_n) de proche en proche.

En effet, {n=5q+r} avec {1\le r\le 4}, alors {u_{n}\equiv nu_{n-1} [10]}.

Tout cela permet en particulier de calculer les u_n pour 5\le n\le 24.

Pour former le tableau ci-dessous, on place {f(u_5),f(u_{10}),f(u_{15}),f(u_{20})}, en début de ligne.
On complète ensuite les lignes de proche en proche (les calculs se font modulo {10}).
On obtient alors la tableau des u_n, pour 5\le n\le 24 :

\begin{array}{|c|c|c|c|}u_{5}\equiv2&u_{10}\equiv4&u_{15}\equiv8&u_{20}\equiv6\\u_{6}\equiv 6u_{5}\equiv 2 &u_{11}\equiv u_{10}\equiv4 &u_{16}\equiv6u_{15}\equiv8 &u_{21}\equiv u_{20}\equiv 6\\u_{7}\equiv7u_{6}\equiv4&u_{12}\equiv2u_{11}\equiv8&u_{17}\equiv7u_{16}\equiv6&u_{22}\equiv 2u_{21}\equiv2\\u_{8}\equiv 8u_{7}\equiv 2 &u_{13}\equiv3u_{12}\equiv4 &u_{18}\equiv8u_{17}\equiv8 &u_{23}\equiv 3u_{22}\equiv 6&\\u_{9}\equiv9u_{8}\equiv8&u_{14}\equiv4u_{13}\equiv6&u_{19}\equiv9u_{18}\equiv2&u_{24}\equiv 4u_{23}\equiv4\end{array}

La suite des f(u_n), pour 0\le k\le 24 est donc :
2,2,4,2,8,4,4,8,4,6,8,8,6,8,2,6,6,2,6,4

8. Un petit programme Python pour finir

En utilisant ce qui précède, on va programmer une fonction Python calculant f(n!) pour tout n, sans utiliser bien sûr la fonction factorielle mais seulement des congruences, tous les calculs intermédiaires se faisant dans l’intervalle [\![0,n]\!].

Il est particulièrement commode de former le tableau suivant:
\begin{array}{rl}tab &= [f(20), f(21), f(22), f(23), f(24), f(5), f(6),\ldots, f(18), f(19)]\\\\&= [6,6,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2]\end{array}

En effet, pour n\ge 5, la valeur de f(u_n) s’obtient en écrivant \text{tab}[n\!\mod\!20].

Pour calculer f(n!), l’égalité f(n!)\equiv f(q_n!)f(u_n) incite à utiliser la récursivité.

La condition d’arrêt est n\le 4.

Dans ce cas les valeurs f(0),\ldots,f(4) seront lues dans le tableau \text{tab0}=[1,1,2,6,4].

Rappelons qu’on s’interdit d’utiliser la fonction factorielle, même pour de petites valeurs de n.

Voici enfin notre fonction chiffre.

Cette fonction prend en argument un entier n et elle renvoie f(n!)

Par exemple, le dernier chiffre non nul de 2017! est un 8.

Pour ceux qui en douteraient, et uniquement pour le plaisir de se dire qu’on n’a pas eu besoin de calculer ce nombre extravagant, voici 2017! :