Chapitre extrait du Tome 5 — Arithmétique du livre « Objectif Olympiades de Mathématiques » de Mohammed Aassila. Réservé aux élèves se préparant aux concours d'olympiades de niveau lycée.

8.2 Fonction indicatrice d'Euler

On commence d'abord par introduire la fonction de Möbius $\mu$ dont on aura besoin, par la suite, pour donner une généralisation de la fonction indicatrice d'Euler $\varphi$.

Définition (Fonction de Möbius)

Pour $n\in {\mathbb{N}}^{\ast }$ on définit la fonction de Möbius $\mu$ par

$$\mu (n)=\{\begin{array}{ll}1& \text{si }n=1\\ 0& \text{si }{p}^2\mid n\text{ pour un certain nombre premier }p\\ (-1{)}^k& \text{si }n=p_1\cdots p_k\text{ ouˋ }{p}_1,\dots ,p_k\text{ sont des premiers distincts}\end{array}$$

• $\mu (2)=-1$, $\mu (6)=1$, $\mu (12)=\mu (2^2\cdot 3)=0$.
• La fonction de Möbius $\mu$ est multiplicative : $\mu (m\cdot n)=\mu (m)\cdot \mu (n)$ pour $m,n\in {\mathbb{N}}^{\ast }$.
• Si $f$ est une fonction multiplicative, alors la fonction $F$ définie par $$F(n)=\sum _{d\mid n}f(d)$$ est aussi multiplicative. De plus, si $n=p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k}$ est la décomposition de $n$ en produit de facteurs premiers alors on a : $$F(n)=\prod _{i=1}^k\left(1+f(p_i)+f(p_i^2)+\cdots +f(p_i^{{\alpha }_i})\right).$$
• Pour tout entier $n\ge 2$ on a : $\sum _{d\mid n}\mu (d)=0$.

Définition (Fonction indicatrice d'Euler)

Pour $n\in {\mathbb{N}}^{\ast }$, on note $\varphi (n)$ le nombre d'entiers $m$ tels que :

$$m\le n\text{et}\gcd (m,n)=1.$$

La fonction $\varphi$ est appelée fonction indicatrice d'Euler.

• $\varphi (1)=1$, et pour tout nombre premier $p$ on a : $\varphi (p)=p-1$.
• Si pour $n\in {\mathbb{N}}^{\ast }$ on a $\varphi (n)=n-1$, alors $n$ est premier.

Théorème (C. F. Gauss)

Pour tout $n\in {\mathbb{N}}^{\ast }$ on a :

$$\sum _{d\mid n}\varphi (d)=n.$$

Démonstration

Soient $d_1,d_2,\dots ,d_k$ les diviseurs de $n$ et $S_i=\{m:m\le n\text{ et }\gcd (m,n)=d_i\}$ pour $i\in [1,k]$. Si $m\in S_i$, alors $m=d_i{m}^{\prime }$ avec $\gcd (m^{\prime },\frac{n}{d_i})=1$. Comme $m^{\prime }\le \frac{n}{d_i}$, alors par la définition de $\varphi$ il s'ensuit que $|S_i|=\varphi \left(\frac{n}{d_i}\right)$ (où $|S_i|$ est le cardinal de l'ensemble $S_i$). Les ensembles $S_1,S_2,\dots ,S_k$ forment une partition de $\{1,2,\dots ,n\}$, alors :

$$\sum _{i=1}^k\varphi \left(\frac{n}{d_i}\right)=\sum _{i=1}^k|S_i|=n.$$

Or, $\{\frac{n}{d_1},\frac{n}{d_2},\dots ,\frac{n}{d_k}\}=\{d_1,d_2,\dots ,d_k\}$, par suite $\sum _{d\mid n}\varphi (d)=n$.

Théorème

Si $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$ est la décomposition en produit de facteurs premiers de l'entier $n>1$, alors :

$$\varphi (n)=n\left(1-\frac{1}{p_1}\right)\cdots \left(1-\frac{1}{p_k}\right).$$

Démonstration

Pour tout nombre premier $p$ et tout entier $\alpha \in {\mathbb{N}}^{\ast }$ on a :

