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.

9.1 Équations fonctionnelles et arithmétique

Définition (Fonction multiplicative)

Une fonction $f:\mathbb{N}\to \mathbb{N}$ est dite multiplicative si $f(xy)=f(x)f(y)$ pour tout $x,y$ premiers entre eux. Si $n=\prod _{i=1}^m{p}_i^{{\alpha }_i}$ est la décomposition de $n$ en produit de facteurs premiers, alors :

$$f(x)=\prod _{i=1}^{m}f(p_i^{{\alpha }_i})=\prod _{i=1}^{m}f(p_i{)}^{{\alpha }_i}.$$

Exemples de fonctions multiplicatives :

• La fonction indicatrice d'Euler $\varphi$.
• La fonction de Möbius définie par $$\mu (n)=\{\begin{array}{ll}0& \text{si }{p}^2\mid n\\ (-1{)}^k& \text{si }n=p_1{p}_2\cdots p_k\end{array}$$
• La fonction $\tau :\mathbb{N}\to \mathbb{N}$ qui calcule le nombre de diviseurs de $n\in \mathbb{N}$. Si $n=p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k}$ alors $$\tau (n)=({\alpha }_1+1)({\alpha }_2+1)\times \cdots \times ({\alpha }_k+1).$$
• La fonction $\sigma :\mathbb{N}\to \mathbb{N}$ qui calcule la somme des diviseurs de $n\in \mathbb{N}$. Si $n=p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k}$ alors $$\sigma (n)=(1+p_1+\cdots +p_1^{{\alpha }_1})\times \cdots \times (1+p_k+\cdots +p_k^{{\alpha }_k}).$$

Théorème

Si $f:\mathbb{N}\to \mathbb{N}$ est une fonction multiplicative alors pour tout $n\in \mathbb{N}$, la fonction $F$ définie par

$$F(n)=\sum _{d\mid n}f(d)$$

vérifie :

$$F(n=p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k})=\left(1+f(p_1)+\cdots +f(p_1^{{\alpha }_1})\right)\times \cdots \times \left(1+f(p_k)+\cdots +f(p_k^{{\alpha }_k})\right).$$

L'application $f\mapsto F$, où $F(n)=\sum _{d\mid n}f(d)$ admet un inverse qui fait appel à la fonction de Möbius :

Théorème

Si $F:\mathbb{N}\to \mathbb{N}$ est une fonction, alors il existe une unique fonction $f$ telle que $F(n)=\sum _{d\mid n}f(d)$, et cette fonction est donnée par :

$$f(n)=\sum _{d\mid n}\mu \left(\frac{n}{d}\right)F(d).$$

9.2 Équations fonctionnelles et bases de numération

L'utilisation des bases de numération permet de résoudre plusieurs équations fonctionnelles. En particulier, l'écriture en base 2 d'un entier naturel $n$ permet de montrer des propriétés intéressantes.

9.3 Polynômes et arithmétique

Dans cette section, nous présentons certains problèmes d'arithmétique dont la résolution fait appel, ou utilise, les polynômes.

Théorème

Soit $P$ un polynôme à coefficients entiers. Alors le quotient $\frac{P(a)-P(b)}{a-b}$ est un entier pour tout entiers distincts $a$ et $b$.

Propriétés :

• Si $a\equiv b(\mathrm{mod}m)$, alors $P(a)\equiv P(b)(\mathrm{mod}m)$ pour tout polynôme $P\in \mathbb{Z}[X]$.
• Par exemple, comme $a\equiv b(\mathrm{mod}a-b)$, alors $P(a)\equiv P(b)(\mathrm{mod}a-b)$.

Proposition

Soient $P\in \mathbb{Z}[X]$ un polynôme, et $n,k$ deux entiers quelconques. Alors :

1. $P(n+kP(n))\equiv 0(\mathrm{mod}P(n))$.
2. $P(nP(n))\equiv P(0)(\mathrm{mod}P(n))$.

