PPCM, PGCD et valuation p-adique

Selon le théorème fondamental de l’arithmétique, tout nombre entier(*) s’écrit, de façon unique à l’ordre des facteurs près, comme un produit de puissances de nombres premiers, sa décomposition en facteurs premiers.

Pour tout nombre premier p et tout entier x, on note v_p(x) la plus grande puissance de p qui divise x, i.e. celle à laquelle il figure dans la décomposition de x en facteurs premiers. L’application v_p est la valuation p-adique(**).

Dans ce billet, je me propose de montrer sur quelques exemples comment l’utiliser pour obtenir simplement des démonstrations de certaines propriétés.

Tout repose sur les deux observations suivantes.

–– D’après le théorème fondamental de l’arithmétique, des nombres entiers x et y sont égaux si, et seulement si, v_p(x)=v_p(y) pour tout nombre premier p.
–– Pour tout nombre premier p et tous nombres entiers x et y, v_p(xy)=v_p(x)+v_p(y).

Si la seconde observation est évidente, elle n’en est pas moins bien utile. C’est elle, en effet, qui permet une utilisation « algébrique » du théorème fondamental.

Les propriétés que nous allons démontrer avec les valuations p-adiques concernent le PPCM et le PGCD. Pour alléger les écritures, je noterai m(x_1,x_2,\ldots) le PPCM de nombres entiers x_1,x_2,\ldots et d(x_1,x_2,\ldots) leur PGCD. On a alors(***), avec des notations évidentes,

v_p(m(x_1,x_2,\ldots))=\sup\{v_p(x_1),v_p(x_2),\ldots\}\quad\&\quad v_p(d(x_1,x_2,\ldots))=\min\{v_p(x_1),v_p(x_2),\ldots\}

Remarquons par ailleurs que les fonctions m et d sont symétriques; elle ne dépendent donc que de l’ensemble de leurs arguments et non de l’ordre de ceux-ci(****). Il est parfois commode de noter m(A) et d(A) le PPCM et le PGCD des éléments de l’ensemble (fini, non vide) d’entiers A. Dans la foulée, nous poserons v_p(A)=\{v_p(x)|x\in A\}.

\boxed A

Soient A et B des ensembles finis et non vides d’entiers. On a

\begin{cases}m(A\cup B)=m(m(A),m(B))\\[1ex]d(A\cup B)=d(d(A),d(B))\end{cases}

Ces propriétés permettent de calculer les et PPCM et PGCD d’ensembles de plus de deux éléments en se ramenant à de plus petits ensembles voire à deux éléments. Par exemple

d(24,16,72,44)=d(d(24,16),d(72,44))=d(8,4)=4

Par ailleurs, si elles peuvent sembler évidentes, l’utilisation des valuations p-adiques rend leurs vérifications mécaniques. Ainsi, pour un nombre premier quelconque p,

\begin{array}{rcl}v_p(d(A\cup B))&=&\min(v_p(A\cup B))\\[1ex]&=&\min(v_p(A)\cup v_p(B))\\[1ex]&=&\min(\min(v_p(A)),\min(v_p(B)))\\[1ex]&=&\min(v_p(d(A)),v_p(d(B)))\\[1ex]&=&v_p(d(d(A),d(B)))\end{array}

D’où la seconde égalité. Pour la première, on procède de même mais, au lieu d’utiliser la formule \min(P\cup Q)=\min(\min(P),\min(Q)) comme on vient de le faire, on utilisera son analogue pour \sup : \sup(P\cup Q)=\sup(\sup(P),\sup(Q)).

\boxed B

La propriété bien utile

(1) m(x,y)d(x,y)=xy

x,y sont des nombres entiers quelconques est vite expédiée avec les valuations p-adiques. En effet, étant donné un nombre premier p, on peut supposer sans perte de généralité que v_p(x)\geqslant v_p(y) car m, d et le produit de nombres entiers sont symétriques en leurs arguments. Alors

v_p(m(x,y)d(x,y))=v_p(m(x,y))+v_p(d(x,y))=v_p(x)+v_p(y)=v_p(xy)

\boxed C

Voici ce qui pourrait être considéré comme une généralisation de la propriété précédente. Quels que soient les nombres entiers x, y et z, on a

(2) m(x,y)m(y,z)m(z,x)d(x,y,z)=xyz\ m(x,y,z)

Soit de nouveau un nombre premier quelconque p. Les deux membres de (2) étant symétriques en x,y,z, nous pouvons supposer que v_p(x)\leqslant v_p(y)\leqslant v_p(z). Alors, en notant MG et MD les membres de gauche et de droite de l’égalité, il vient

\begin{array}{rcl}v_p(MG)&=&v_p(m(x,y))+v_p(m(y,z))+v_p(m(z,x))+v_p(d(x,y,z))\\[1ex]&=&v_p(y)+v_p(z)+v_p(z)+v_p(x)\\[1ex]&=&v_p(x)+v_p(y)+2v_p(z)\end{array}

puis

\begin{array}{rcl}v_p(MD)&=&v_p(x)+v_p(y)+v_p(z)+v_p(m(x,y,z))\\[1ex]&=&v_p(x)+v_p(y)+2v_p(z)\end{array}

ce qui prouve la propriété.

Pour z=y, il vient MG=m(x,y)^2zd(x,y) et MD=xyz\ m(x,y). En simplifiant alors les deux membres de (2) par m(x,y)z, on retrouve (1).
C’est ici que s’achève ce billet.
_________
(*) Par simplicité, nous nous limiterons dans ce billet aux entiers strictement positifs.
(**) Elle est en fait définie sur \mathbf Z, et s’étend même à \mathbf Q donnant alors naissance au corps des nombres p-adiques et à l’analyse p-adique. Il s’agit de notion et discipline importantes et je renvoie le lecteur intéressé à ce texte de Bruno Winckler qui est une jolie introduction à l’analyse p-adique.
(***) J’ai tendance à considérer que c’est évident mais je vais rassurer le lecteur un peu dubitatif en fournissant une vérification très simple. Je ne détaille que le cas du PPCM car celui du PGCD se règle de façon tout à fait semblable. Pour qu’un nombre soit multiple des nombres x_i, il faut, et il suffit, que, pour chaque nombre premier p, sa valuation p-adique soit plus grande ou égale à celle de chaque x_i. La valuation p-adique du plus petit commun multiple des x_i est donc le plus petit nombre supérieur ou égal à leurs valuations v_p(x_i), c’est-à-dire, leur meilleure borne supérieure.
(****) C’est vrai même si plusieurs arguments sont égaux. Par exemple, d(16,34,54,16)=d(16,34,54) que nous noterons à l’occasion d\{16,34,54\}.

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 )

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.