$$\varphi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}=p^{\alpha }\left(1-\frac{1}{p}\right).$$

En effet, le nombre de diviseurs positifs de $p$ et ne dépassant pas $n$, sont au nombre de $p^{\alpha -1}$, par suite $\varphi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}$. La fonction $\varphi$ est clairement multiplicative (d'après le théorème précédent), d'où :

$$\varphi (n)=\varphi (p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k})=\varphi (p_1^{{\alpha }_1})\cdots \varphi (p_k^{{\alpha }_k})$$ $$=p_1^{{\alpha }_1}\left(1-\frac{1}{p_1}\right)\cdots p_k^{{\alpha }_k}\left(1-\frac{1}{p_k}\right)$$ $$=p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k}\left(1-\frac{1}{p_1}\right)\cdots \left(1-\frac{1}{p_k}\right)$$ $$=n\left(1-\frac{1}{p_1}\right)\cdots \left(1-\frac{1}{p_k}\right).$$

Remarque : En écrivant la relation ci-dessus comme :

$$\varphi (n)=\frac{n}{p_1\cdots p_k}(p_1-1)\cdots (p_k-1)$$

alors on déduit que $\varphi (n)$ est un entier pair pour tout $n\ge 3$.

Théorème (généralisation de la fonction d'Euler)

Soit $f$ une fonction de ${\mathbb{N}}^{\ast }$ vers l'ensemble des entiers vérifiant $f(m+n)\equiv f(n)(\mathrm{mod}m)$ pour tous $m,n\ge 1$ (par exemple un polynôme à coefficients entiers). Soient $g(n)$ le nombre d'éléments, parmi $\{f(1),f(2),\dots ,f(n)\}$, qui sont divisibles par $n$, et $h(n)$ le nombre d'éléments parmi le même ensemble et qui sont premiers avec $n$. Alors on a :

$$h(n)=n\sum _{d\mid n}\frac{\mu (d)}{d}g(d)=n\prod _{j=1}^k\left(1-\frac{g(p_j)}{p_j}\right)$$

où $n=p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k}$ est la décomposition de $n$ en produit de facteurs premiers.

Démonstration

Soient $m$ et $n$ deux entiers strictement positifs et premiers entre eux, et $1\le a\le m$, $1\le b\le n$ deux entiers. Alors, par le théorème des restes chinois et les propriétés de la fonction $f$ on a :

$$m\mid f(a)\text{ et }n\mid f(b)⟺mn\mid f(x)$$

où $x$ est l'unique entier tel que $x\equiv a(\mathrm{mod}m)$, $x\equiv b(\mathrm{mod}n)$ et $1\le x\le \min \{m,n\}$. D'où $g$ est une fonction multiplicative. Pour un diviseur $d$ de $n$, le nombre d'éléments de $\{f(1),\cdots ,f(n)\}$ qui sont divisibles par $d$ est égal à $\frac{n}{d}g(d)$. D'après le principe d'inclusion-exclusion, on déduit que :

$$h(n)=n-\sum _{i=1}^k\frac{n}{p_i}g(p_i)+\sum _{1\le i<j\le k}\frac{n}{p_i{p}_j}g(p_i{p}_j)-\cdots$$

Finalement, on a :

$$h(n)=n\prod _{j=1}^k\left(1-\frac{g(p_j)}{p_j}\right).$$

Théorème (Andrzej Schinzel)

Il existe une infinité d'entiers naturels strictement positifs et pairs $k$ pour lesquels l'équation $\varphi (n)=k$ n'a pas de solutions.

Démonstration

On prend $k=2\cdot 7^m$ avec $m\in {\mathbb{N}}^{\ast }$. Si $n=p_1^{{\alpha }_1}\cdots p_h^{{\alpha }_h}$, alors

$$\varphi (n)=p_1^{{\alpha }_1}\left(1-\frac{1}{p_1}\right)\cdots p_h^{{\alpha }_h}\left(1-\frac{1}{p_h}\right)=p_1^{{\alpha }_1-1}\cdots p_h^{{\alpha }_h-1}(p_1-1)\cdots (p_h-1).$$