9.3.1 Théorème de Schur

Théorème de Schur (1912)

Soit $f\in \mathbb{Z}[X]$ un polynôme non constant. L'ensemble des diviseurs premiers de la suite $(f(n){)}_{n\ge 1}$ est infini.

Remarque : Il y a plusieurs façons pour démontrer ce théorème. Une méthode simple consiste à considérer le polynôme $f(x)=a_d{x}^d+\cdots +a_{1}x+a_0$, et considérer la suite $f(a_{0}x)=a_0(a_d{a}_0^{d-1}{x}^d+\cdots +1)$. On applique alors la même méthode d'Euclide pour montrer que l'ensemble des nombres premiers est infini. On suppose qu'il existe un nombre fini de nombres premiers $p_1,\dots ,p_m$, et on prend $x=p_1\cdots p_m$ pour aboutir à une contradiction.

9.3.2 Formule du binôme

On rappelle la formule du binôme : pour tout nombres complexes $a,b$, et tout entier $n\ge 1$ on a :

$$(a+b{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k}{b}^k.$$

Théorème

Si $P\in \mathbb{Z}[X]$ est un polynôme à coefficients entiers, alors pour tout entiers $a,b$, et pour tout entier naturel $N\ge 0$ on a :

$$P(a+b)\equiv \sum _{k=0}^N\frac{P^{(k)}(a)}{k!}{b}^k(\mathrm{mod}{b}^{N+1}).$$

En particulier, pour $N=1$ on a :

$$P(a+b)\equiv P(a)+P^{\prime }(a)b(\mathrm{mod}{b}^2).$$

9.3.4 Théorème de Lagrange

Le théorème de Fermat a la conséquence surprenante que pour tout nombre premier $p$, le polynôme $x^p-x$ possède $p$ racines distinctes modulo $p$, à savoir $0,1,\dots ,p-1$. Il y a un autre polynôme ayant les mêmes racines, à savoir $x(x-1)\cdots (x-p+1)$. Bien évidemment, $x^p-x$ et $x(x-1)\cdots (x-p+1)$ ne sont pas des polynômes égaux. Dans ce paragraphe on va définir une relation de congruence pour les polynômes à coefficients entiers, et on montrera que $x^p-x$ et $x(x-1)\cdots (x-p+1)$ sont congrus modulo $p$. On étudiera ensuite l'application $x\mapsto x^d(\mathrm{mod}p)$ lorsque $d\in {\mathbb{N}}^{\ast }$ et $p$ est un nombre premier.

Définition

Soient $n$ un entier, et $f,g$ deux polynômes de $\mathbb{Z}[X]$. On dit que $f$ est congru à $g$ modulo $n$, et l'on note $f\equiv g(\mathrm{mod}n)$, si tous les coefficients du polynôme $f-g$ sont des multiples de $n$, en d'autres termes, s'il existe $h\in \mathbb{Z}[X]$ tel que $f-g=nh$.

Remarques :

• Si $f\equiv g(\mathrm{mod}n)$, alors $f(x)\equiv g(x)(\mathrm{mod}n)$ pour tout $x\in \mathbb{Z}$. La réciproque est fausse, prendre par exemple $f(x)=x^2+x$ et $g(x)=2$, alors $f(x)\equiv g(x)\equiv 0(\mathrm{mod}2)$ pour tout $x\in \mathbb{Z}$, alors que $f\not\equiv g(\mathrm{mod}2)$ car les coefficients de $x^2+x-2$ ne sont pas tous pairs.
• Les polynômes $x(x-1)(x-2)$ et $x^3-x$ sont congrus modulo $3$ car les coefficients de leur différence $(x^3-x)-x(x-1)(x-2)=3x(x-1)$ sont des multiples de $3$. D'autre part, $x^3-x$ et $x(x-1)(x-2)$ ne sont pas congrus modulo $n$ pour tout $n>1$ différent de $3$.

Propriété

Pour tous les polynômes $f,g,h,k\in \mathbb{Z}[X]$, et pour tout entier $n$ on a :

1. $f\equiv f(\mathrm{mod}n)$.
2. Si $f\equiv g(\mathrm{mod}n)$, alors $g\equiv f(\mathrm{mod}n)$.
3. Si $f\equiv g(\mathrm{mod}n)$ et $g\equiv h(\mathrm{mod}n)$, alors $f\equiv h(\mathrm{mod}n)$.
4. Si $f\equiv g(\mathrm{mod}n)$ et $h\equiv k(\mathrm{mod}n)$, alors $f+h\equiv g+k(\mathrm{mod}n)$ et $fh\equiv gk(\mathrm{mod}n)$.

Exemple

Pour tout $f,g\in \mathbb{Z}[X]$, et pour tout nombre premier $p$, on a :

$$(f+g{)}^p\equiv f^p+g^p(\mathrm{mod}p)\text{et}f(x{)}^p\equiv f(x^p)(\mathrm{mod}p).$$

D'après la formule du binôme $(f+g{)}^p=f^p+g^p+\sum _{k=1}^{p-1}(\genfrac{}{}{0ex}{}{p}{k})f^{p-k}{g}^k$, et le fait que $p\mid \left(\genfrac{}{}{0ex}{}{p}{k}\right)$ pour $1\le k\le p-1$ on déduit la première relation. En appliquant, de façon répétée, la première congruence on trouve :

$$f(x{)}^p=(a_0+a_{1}x+\cdots +a_n{x}^n{)}^p\equiv a_0^p+(a_{1}x{)}^p+\cdots +(a_n{x}^n{)}^p(\mathrm{mod}p).$$

En utilisant le théorème de Fermat on obtient $a_i^p\equiv a_i(\mathrm{mod}p)$, ce qui donne la seconde relation.

Théorème (Lemme de Gauss)

Soient $p$ un nombre premier, et $f,g$ deux polynômes à coefficients entiers tels que $f\cdot g\equiv 0(\mathrm{mod}p)$. Alors, $f\equiv 0(\mathrm{mod}p)$ ou $g\equiv 0(\mathrm{mod}p)$.

Théorème

Soient $a$ un entier, et $f\in \mathbb{Z}[X]$ un polynôme à coefficients entiers. Alors, $f(a)\equiv 0(\mathrm{mod}n)$ si, et seulement si, il existe $g\in \mathbb{Z}[X]$ tel que $f(x)\equiv (x-a)g(x)(\mathrm{mod}n)$. De plus, on peut choisir $g$ de degré inférieur ou égal à $\mathrm{deg}(f)-1$.

Théorème de Lagrange

Soient $p$ un nombre premier, et $f$ un polynôme à coefficients entiers. Si, au moins, un des coefficients de $f$ n'est pas un multiple de $p$ (en d'autres termes si $f$ n'est pas congru à $0$ modulo $p$), alors la congruence $f(x)\equiv 0(\mathrm{mod}p)$ possède au plus $\mathrm{deg}(f)$ solutions.

Remarques :

• La preuve se fait par récurrence sur $d=\mathrm{deg}(f)$.
• Le résultat est faux pour les congruences $f(x)\equiv 0(\mathrm{mod}n)$ lorsque $n$ est un nombre composé. Par exemple, la congruence $x^3\equiv x(\mathrm{mod}6)$ possède $6$ solutions, le polynôme $x^3-x$ étant certainement non congru à $0$ modulo $6$.

Comme conséquence du théorème de Fermat, et du théorème de Lagrange, on a le résultat :

Théorème

Pour tout nombre premier $p$ on a :

$$x^{p-1}-1\equiv (x-1)(x-2)\cdots (x-p+1)(\mathrm{mod}p).$$

Démonstration

Soit $f(x)=x^{p-1}-1-(x-1)(x-2)\cdots (x-p+1)$. Alors, $\mathrm{deg}(f)\le p-2$ car $x^{p-1}-1$ et $(x-1)\cdots (x-p+1)$ sont unitaires de degré $p-1$. D'autre part, d'après le théorème de Fermat on a : $f(i)\equiv 0(\mathrm{mod}p)$ pour $1\le i\le p-1$. Donc, d'après le théorème de Lagrange on a : $f\equiv 0(\mathrm{mod}p)$.

Exemple (Roumanie)

Déterminer toutes les paires $(m,n)\in {\mathbb{N}}^{\ast }\times {\mathbb{N}}^{\ast }$, avec $m,n\ge 2$, telles que $a^n-1$ est divisible par $m$ pour chaque $a\in \{1,2,\dots ,n\}$.

Soit $p$ un diviseur premier de $m$ de sorte que $p\mid a^n-1$ pour $1\le a\le n$. Si $p\le n$, on obtient $p\mid p^{n-1}$, une contradiction. D'où, $p\ge n+1$. Il s'ensuit que $1,2,\dots ,n$ sont des solutions deux à deux distinctes de la congruence $x^n\equiv 1(\mathrm{mod}p)$. Donc la congruence :

$$x^n-1-(x-1)\cdots (x-n)\equiv 0(\mathrm{mod}p)$$

est de degré au plus $n-1$ et possède au moins $n$ solutions différentes. Le théorème de Lagrange implique que :

$$x^n-1\equiv (x-1)(x-2)\cdots (x-n)(\mathrm{mod}p).$$

En considérant les coefficients de $x^{n-1}$ on déduit que $p\mid \frac{n(n+1)}{2}$. Comme $p>n$, la seule possibilité est $p=n+1$. En particulier, $n+1$ est un nombre premier $p>2$ et $m$ a un unique diviseur premier, à savoir $p$. On va montrer que $p^2$ ne peut pas diviser $a^{p-1}-1$ pour tout $1\le a\le p-1$, ce qui prouve que $m=p$. En effet, notons que :

$$(p-1{)}^{p-1}-1\equiv (-1{)}^{p-1}+(-1{)}^{p-2}(p-1)p-1\equiv -p(p-1)(\mathrm{mod}{p}^2)$$

et ainsi $p^2$ ne divise pas $(p-1{)}^{p-1}-1$.

Exemple (États-unis)

Soient $p\ge 5$ un nombre premier, et $a,b,c$ des entiers tels que $p\nmid (a-b)(b-c)(c-a)$. Soient $i,j,k$ des entiers naturels tels que $p-1\mid i+j+k$, et pour tout entier $x$ :

$$p\mid (x-a)(x-b)(x-c)\left[(x-a{)}^i(x-b{)}^j(x-c{)}^k-1\right].$$

Montrer que les nombres $i,j,k$ sont divisibles par $p-1$.

Grâce au théorème de Fermat on peut remplacer $i,j,k$ par leurs restes modulo $p-1$ sans changer les hypothèses ou la conclusion. Donc, on peut supposer que $0\le i,j,k<p-1$, et on doit montrer que $i=j=k=0$. Supposons, par l'absurde, que ce n'est pas le cas. Puisque $p-1\mid i+j+k$, on conclut que $i+j+k=p-1$ ou $2(p-1)$. Si $i+j+k=2(p-1)$, on remplace chaque $x\in \{i,j,k\}$ avec $p-1-x$, ce qui ne change pas l'hypothèse ou la conclusion. On peut donc supposer que $i+j+k=p-1$. Finalement, on peut supposer que $i=\max (i,j,k)$. En multipliant la congruence $(x-a)(x-b)(x-c)\left[(x-a{)}^i(x-b{)}^j(x-c{)}^k-1\right]\equiv 0(\mathrm{mod}p)$ par $(x-a{)}^{j+k}$, et en utilisant le théorème de Fermat on obtient :

$$f(x)=(x-a)(x-b)(x-c)\left[(x-b{)}^j(x-c{)}^k-(x-a{)}^{j+k}\right]\equiv 0(\mathrm{mod}p)$$

pour tout $x$. Puisque $p\ge 5$ on a : $\mathrm{deg}(f)\le 3+j+k-1\le 2+\frac{2(p-1)}{3}<p$, et ainsi par le théorème de Lagrange $f(x)\equiv 0(\mathrm{mod}p)$. Grâce au lemme de Gauss on déduit que :

$$(x-b{)}^j(x-c{)}^k\equiv (x-a{)}^{j+k}(\mathrm{mod}p).$$

Comme $i<p-1$ et $i+j+k=p-1$, on a : $j+k\ne 0$, d'où $(x-b{)}^j(x-c{)}^k$ s'annule en $b$ ou en $c$. On déduit que $p$ divise $(b-a{)}^{j+k}$ ou $(c-a{)}^{j+k}$, contradiction avec l'hypothèse. Donc, $i=j=k=0$, et on obtient le résultat demandé.

L'équation $x^d\equiv 1(\mathrm{mod}p)$

Une conséquence immédiate du théorème de Lagrange est le résultat intéressant suivant :

Corollaire

Soient $p$ un nombre premier, et $k\in {\mathbb{N}}^{\ast }$ un entier tel que $x^k\equiv 1(\mathrm{mod}p)$ pour tous les entiers $x$ qui ne sont pas multiples de $p$. Alors, $p-1\mid k$.

Preuve

Soit $d=\gcd (k,p-1)$, alors $d\mid p-1$ et, de plus, pour tout $x$ non divisible par $p$ on a : $x^d\equiv 1(\mathrm{mod}p)$ (car $x^k\equiv 1(\mathrm{mod}p)$ par hypothèse et $x^{p-1}\equiv 1(\mathrm{mod}p)$ d'après le théorème de Fermat). Donc la congruence $x^d\equiv 1(\mathrm{mod}p)$ admet au moins $p-1$ solutions. Le théorème de Lagrange implique $d\ge p-1$. Comme $d=\gcd (k,p-1)$, on conclut que $p-1\mid k$.

Corollaire

1. Si $j$ est un entier strictement positif non divisible par $p-1$, alors : $$1^j+2^j+\cdots +(p-1{)}^j\equiv 0(\mathrm{mod}p).$$
2. Si $f\in \mathbb{Z}[X]$ est un polynôme avec $\mathrm{deg}(f)<p-1$, alors : $$f(0)+f(1)+\cdots +f(p-1)\equiv 0(\mathrm{mod}p).$$

Preuve

1) D'après le corollaire précédent on peut choisir un entier $x$ qui n'est pas divisible par $p$ et tel que $p$ ne divise pas $x^j-1$. Soit $S=1^j+2^j+\cdots +(p-1{)}^j$. Comme les restes de $x,2x,\dots ,(p-1)x$, modulo $p$, forment une permutation de $1,2,\dots ,p-1$ on obtient :

$$x^{j}S=x^j+(2x{)}^j+\cdots +((p-1)x{)}^j\equiv 1^j+2^j+\cdots +(p-1{)}^j\equiv S(\mathrm{mod}p),$$

donc $p$ divise $S(x^j-1)$. Puisque $p$ ne divise pas $x^j-1$, le résultat demandé en découle.

2) Posons $f(x)=a_0+a_{1}x+\cdots +a_d{x}^d$ pour des entiers $a_0,a_1,\dots ,a_d$ et $d<p-1$, alors :

