Par combien de zéros finit 2015! (factorielle) ?

guiditito , , ,

En effet, combien rencontre-t-on de zéros à la fin du nombre 2015! ? Ne vous êtes-vous jamais posés la question ? Moi si. Ce petit problème très simple va nous permettre d’introduire une notion d’arithmétique très cool : la valuation p-adique d’un entier.

Une valuation p-adique

Avant d’aborder la notion de valuation p-adique, il faut se rappeler que tout nombre entier supérieur à 1 admet une décomposition en facteurs premiers. Soit n \in \mathbb N, n \ge 2 . Alors :

n = \prod_{k=0}^i p_k^{\alpha_k} = p_0^{\alpha_0} p_1^{\alpha_1} p_2^{\alpha_2}...p_i^{\alpha_i}

Dans cette formule, tous les p_i sont des nombres premiers et tous les \alpha_i sont des nombres entiers naturels.

Bien, nous pouvons maintenant définir la valuation p-adique d’un entier n . Celle-ci est simplement (que de mots compliqués pour des choses simples !) l’exposant de p dans la décomposition en facteurs premiers de n . On note alors ce nombre v_{p}(n) et on convient que pour tout nombre premier p , v_p(0) = +\infty et v_p(1) = 0 .

Prenons par exemple le nombre 15. On peut dire que 15 = 3^1 \times 5^1 . Donc, en fait, v_5(15) = v_3(15) = 1 , mais aussi v_2(15) = 0 .

Bon c’est plutôt cool tout ça. Mais quel rapport avec notre problème de départ ? En fait, pour trouver le nombre de zéros qu’il y a à la fin de l’écriture décimale de 2015! , il suffit juste de compter le nombre de facteurs 10 dans 2015! . Si 10 était un nombre premier, on regarderait donc la valuation 10-adique de 2015! . Cependant, 10 n’est évidement pas un nombre premier. Par contre, on connait sa décomposition en facteurs premiers, qui est plutôt simple :

10 = 2^1 \times 5^1

On peut donc regarder les valuations 2-adique v_2(2015!) et 5-adique v_5(2015!) de 2015! . On prend la plus petite pour trouver le nombre de facteurs 10 dans 2015! .

La formule de Legendre

Comme 2015! est un nombre très grand, ça s’annonce un peu compliqué. Heureusement pour nous, il existe une méthode très simple pour trouver la valuation p-adique d’une factorielle. Il s’agit d’utiliser la formule de Legendre, que l’on énoncera ainsi :

v_p(n!) = \sum_{k=1}^\infty \lfloor \frac{n}{p^k} \rfloor où \lfloor \frac{n}{p^k} \rfloor désigne la partie entière de \frac{n}{p^k} .

Démontrons cette sympathique formule.

Souvenons-nous déjà que \forall n \in \mathbb{N^{\star}}, n! = 1 \times 2 \times 3 \times 4 \times ... \times n . Soit k \in \mathbb{N^{\star}} . Combien y a-t-il de multiples de p^k entre 1 et n ? Les nombres multiples de p^k sont de la forme m p^k avec m \in \mathbb N . On cherche donc le plus grand entier m tel que m p^k \le n , donc, tel que m \le \frac{n}{p^k} .

Il est immédiat que m = \lfloor \frac{n}{p^k} \rfloor . Pour trouver la valuation p-adique de n! , on compte d’abord le nombre de multiples de p^1 entre 1 et n , puis le nombre de multiples de p^2 (ceux-ci ont déjà été comptés, mais ils faut les compter au moins une deuxième fois, puisque dans leur décomposition en facteurs premiers ils ont un exposant associé à p supérieur ou égal à 2), puis le nombre de multiples de p^3 (que l’on doit compter trois fois par le raisonnement précédent), et ainsi de suite. On peut s’arrêter de compter quand k est devenu si grand que \lfloor \frac{n}{p^k} \rfloor = 0 (ce qui assure que la somme contient un nombre fini de termes non nuls). D’où la formule :

v_p(n!) = \sum_{k=1}^\infty \lfloor \frac{n}{p^k} \rfloor

Appliquons ce résultat à 2015! . On obtient :

v_2(2015!) = \sum_{k=1}^\infty \lfloor \frac{2015}{2^k} \rfloor

v_2(2015!) = \lfloor \frac{2015}{2} \rfloor + \lfloor \frac{2015}{4} \rfloor + \lfloor \frac{2015}{8} \rfloor + \lfloor \frac{2015}{16} \rfloor + \lfloor \frac{2015}{32} \rfloor + \lfloor \frac{2015}{64} \rfloor + \lfloor \frac{2015}{128} \rfloor + \lfloor \frac{2015}{256} \rfloor + \lfloor \frac{2015}{512} \rfloor + \lfloor \frac{2015}{1024} \rfloor + \lfloor \frac{2015}{2048} \rfloor

v_2(2015!) = 1007 + 503 + 251 + 125 + 62 + 31 + 15 + 7 + 3 + 1 + 0 = 2005

(Latex de m**de.)

De même :

v_5(2015!) = \sum_{k=1}^\infty \lfloor \frac{2015}{5^k} \rfloor

v_5(2015!) = \lfloor \frac{2015}{5} \rfloor + \lfloor \frac{2015}{25} \rfloor + \lfloor \frac{2015}{125} \rfloor + \lfloor \frac{2015}{625} \rfloor + \lfloor \frac{2015}{3125} \rfloor

v_5(2015!) = 403 + 80 + 16 + 3 + 0 = 502

Le minimum est bien-sûr 502, on peut donc conclure qu’il y a 502 zéros à la fin de l’écriture décimale de 2015! .

Laisser un commentaire