Si, au moins, deux des nombres premiers $p_1,\dots ,p_h$ sont impairs, alors $4\mid \varphi (n)$ et $\varphi (n)\ne k$. Si $p_i=7$, pour un certain $i$, alors $3\mid \varphi (n)$ et $\varphi (n)\ne k$. Si aucun nombre premier $p_i\ne 7$ n'admet ${\alpha }_i>1$, alors $p_i\mid \varphi (n)$ et par suite $\varphi (n)\ne k$. Donc les seules possibilités restantes sont $n=2^{\alpha }$ ou $n=2^{\alpha }p$ pour un certain $p\ge 3$. Dans le premier cas, $\varphi (n)=2^{\alpha -1}\ne k$. Dans le second cas, si $\alpha >1$, alors $4\mid \varphi (n)$ et $\varphi (n)\ne k$. Si $\alpha \le 1$, alors $\varphi (n)=p-1$. Pour que $\varphi (n)$ soit égal à $k$ on doit avoir $p-1=2\cdot 7^m$ ou $p=2\cdot 7^m+1$. Cependant, on vérifie facilement que $3\mid 2\cdot 7^m+1$, donc forcément $p=3$ et $m=0$, contradiction.

Exemple

Pour tout entier $n\ge 2$, il existe une infinité d'entiers $m$ tels que :

$$\frac{\varphi (n)}{n}=\frac{\varphi (m)}{m}.$$

Soit $p$ un nombre premier, et posons $m=p^{\alpha }k$, $n=p^{\beta }k$ avec $\gcd (k,p)=1$. On a

$$\frac{\varphi (m)}{m}=\frac{\varphi (p^{\alpha })\varphi (k)}{p^{\alpha }k}=\left(1-\frac{1}{p}\right)\frac{\varphi (k)}{k}$$

et

$$\frac{\varphi (n)}{n}=\left(1-\frac{1}{p}\right)\frac{\varphi (k)}{k}=\frac{\varphi (m)}{m}.$$

Exemple

Il existe une infinité d'entiers $n\in {\mathbb{N}}^{\ast }$ tels que : $\varphi (n)=\frac{n}{3}$.

Soit $n=2\cdot 3^m$ avec $m\in {\mathbb{N}}^{\ast }$, alors on a :

$$\varphi (n)=\varphi (2\cdot 3^m)=\varphi (2)\varphi (3^m)=3^m-3^{m-1}=2\cdot 3^{m-1}=\frac{n}{3}.$$

Exemple

1. Si $n$ est un nombre composé, alors on a : $\varphi (n)\le n-\sqrt{n}$.
2. Si $n\in {\mathbb{N}}^{\ast }$ avec $n\ne 2$ et $n\ne 6$, alors on a : $\varphi (n)\ge \sqrt{n}$.

Preuve :

① Comme $n$ est composé alors il admet un facteur premier $p_j\le \sqrt{n}$, par suite

$$\varphi (n)=n\left(1-\frac{1}{p_1}\right)\cdots \left(1-\frac{1}{p_k}\right)\le n\left(1-\frac{1}{\sqrt{n}}\right)=n-\sqrt{n}.$$

② Si $n=2m$ avec $m\ge 2$, alors :

$$\varphi (n)=2m-2^{m-1}=2^{m-1}\ge \sqrt{2m}=\sqrt{n}.$$

Si $n=p^m$, avec $p$ nombre premier impair et $m\ge 2$, alors

$$\varphi (n)=p^m-p^{m-1}=p^{m-1}(p-1)\ge \frac{p}{2}\sqrt{p^m}=\sqrt{2n}.$$

Si $n=p^m$, avec $p$ premier plus grand que 5, alors $\varphi (n)\ge \sqrt{2n}$. Si $n$ est impair ou $4\mid n$, alors :

$$\varphi (n)=\varphi (p_1^{{\alpha }_1})\cdots \varphi (p_k^{{\alpha }_k})\ge \sqrt{p_1^{{\alpha }_1}}\cdots \sqrt{p_k^{{\alpha }_k}}=\sqrt{n}.$$