$$f(0)+f(1)+\cdots +f(p-1)=p{a}_0+a_1(1+2+\cdots +(p-1))+\cdots +a_d\left(1^d+2^d+\cdots +(p-1{)}^d\right).$$

D'après la première partie du corollaire, chacune des sommes $1+2+\cdots +(p-1),\dots ,1^d+2^d+\cdots +(p-1{)}^d$ est divisible par $p$, ce qui termine la preuve.

Théorème

Soient $p$ un nombre premier, et $d$ un diviseur positif de $p-1$. Alors, la congruence $x^d\equiv 1(\mathrm{mod}p)$ admet exactement $d$ solutions.

Démonstration

Comme $d\mid p-1$, on peut trouver un polynôme $f\in \mathbb{Z}[X]$ tel que $x^{p-1}-1=(x^d-1)f(x)$, à savoir $f(x)=1+x^d+\cdots +x^{\left(\frac{p-1}{d}-1\right)d}$. D'après le théorème de Fermat la congruence $x^{p-1}\equiv 1(\mathrm{mod}p)$ admet $p-1$ solutions. Chaque solution de cette congruence est une solution de l'une des congruences $x^d\equiv 1(\mathrm{mod}p)$ ou $f(x)\equiv 0(\mathrm{mod}p)$. D'après le théorème de Lagrange, ces deux congruences ont au plus $d$ (respectivement $p-1-d$) solutions. Comme elles ont, au total, $p-1=d+p-1-d$ solutions, on déduit que la première admet $d$ solutions et la seconde admet $p-1-d$ solutions, ce qui termine la preuve.

Exemple (Roumanie)

Soit $n>1$ un entier naturel. Déterminer $d=\gcd (2^n-2,3^n-3,\dots ,n^n-n)$.

Si $n=2$ la réponse est $d=2$. On suppose dans la suite que $n>2$, et soit $p$ un diviseur premier de $d$. Si $p>n$, alors la congruence $x^n\equiv x(\mathrm{mod}p)$ admet des solutions deux à deux distinctes $0,1,2,\dots ,n$ modulo $p$, contradiction avec le théorème de Lagrange. Donc $p\le n$, en particulier $d\mid p^{n-p}$, et ainsi $p^2$ ne peut pas diviser $d$. Ensuite, $p\mid a^{n-1}-1$ pour tout $a$ relativement premier avec $p$ car $p\mid a^n-a$ pour $1\le a\le n$ et $n\ge p$. Le corollaire ci-dessus donne $p-1\mid n-1$. Réciproquement, si $p$ est un tel premier tel que $p-1\mid n-1$ alors $p\mid a^n-a$ pour tous les entiers $a$ et alors $p\mid d$. En d'autres termes, on a montré que :

$$d=\prod _{p-1\mid n-1}p.$$

Exemple

Soient $p$ un nombre premier, et $f\in \mathbb{Z}[X]$ un polynôme tel que $f(0)=0$, $f(1)=1$ et $f(x)$ est congru à $0$ ou $1$ modulo $p$ pour tout $x\in \mathbb{Z}$.