Si $n=2t$, avec $t$ impair, alors comme $n\ne 6$, on voit que $t$ admet au moins un facteur, puissance d'un premier qui est au moins égal à 5. D'où, $\varphi (n)=\varphi (t)\ge \sqrt{2t}$.

Exemple

Soient $n>6$ un entier et $a_1,a_2,\dots ,a_k$ tous les entiers compris strictement entre 0 et $n$ et qui sont premiers avec $n$. On suppose que $a_2-a_1=a_3-a_2=\cdots =a_k-a_{k-1}>0$. Montrer que $n$ est soit un nombre premier, soit une puissance entière de deux. (OIM, 1991)

Soit $n$ un entier vérifiant la propriété de l'exemple. On distingue deux cas :

Cas 1 : $n$ est impair. Alors 1 et 2 sont premiers avec $n$. L'écart entre deux $a_i$ consécutifs est 1. L'ensemble des entiers inférieurs à $n$ et premiers avec $n$ est donc $[1,k]$. L'entier $n-1$ est également premier avec $n$, donc nécessairement $k=n-1$. Donc, tous les entiers de $[1,n-1]$ sont premiers avec $n$, et en conclusion $n$ est premier.

Cas 2 : $n$ est pair. On suppose par l'absurde que $n=2^{m}q$ avec $q$ impair, $q\ge 3$. Alors, nécessairement $q>3$ ou $m>1$ (car sinon $n=6$, contradiction avec l'énoncé), donc $q+2$ et $q+4$ sont inférieurs à $n$, premiers avec $2^{m}q=n$. L'écart entre deux $a_i$ consécutifs est donc 1 ou 2. Dans chacun des deux cas $(q+2)-2=q$ est alors premier avec $n$, absurde. Donc, $n$ est une puissance de 2.

Réciproquement, les nombres premiers et les puissances de deux vérifient clairement les conditions de l'énoncé.

Exemple

Montrer que :

$$n^2=\sum _{d\mid n}d\sum _{k\mid d}\frac{\varphi (k)\varphi (d/k)}{k}.$$

En utilisant la relation $\sum _{d\mid n}\varphi (d)=n$, et en posant $d=kt$, on a :

$$\sum _{d\mid n}d\sum _{k\mid d}\frac{\varphi (k)\varphi (d/k)}{k}=\sum _{k,t:kt\mid n}t\varphi (t)\varphi (k)=\sum _{t\mid n}t\varphi (t)\sum _{k\mid (n/t)}\varphi (k)$$ $$=\sum _{t\mid n}t\varphi (t)\cdot \frac{n}{t}=n\sum _{t\mid n}\varphi (t)=n^2.$$

8.3 Formule de Legendre

Définition

Soit $p$ un nombre premier. On note $v_p(a)$ l'exposant de $p$ dans la décomposition en produit de facteurs premiers de l'entier naturel $a$. Si $p$ ne divise pas $a$, on pose $v_p(a)=0$.

• $\min \{v_p(a),v_p(b)\}\le v_p(a+b)$. Si $v_p(a)\ne v_p(b)$ alors $v_p(a+b)=\min \{v_p(a),v_p(b)\}$.
• $v_p(ab)=v_p(a)+v_p(b)$.
• $v_p(\gcd (a_1,a_2,\dots ,a_n))=\min \{v_p(a_1),v_p(a_2),\dots ,v_p(a_n)\}$.
• $v_p(\text{lcm}(a_1,a_2,\dots ,a_n))=\max \{v_p(a_1),v_p(a_2),\dots ,v_p(a_n)\}$.
• $a\mid b$ si, et seulement si, pour tout nombre premier $p$ : $v_p(a)\le v_p(b)$.
• $a=b$ si, et seulement si, pour tout nombre premier $p$ : $v_p(a)=v_p(b)$.

Définition

Pour $n\in {\mathbb{N}}^{\ast }$, on note $e_p(n)$ l'exposant du nombre premier $p$ dans la décomposition en produit de facteurs premiers de l'entier $n!$