Montrer que $\mathrm{deg}(f)\ge p-1$. (Proposé à l'OIM, 1997)

On suppose, par l'absurde, que ce n'est pas le cas. D'après le dernier corollaire on a :

$$f(0)+f(1)+\cdots +f(p-1)\equiv 0(\mathrm{mod}p).$$

Or le membre de gauche est congru à une somme de zéros et de uns par hypothèse, et il y a au moins un zéro et au moins un 1 dans cette somme. Il est donc impossible d'obtenir un multiple de $p$.

Exemple (Mathematical Reflections)

Déterminer le plus petit degré possible d'un polynôme $f$ non constant, à coefficients entiers, et tel que $f(0),f(1),\dots ,f(p-1)$ soient tous des puissances $(p-1)$-ième.

Soit $f$ un polynôme répondant à la question, et posons $f(i)=x_i^{p-1}$ pour des entiers $x_0,x_1,\dots ,x_{p-1}$. D'après le théorème de Fermat on déduit que $f(i)$ est congru à $0$ ou $1$ modulo $p$ pour tout $0\le i\le p-1$. Supposons que $\mathrm{deg}(f)<p-1$, alors le dernier corollaire donne :

$$f(0)+f(1)+\cdots +f(p-1)\equiv 0(\mathrm{mod}p)$$

et puisque chacun des nombres $f(0),f(1),\dots ,f(p-1)$ est congru à $0$ ou $1$ modulo $p$ on déduit que $f(0),f(1),\dots ,f(p-1)$ sont tous congrus à $0$ modulo $p$ ou tous congrus à $1$ modulo $p$. Donc, il existe $\epsilon \in \{0,1\}$ tel que la congruence $f(x)\equiv \epsilon (\mathrm{mod}p)$ admette au moins $p$ solutions, en contradiction avec le théorème de Lagrange. Donc $\mathrm{deg}(f)\ge p-1$. Puisque $f(x)=x^{p-1}$ vérifie clairement les propriétés requises, on conclut que la réponse est $p-1$.

Théorème de Chevalley-Warning

On donne, à présent, et à titre informatif, le théorème de Chevalley-Warning :

Théorème de Chevalley-Warning (1935)

Soient $p$ un nombre premier, et $k,n$ des entiers strictement positifs. Soient $f_1,f_2,\dots ,f_k\in \mathbb{Z}[X_1,X_2,\dots ,X_n]$ des polynômes à coefficients entiers tels que $n>\mathrm{deg}(f_1)+\mathrm{deg}(f_2)+\cdots +\mathrm{deg}(f_k)$. Alors, le nombre de $n$-uplets $(x_1,x_2,\dots ,x_n)\in \{0,1,\dots ,p-1{\}}^n$ tels que :

$$f_1(x_1,x_2,\dots ,x_n)\equiv f_2(x_1,x_2,\dots ,x_n)\equiv \cdots \equiv f_k(x_1,x_2,\dots ,x_n)\equiv 0(\mathrm{mod}p)$$

est un multiple de $p$.

Une conséquence très utile du théorème de Chevalley-Warning est le résultat suivant, qui garantit l'existence de solutions non triviales aux systèmes de congruences polynomiales, tant que ces systèmes ont suffisamment d'inconnues et une solution triviale.

Corollaire

Sous les hypothèses du théorème de Chevalley-Warning, si $f_i(0,\dots ,0)=0$ pour tout $i$ alors le système :

$$f_1(x_1,\dots ,x_n)\equiv f_2(x_1,\dots ,x_n)\equiv \cdots \equiv f_k(x_1,\dots ,x_n)\equiv 0(\mathrm{mod}p)$$

admet une solution $(x_1,x_2,\dots ,x_n)$ avec au moins un $x_i$ non divisible par $p$.

Preuve

Le théorème de Chevalley-Warning garantit que le nombre de solutions du système est divisible par $p$. L'hypothèse $f_i(0,\dots ,0)=0$ garantit que $(0,0,\dots ,0)$ est une solution du système. Il s'ensuit que le système possède une solution différente de celle-ci, ce qui termine la preuve.

Exemple

Soient $p$ un nombre premier, et $a,b,c$ des entiers. Montrer qu'il existe des entiers $x,y,z$, pas tous divisibles par $p$, tels que : $p\mid a{x}^2+b{y}^2+c{z}^2$.

Conséquence immédiate du corollaire ci-dessus.

Exemple (Théorème de Erdős-Ginzburg-Ziv)

Soit $p$ un nombre premier. Montrer que, parmi n'importe quels $2p-1$ entiers, il y en a $p$ dont la somme est un multiple de $p$.

Nous avons déjà rencontré ce théorème au chapitre 6, on donne ici une nouvelle preuve. En appliquant le corollaire précédent à :

$$f_1(x)=\sum _{i=1}^{2p-1}{a}_i{x}_i^{p-1},f_2(x)=\sum _{i=1}^{2p-1}{x}_i^{p-1}$$

où $a_1,a_2,\dots ,a_{2p-1}$ sont les $2p-1$ entiers donnés, et en choisissant $x_i\in \{0,1\}$, on déduit l'existence d'une sous-famille non vide de nos $2p-1$ entiers dont la somme est un multiple de $p$. En utilisant des arguments supplémentaires, on peut montrer qu'il existe toujours une telle sous-famille de taille exactement $p$.