$e_p$ est appelée la fonction de Legendre associée au nombre premier $p$, et l'on a : $e_p(n)=v_p(n!)$

Théorème (Formule de Legendre)

Soient $p$ un nombre premier et $n\in {\mathbb{N}}^{\ast }$ un nombre entier. Alors, on a :

$$e_p(n)=\sum _{i\ge 1}\lfloor \frac{n}{p^i}\rfloor =\frac{n-S_p(n)}{p-1}$$

où $S_p(n)$ est la somme des chiffres de $n$ lorsqu'il est écrit dans la base $p$.

Démonstration

Si $n<p$ alors il est clair que $e_p(n)=0$. Si $n\ge p$, pour déterminer $e_p(n)$ il suffit de considérer seulement les multiples de $p$ dans le produit $1\times 2\times \cdots \times n$, c'est-à-dire $(1\cdot p)\times (2\cdot p)\times \cdots \times (k\cdot p)=p^{k}k!$ où $k=\lfloor \frac{n}{p}\rfloor$.

Donc : $e_p(n)=\lfloor \frac{n}{p}\rfloor +e_p\left(\lfloor \frac{n}{p}\rfloor !\right)$. En remplaçant $n$ par $\lfloor \frac{n}{p}\rfloor$ et comme $\lfloor \frac{\lfloor n/p\rfloor }{p}\rfloor =\lfloor \frac{n}{p^2}\rfloor$, on obtient :

$$e_p\left(\lfloor \frac{n}{p}\rfloor !\right)=\lfloor \frac{n}{p^2}\rfloor +e_p\left(\lfloor \frac{n}{p^2}\rfloor !\right).$$

En continuant ainsi, on déduit que

$$e_p\left(\lfloor \frac{n}{p^2}\rfloor !\right)=\lfloor \frac{n}{p^3}\rfloor +e_p\left(\lfloor \frac{n}{p^3}\rfloor !\right)$$ $$⋮$$ $$e_p\left(\lfloor \frac{n}{p^{m-1}}\rfloor !\right)=\lfloor \frac{n}{p^m}\rfloor +e_p\left(\lfloor \frac{n}{p^m}\rfloor !\right)$$

où $m$ est le plus petit entier strictement positif tel que $n<p^{m+1}$, c'est-à-dire $m=\lfloor \frac{\ln n}{\ln p}\rfloor$. En sommant les relations ci-dessus on déduit que :

$$e_p(n)=\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\cdots +\lfloor \frac{n}{p^m}\rfloor .$$

Montrons, à présent, que $e_p(n)=\frac{n-S_p(n)}{p-1}$. Si, en base $p$, on a : $n=a_0+a_{1}p+\cdots +a_k{p}^k$ avec $a_0,a_1,\dots ,a_k\in [0,p-1]$ et $a_k\ne 0$ alors :

$$\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\cdots =a_1+a_{2}p+\cdots +a_k{p}^{k-1}+a_2+a_{3}p+\cdots +a_k{p}^{k-2}+\cdots +a_k.$$

Le coefficient de $a_i$ dans le membre de droite est $1+p+\cdots +p^{i-1}$, et comme $1+p+\cdots +p^{i-1}=\frac{p^i-1}{p-1}$, alors on déduit le résultat.

Exemple

Déterminer l'exposant de 7 dans la décomposition en produit de facteurs premiers du nombre $400!$

D'après la formule de Legendre on a :

$$e_7(400)=\lfloor \frac{400}{7}\rfloor +\lfloor \frac{400}{7^2}\rfloor +\lfloor \frac{400}{7^3}\rfloor =57+8+1=66.$$

Exemple

Déterminer l'exposant de 3 dans la décomposition en produit de facteurs premiers du nombre $((3!)!)!$

On a $((3!)!)!=(6!)!=720!$, et par la formule de Legendre :

$$e_3(720)=\lfloor \frac{720}{3}\rfloor +\lfloor \frac{720}{3^2}\rfloor +\lfloor \frac{720}{3^3}\rfloor +\lfloor \frac{720}{3^4}\rfloor +\lfloor \frac{720}{3^5}\rfloor =240+80+26+8+2=356.$$