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.

10.2 Système de numération

Le résultat principal de ce paragraphe est le :

Théorème

Soit $b>1$ un entier naturel. Alors, pour tout entier $n\ge 1$, il existe une unique suite d'entiers $(k,a_0,a_1,\cdots ,a_k)$ telle que $0\le a_i\le b-1$, $i\in \mathbb{J}0,k\mathbb{K}$, $a_k\ne 0$ et : $$n=a_k{b}^k+a_{k-1}{b}^{k-1}+\cdots +a_{1}b+a_0.$$ On note $n=a_k{a}_{k-1}\cdots a_0$. C'est l'écriture de $n$ dans la base $b$.

Lorsque $b=10$, alors c'est la représentation décimale d'un entier. Par exemple : $2015=2\cdot 10^3+0\cdot 10^2+1\cdot 10+5$. En base 3 on a : $1211_3=1\cdot 3^3+2\cdot 3^2+2\cdot 3+1=122_2\cdot 3$.

10.3 Puissances d'entiers

Définition (Carré parfait)

On dit qu'un entier $n$ est un carré parfait si $n=m^2$ pour un certain entier $m$. Si $m=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$ est la décomposition primaire de $m$, alors $n=p_1^{2{\alpha }_1}{p}_2^{2{\alpha }_2}\cdots p_k^{2{\alpha }_k}$.

• L'entier $n$ est un carré parfait si, et seulement si, tous les exposants dans sa décomposition primaire sont pairs.
• L'entier $n$ est une puissance $s$-ème parfaite si, et seulement si, tous les exposants dans sa décomposition primaire sont divisibles par $s$.
• On dit qu'un entier $n$ est sans facteur carré (ou square-free ou quadratfrei) si pour tout diviseur premier $p$, $p^2$ ne divise pas $n$.

Résultats fondamentaux

Propriété 1. Si un entier $n$ est somme de deux carrés alors il en est de même pour $2n$.
En effet, si $n=a^2+b^2$ alors $2n=(a+b{)}^2+(a-b{)}^2$.

Propriété 2. On a l'identité : $$(a^2+b^2)(x^2+y^2)=(ax+by{)}^2+(ay-bx{)}^2=(ax-by{)}^2+(ay+bx{)}^2.$$

Propriété 3. La somme des carrés de cinq entiers strictement positifs et consécutifs n'est jamais un carré parfait.
En effet : $(n-2{)}^2+(n-1{)}^2+n^2+(n+1{)}^2+(n+2{)}^2=5(n^2+2)$. Si $5(n^2+2)$ était un carré parfait, alors $5|(n^2+2)$, c'est-à-dire $n^2\equiv -2(\mathrm{mod}5)$. Or, un carré n'est jamais congru à $3$ modulo $5$, ce qui résout le problème.

Représentation de nombres comme sommes de carrés

Propriété 4. Tout entier $n\in {\mathbb{N}}^{\ast }$ s'écrit comme somme de 5 cubes parfaits.
Une décomposition directe utilise l'identité : $6n=(n+1{)}^3+(n-1{)}^3+(-n{)}^3+(-n{)}^3$.

Propriété 5. Tout nombre rationnel $x\in \mathbb{Q}$ peut s'écrire comme la somme de trois cubes parfaits.
En particulier, si $x$ est rationnel, on peut trouver $a(x),b(x),c(x)$ rationnels tels que $x=a(x{)}^3+b(x{)}^3+c(x{)}^3$.

10.4 Nombres premiers de la forme $4k+3$ et $3k+2$

Proposition fondamentale

Soient $p$ un nombre premier, et $a\in {\mathbb{N}}^{\ast }$ un entier divisant $p-1$. Si $a$ est un entier tel que la congruence $x^n\equiv a(\mathrm{mod}p)$ possède des solutions (en d'autres termes $a$ est une puissance $n$-ième modulo $p$), alors : $p|a$ ou $a^{\frac{p-1}{n}}\equiv 1(\mathrm{mod}p)$.

Preuve. C'est une application immédiate du théorème de Fermat : si $p\nmid a$, alors : $$a^{\frac{p-1}{n}}\equiv (x^n{)}^{\frac{p-1}{n}}=x^{p-1}\equiv 1(\mathrm{mod}p)$$ ce qui permet de conclure.

Corollaire 1

Soit $p$ un nombre premier de la forme $4k+3$. Si $p|a^2+b^2$ pour certains entiers $a,b$, alors $p|a$ et $p|b$.

Preuve. Si $p|a$ alors clairement $p|b^2$ et donc $p|b$. Supposons maintenant que $p\nmid a$, et soit $c$ un entier tel que $ac\equiv 1(\mathrm{mod}p)$. Comme $p|(ac{)}^2+(bc{)}^2$, on obtient $(bc{)}^2\equiv -1(\mathrm{mod}p)$, et par la proposition précédente $(-1{)}^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$. Puisque $p\equiv 3(\mathrm{mod}4)$, on a $\frac{p-1}{2}$ impair, donc $-1\equiv 1(\mathrm{mod}p)$, absurde.

Théorème sur les permutations modulo p

Soient $p$ un nombre premier, et $n\in {\mathbb{N}}^{\ast }$ un entier tel que $\gcd (n,p-1)=1$. Alors les restes de la division euclidienne de $1^n,2^n,\dots ,(p-1{)}^n$ par $p$ forment une permutation de $1,2,\dots ,p-1$.

Démonstration. Il est clair qu'aucun de ces nombres n'est un multiple de $p$. Il suffit donc de montrer que les nombres sont deux à deux non congrus modulo $p$. Supposons que $p|a^n-b^n$ pour certains $a,b\in \{1,2,\dots ,p-1\}$, et notons qu'on peut supposer que $\gcd (a,b)=1$ (car $p$ ne divise pas $\gcd (a,b)$). D'après le théorème de Fermat on a aussi $p|a^{p-1}-b^{p-1}$ et par conséquent : $$p|\gcd (a^n-b^n,a^{p-1}-b^{p-1})=a^{\gcd (n,p-1)}-b^{\gcd (n,p-1)}=a-b,$$ la dernière égalité étant une conséquence de notre hypothèse. Puisque $p|a-b$ et $a,b\in \{1,2,\dots ,p-1\}$, on doit avoir $a=b$, ce qui termine la preuve.

Corollaire 2

Soit $p$ un nombre premier de la forme $3k+2$. Alors :

1. Les restes de la division euclidienne des nombres $1^3,2^3,\dots ,(p-1{)}^3$ par $p$ forment une permutation de $1,2,\dots ,p-1$.
2. Si $p|a^2+ab+b^2$, pour des entiers $a,b$, alors $p|a$ et $p|b$.
3. Si $p\ne 2$ alors il n'existe aucun entier $x$ tel que $x^2\equiv -3(\mathrm{mod}p)$.

Preuve.

• (1) Conséquence directe du théorème précédent avec $n=3$.
• (2) Si $p|a$ alors $p|b$, donc supposons que $p\nmid ab$. Alors $p|(a-b)(a^2+ab+b^2)=a^3-b^3$, et par la propriété (1) on déduit que $p|a-b$. Mais comme $p|a^2+ab+b^2$, il s'ensuit que $p|3a^2$, une contradiction.
• (3) Supposons que $x$ est un tel entier. Puisque $p\ne 2$, il existe un entier $y$ tel que $2y+1\equiv x(\mathrm{mod}p)$, d'où $4y^2+4y+4\equiv 0(\mathrm{mod}p)$, par suite $y^2+y+1\equiv 0(\mathrm{mod}p)$, ce qui contredit la propriété (2).

10.6 Partie entière. Partie fractionnaire

Nous avons étudié, en détail, la notion de partie entière et partie fractionnaire au « Tome 1 : Algèbre » de cette série. On ne présente ici que les exemples en rapport avec l'arithmétique.

Théorème 1

Soient $a,b,c,d$ des nombres réels positifs ou nuls, $f:[a,b]\to [c,d]$ une fonction bijective strictement croissante de graphe $G_f$. On note $n(G_f)$ le nombre de points du graphe $G_f$ à coordonnées entières, alors on a :

$$n(G_f)=\sum _{a\le k\le b}\lfloor f(k)\rfloor +\sum _{c\le k\le d}\lfloor f^{-1}(k)\rfloor +\lceil a-1\rceil \cdot \lceil c-1\rceil -\lfloor b\rfloor \cdot \lfloor d\rfloor (1)$$

avec $k$ prenant les valeurs entières.

Démonstration

Notons que $\lceil x\rceil$ est le nombre d'entiers dans l'intervalle $[0,x[$, $\lfloor x\rfloor$ est le nombre d'entiers dans l'intervalle $]0,x]$, par suite $\lfloor x\rfloor +1$ est le nombre d'entiers dans l'intervalle $[0,x]$.

Pour une région bornée $M$ du plan, on note $n(M)$ le nombre de points à coordonnées entières positives dans $M$. Comme $f$ est bijective et strictement croissante, alors elle est continue, et on peut alors considérer les quatre régions :

$$M_1=\{(x,y)\in {\mathbb{R}}^2:a\le x\le b,0\le y\le f(x)\}$$ $$M_2=\{(x,y)\in {\mathbb{R}}^2:c\le y\le d,0\le x\le f^{-1}(y)\}$$ $$M_3=\{(x,y)\in {\mathbb{R}}^2:0\le x\le b,0\le y\le d\}$$ $$M_4=\{(x,y)\in {\mathbb{R}}^2:0\le x<a,0\le y<d\}$$

D'après les remarques au début de la démonstration on déduit que :

$$n(M_1)=\sum _{a\le k\le b}(\lfloor f(k)\rfloor +1);n(M_2)=\sum _{c\le k\le d}(\lfloor f^{-1}(k)\rfloor +1);$$ $$n(M_3)=(\lfloor b\rfloor +1)(\lfloor d\rfloor +1);n(M_4)=\lceil a\rceil \cdot \lceil c\rceil$$

Comme $M_1\cup M_2=M_3\setminus M_4$ et $M_1\cap M_2=G_f$ alors on déduit que :

$$\sum _{a\le k\le b}(\lfloor f(k)\rfloor +1)+\sum _{c\le k\le d}(\lfloor f^{-1}(k)\rfloor +1)-n(G_f)=(\lfloor b\rfloor +1)(\lfloor d\rfloor +1)-\lceil a\rceil \cdot \lceil c\rceil$$

L'intervalle $[a,b]=[0,b]-[0,a[$ contient $\lfloor b\rfloor +1-\lceil a\rceil$ entiers, et de même pour l'intervalle $[c,d]$ avec $\lfloor d\rfloor +1-\lceil c\rceil$ entiers, on conclut que

$$\sum _{a\le k\le b}\lfloor f(k)\rfloor +\sum _{c\le k\le d}\lfloor f^{-1}(k)\rfloor -n(G_f)=\lfloor b\rfloor \cdot \lfloor d\rfloor -\lceil a-1\rceil \cdot \lceil c-1\rceil$$

Théorème 2

Soient $m,n,s$ des entiers strictement positifs avec $m\le n$. Alors, on a :

$$\sum _{k=1}^s\lfloor \frac{km}{n}\rfloor +\sum _{1\le k\le \lfloor ms/n\rfloor }\lfloor \frac{kn}{m}\rfloor =s\lfloor \frac{ms}{n}\rfloor +\lfloor \frac{\gcd (m,n)\cdot s}{n}\rfloor (2)$$

Démonstration

On commence par montrer le lemme suivant : l'ensemble $\left\{\frac{1\cdot m}{n},\frac{2\cdot m}{n},\dots ,\frac{s\cdot m}{n}\right\}$ contient exactement $\lfloor \frac{\gcd (m,n)\cdot s}{n}\rfloor$ entiers. En effet, si $d=\gcd (m,n)$, alors $m=m_{1}d$, $n=n_{1}d$, $\gcd (m_1,n_1)=1$. L'ensemble en question devient $\left\{\frac{1\cdot m_1}{n_1},\frac{2\cdot m_1}{n_1},\dots ,\frac{s\cdot m_1}{n_1}\right\}$, et puisque $\gcd (m_1,n_1)=1$ alors il y a $\lfloor \frac{s}{n_1}\rfloor$ entiers parmi eux. Finalement, comme $n_1=\frac{n}{d}=\frac{n}{\gcd (m,n)}$ il s'ensuit qu'il y a $\lfloor \frac{\gcd (m,n)\cdot s}{n}\rfloor$ entiers dans l'ensemble.

Revenons maintenant à notre théorème : considérons la fonction $f:[1,s]\to \left[\frac{m}{n},\frac{ms}{n}\right]$ définie par $f(x)=\frac{m}{n}x$. En appliquant le théorème 1 et le lemme ci-dessus, on déduit que :

$$n(G_f)=\lfloor \frac{\gcd (m,n)\cdot s}{n}\rfloor$$

Exemple

Soient $m$ et $n$ deux entiers naturels strictement positifs. Alors, on a :

$$\sum _{k=1}^n\lfloor \frac{km}{n}\rfloor +\sum _{k=1}^m\lfloor \frac{kn}{m}\rfloor =mn+\gcd (m,n)(3)$$

Il suffit de prendre $s=n$ dans le théorème précédent.

Théorème 3

Soient $a,b,c,d$ des nombres réels positifs ou nuls, et $f:[a,b]\to [c,d]$ une application bijective et strictement décroissante. Alors, on a :

$$\sum _{a\le k\le b}\lfloor f(k)\rfloor -\sum _{c\le k\le d}\lfloor f^{-1}(k)\rfloor =\lfloor b\rfloor \cdot \lceil c-1\rceil -\lfloor d\rfloor \cdot \lceil a-1\rceil$$

avec $k$ prenant des valeurs entières.

Démonstration

On utilise les mêmes notations que dans le théorème 1. La fonction $f$ est continue car bijective et strictement décroissante. On considère les quatre régions du plan suivantes :

$$N_1=\{(x,y)\in {\mathbb{R}}^2:a\le x\le b,c\le y\le f(x)\}$$ $$N_2=\{(x,y)\in {\mathbb{R}}^2:c\le y\le d,a\le x\le f^{-1}(y)\}$$ $$N_3=\{(x,y)\in {\mathbb{R}}^2:a\le x\le b,0\le y<c\}$$ $$N_4=\{(x,y)\in {\mathbb{R}}^2:a\le x\le b,c\le y\le d\}$$

On a $N_1=N_2$, d'où $n(N_1)=n(N_2)$ et

$$\sum _{a\le k\le b}(\lfloor f(k)\rfloor +1)=n(N_1)+n(N_3)$$ $$\sum _{c\le k\le d}(\lfloor f^{-1}(k)\rfloor +1)=n(N_2)+n(N_4)$$ $$n(N_3)=(\lfloor b\rfloor +1-\lceil a\rceil )\lceil c\rceil$$ $$n(N_4)=(\lfloor d\rfloor +1-\lceil c\rceil )\lceil a\rceil$$

Par conséquent

$$\sum _{a\le k\le b}\lfloor f(k)\rfloor -\sum _{c\le k\le d}\lfloor f^{-1}(k)\rfloor =(\lfloor b\rfloor +1-\lceil a\rceil )\lceil c-1\rceil -(\lfloor d\rfloor +1-\lceil c\rceil )\lceil a-1\rceil$$ $$=\lfloor b\rfloor \cdot \lceil c-1\rceil -\lfloor d\rfloor \cdot \lceil a-1\rceil$$

10.7 Nombres de Fermat

Fermat a cherché à déterminer les nombres premiers de la forme $2^m+1$. Il a montré le résultat suivant :

Exemple

Si $2^m+1$ est un nombre premier, alors $m$ est une puissance de 2.

Si $m=k\cdot h$ avec $k>1$ entier impair, alors :

$$2^m+1=(2^h{)}^k+1=(2^h+1)(2^{h(k-1)}-2^{h(k-2)}+\cdots -2^h+1)$$

d'où $2^m+1$ non premier.

Définition (Nombres de Fermat)

Les entiers $f_n=2^{2^n}+1$, $n\in \mathbb{N}$, sont appelés les nombres de Fermat. On a :

$$f_0=3,f_1=5,f_2=17,f_3=257,f_4=65573$$

Fermat pensait, à tort, que $f_n$ est premier pour tout $n\in \mathbb{N}$. On a le contre exemple suivant :

Exemple (Euler)

On a : $641\mid f_5$.

En effet :

$$f_5=2^{32}+1=2^{28}(5^4+2^4)-(5\cdot 2^7{)}^4+1=2^{28}\cdot 641-(6404-1)=641\left[2^{28}-\frac{6404-1}{641}\right]$$

Exemple

Soit $f_n$ le $n$-ème nombre de Fermat. Alors, on a :

1. $f_n=f_0\cdots f_{n-1}+2$ pour tout $n\in {\mathbb{N}}^{\ast }$
2. $\gcd (f_k,f_h)=1$ si $k\ne h$
3. $f_n$ se termine par 7 pour tout entier $n\ge 2$

➀ On a

$$f_k=2^{2^k}+1=(2^{2^{k-1}}{)}^2+1=(f_{k-1}-1{)}^2+1=f_{k-1}^2-2f_{k-1}+2$$

d'où, pour $k\ge 1$ :

$$f_k-2=f_{k-1}(f_{k-1}-2)(\ast )$$

En multipliant les relations $(\ast )$ pour $k=1,2,\dots ,n$ on déduit que :

$$f_n-2=f_0{f}_1\cdots f_{n-1}(f_0-2)$$

et la preuve est ainsi terminée.

➁ D'après (1) on a pour tout $n\ge 1$ :

$$\gcd (f_n,f_0)=\gcd (f_n,f_1)=\cdots =\gcd (f_n,f_{n-1})=1$$

Donc, $\gcd (f_k,f_h)=1$ pour tout $k\ne h$.

➂ Comme $f_1=5$ et $f_0\cdots f_{n-1}$ est impair, alors par (1) il s'ensuit que $f_n$ se termine par $5+2=7$ pour tout $n\ge 2$.

Exemple

Soit $n\in {\mathbb{N}}^{\ast }$. Montrer que : $f_n\mid 2^{f_n-2}$. En déduire que la réciproque du théorème de Fermat est fausse.

On a

$$2^{f_n-2}=2^{2^{2^n}-1}=2^{(2^{2^n}{)}^{2^n-n}}$$

Clairement, le nombre $2^{2^n-n}$ est pair ; et $x^{2m}-1$ est divisible par $x+1$ (car $2m$ est pair). Donc, $x+1$ divise $x^{2^{2^n-n}}-1$, et en posant $x=2^{2^n}$ on arrive au résultat demandé.

D'après ce qui précède on a : $2^{f_n}\equiv 2(\mathrm{mod}{f}_n)$. Ainsi, $2^{f_5}\equiv 2(\mathrm{mod}{f}_5)$ alors que $f_5$ n'est pas un nombre premier.

Exemple

Déterminer les nombres de Fermat qui peuvent s'écrire comme somme de deux nombres premiers.

On sait que tous les nombres de Fermat sont impairs. Si $f_n=p+q$ avec $p,q$ des nombres premiers ($p\le q$), alors $p=2$ et $q>2$. On obtient alors :

$$q=2^{2^n}-1=(2^{2^{n-1}}{)}^2-1=(2^{2^{n-1}}-1)(2^{2^{n-1}}+1)$$

D'où, $2^{2^{n-1}}-1$ doit être égal à 1, c'est-à-dire $n=1$. En conclusion, $f_1=2+3$ est le seul nombre de Fermat qui s'écrit comme somme de deux nombres premiers.

Exemple

Pour $n\ge 2$, montrer que les diviseurs premiers $p$ de $f_n$ sont de la forme $p=s\cdot 2^{n+2}+1$.

Comme $p\mid f_n$ alors :

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

Donc, en prenant le carré, on déduit que $2^{2^{n+1}}\equiv 1(\mathrm{mod}p)$, et alors ${\text{ord}}_p(2)\mid 2^{n+1}$. Puisque $2^{2^n}\not\equiv 1(\mathrm{mod}p)$, on a ${\text{ord}}_p(2)=2^{n+1}$, par suite $2^{n+1}\mid p-1$, d'où $p\equiv 1(\mathrm{mod}8)$ et $\left(\frac{2}{p}\right)=1$. Donc, 2 est un résidu quadratique modulo $p$ et il existe un certain $a$ avec $a^2\equiv 2(\mathrm{mod}p)$. Alors, ${\text{ord}}_p(a)=2^{n+2}$ et $2^{n+2}\mid p-1$, c'est-à-dire, $p=s\cdot 2^{n+2}+1$ pour un certain $s$.

Exemple

Montrer qu'un nombre de Fermat n'est jamais égal à un carré parfait ou à un cube parfait.

$\diamond$ On a : $f_n=k^2\iff 2^{2^n}+1=k^2\iff (k-1)(k+1)=2^{2^n}$. D'où, $k-1=2^a$ et $k+1=2^b$ avec $a<b$. On a :

$$2^{b-1}-2^{a-1}=1\Rightarrow a=1\Rightarrow k=3\Rightarrow 2^{2^n}=8\text{impossible}$$

$\diamond$ On a $f_0=3,f_1=5$ et $f_{n+1}=(f_n-1{)}^2+1$. On montre que $f_n\equiv 3(\mathrm{mod}7)$ ou $f_n\equiv 5(\mathrm{mod}7)$, mais $k^3\equiv 0,1,-1(\mathrm{mod}7)$. Donc, aucun nombre de Fermat n'est un cube parfait.

10.8 Nombres de Mersenne

Définition

On appelle nombres de Mersenne les entiers $M_n=2^n-1$ avec $n\in {\mathbb{N}}^{\ast }$.

• Si $n$ est un nombre composé, alors $M_n$ est lui aussi un nombre composé.
• Si $n=ab$ avec $a$ et $b$ des entiers plus grands que 1, alors $M_a\mid M_n$ et $M_b\mid M_n$.
• Il existe des entiers $n$ premiers pour lesquels $M_n$ est un nombre composé. Par exemple, $47\mid M_{23}$, $167\mid M_{83}$ et $263\mid M_{131}$.

Exemple

Soient $p$ un nombre premier impair et $q$ un diviseur premier de $M_p$. Alors, $q=2kp+1$ pour un certain $k\in {\mathbb{N}}^{\ast }$.

Comme $2^p\equiv 1(\mathrm{mod}q)$ et puisque $p$ est premier, alors $p$ est le plus entier strictement positif vérifiant cette propriété. D'après le théorème de Fermat on a $2^{q-1}\equiv 1(\mathrm{mod}q)$, et par suite $p\mid q-1$. Or $q-1$ est un entier pair, d'où $q-1=2kp$ avec $k\in {\mathbb{N}}^{\ast }$, et le problème est alors résolu.

Exemple

Soit $p$ un nombre premier de la forme $4k+3$. Alors :

$$2p+1\text{ est premier}\iff 2p+1\mid M_p$$

($\Rightarrow$) Si $q=2p+1$ est un nombre premier alors

$$\left(\frac{2}{q}\right)=(-1{)}^{\frac{q^2-1}{8}}=(-1{)}^{\frac{p(p+1)}{2}}=(-1{)}^{2(k+1)(4k+3)}=1$$

et par suite 2 est un résidu quadratique modulo $q$. En utilisant le critère d'Euler, il s'ensuit que $2^{\frac{q-1}{2}}\equiv 1(\mathrm{mod}q)$, c'est-à-dire $2^p\equiv 1(\mathrm{mod}q)$.

($\Leftarrow$) Si $q$ est un nombre composé, alors il admet un diviseur premier $q_1$ tel que $q_1\le \sqrt{q}$. D'après le théorème de Fermat on a : $2^{q_1-1}\equiv 1(\mathrm{mod}{q}_1)$. Or $2^p\equiv 1(\mathrm{mod}{q}_1)$ avec $p$ premier implique que $p$ est le plus petit entier strictement positif avec cette propriété. D'où, $p\mid q_1-1$ et par suite $q_1\ge p+1>\sqrt{p}$, contradiction avec le choix de $q_1$. Par conséquent, $q$ doit être un nombre premier, et la preuve est terminée.

Exemple

Montrer que pour $m$ et $n>1$ deux entiers naturels, l'équation $M_n=k^m$ n'a pas de solutions entières.

De la relation $2^n=k^m+1$ on déduit que $k$ est impair, $k\ge 3$.

$\diamond$ Si $m$ est pair, contradiction avec $2^n=M_8+2$.

$\diamond$ Si $m$ est impair, on a $2^n=(k+1)(k^{m-1}-k^{m-2}+\cdots +1)$. La contradiction vient du fait que $M=k^{m-1}-k^{m-2}+\cdots +1$ est impair et $M>1$.

10.9 Nombres parfaits. Nombres triangulaires

Définition (Nombre parfait)

Un entier $n\ge 2$ est dit parfait si la somme de ses diviseurs est égal à $2n$, c'est-à-dire $\sigma (n)=2n$ où $\sigma (n)$ est la somme des diviseurs positifs de $n$.

• Les nombres 6, 28 et 496 sont parfaits. On ne sait pas si des nombres parfaits impairs existent.

Définition (Nombre triangulaire)

Soit $n\in {\mathbb{N}}^{\ast }$, alors

$$t_n=1+2+\cdots +n=\frac{n(n+1)}{2}=\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$$

est appelé nombre triangulaire.

Exemple (Euclide et Euler)

Montrer que si le nombre de Mersenne $M_k$ est premier, alors $n=2^{k-1}{M}_k$ est un nombre parfait.

Réciproquement, si un entier naturel strictement positif et pair $n$ est un nombre parfait, alors $n=2^{k-1}{M}_k$ pour un certain $k\in {\mathbb{N}}^{\ast }$ pour lequel $M_k$ est premier.

$\diamond$ Comme $\gcd (2^{k-1},2^k-1)=1$ et puisque $\sigma$ est une fonction multiplicative (facile à vérifier) alors

$$\sigma (n)=\sigma (2^{k-1})\sigma (2^k-1)=(2^k-1)\cdot 2^k=2n$$

$\diamond$ Soit $n=2^{t}u$ avec $t\ge 1$ et $u$ impair. Comme $n$ est parfait alors $\sigma (n)=2n$ et par suite $\sigma (2^{t}u)=2^{t+1}u$. Comme $\sigma$ est multiplicative alors :

$$\sigma (2^{t}u)=\sigma (2^t)\sigma (u)=(2^{t+1}-1)\sigma (u)$$

C'est équivalent à :

$$(2^{t+1}-1)\sigma (u)=2^{t+1}u$$

Comme $\gcd (2^{t+1}-1,2^{t+1})=1$, il s'ensuit que $2^{t+1}\mid \sigma (u)$, d'où $\sigma (u)=2^{t+1}v$ pour un certain $v\in {\mathbb{N}}^{\ast }$.

On obtient $u=(2^{t+1}-1)v$. Montrons maintenant que $v=1$. Supposons, par l'absurde, que $v>1$, alors :

$$\sigma (u)\ge 1+v+2^{t+1}-1+v(2^{t+1}-1)=(v+1)2^{t+1}>v\cdot 2^{t+1}=\sigma (u)$$

contradiction. Par conséquent, $v=1$, alors $u=2^{t+1}-1=M_{t+1}$ et $\sigma (u)=2^{t+1}$. Si $M_{t+1}$ n'est pas premier, alors $\sigma (u)>2^{t+1}$, impossible. Finalement, $n=2^{k-1}{M}_k$ où $k=t+1$.

Exemple

Montrer que tout nombre parfait pair est triangulaire.

D'après l'exemple précédent on a : $n=2^{k-1}{M}_k=\frac{2^k}{2}(2^k-1)=\frac{m(m+1)}{2}$, où $m=2^k-1$. La preuve est terminée.

Exemple

Montrer que si $n$ est un nombre parfait pair, alors $8n+1$ est un carré parfait.

D'après l'exemple précédent $n$ est un nombre triangulaire : $n=\frac{m(m+1)}{2}$ avec $m\in {\mathbb{N}}^{\ast }$. D'où :

$$8n+1=4m(m+1)+1=(2m+1{)}^2$$

Exemple

Montrer que si $k$ est un entier strictement positif impair, alors $2^{k-1}{M}_k$ peut s'écrire comme la somme des cubes des $2^{\frac{k-1}{2}}$ premiers entiers strictement positifs et impairs.

Il est facile de vérifier que $\sum _{i=1}^n(2i-1{)}^3=n^2(2n^2-1)$. Alors, avec $n=2^{\frac{k-1}{2}}$, le membre de droite devient $2^{k-1}(2^k-1)=2^{k-1}{M}_k$.

remarque : tout nombre parfait vérifie la propriété de l'exemple.

Exemple

Montrer que si $n$ est un nombre parfait, alors :

$$\sum _{p\mid n}\frac{1}{p+1}<\ln 2<\sum _{p\mid n}\frac{1}{p-1}$$

Soit $n=\prod _{i=1}^n{p}_i^{{\alpha }_i}$ la décomposition de $n$ en produit de facteurs premiers, alors comme $n$ est parfait on a $\sigma (n)=2n$. Par suite

$$\frac{\sigma (n)}{n}=2=\prod _{i=1}^k\left(1+\frac{1}{p_i}+\frac{1}{p_i^2}+\cdots +\frac{1}{p_i^{{\alpha }_i}}\right)<\prod _{i=1}^k\left(1+\frac{1}{p_i-1}\right)$$

et $\ln (1+x)<x$.

On a

$$2\ge \prod _{p\mid n}\left(1+\frac{1}{p}\right)\text{et}\ln (1+x)>\frac{x}{1+x}$$

En conclusion, $\sum _{p\mid n}\frac{1}{p+1}<\ln 2<\sum _{p\mid n}\frac{1}{p-1}$.

Exemple

Déterminer les entiers $m$ et $n$ pour lesquels $t_{n+m}-t_n$ est un nombre premier.

Les relations $t_{n+m}-t_n=\frac{m(2n+m+1)}{2}=p$ donnent immédiatement $m=1,n=p-1$ ou $m=2,n=\frac{p-3}{2}$ ; $p$ nombre premier impair dans les deux cas. En conclusion, les solutions sont

$$(n,m)=(p-1,1)\text{et}(n,m)=\left(\frac{p-3}{2},2\right)$$

où $p$ est un nombre premier impair.

Exemple

Montrer qu'un nombre $N$ qui s'écrit en base 9 qu'avec des chiffres 1 est un nombre triangulaire.

On a

$$N=9^{k-1}+9^{k-2}+\cdots +9+1=\frac{9^k-1}{8}$$

En notant $n=\frac{3^k-1}{2}$, alors on a : $N=t_n$.

Exemple

Montrer que le nombre $N=\underset{n}{\underbrace{22\cdots 2}}\underset{n}{\underbrace{11\cdots 1}}$ est triangulaire.

On a

$$N=2\cdot 10^n(10^n-1+10^n-2+\cdots +1)+(10^n-1+10^n-2+\cdots +1)=\frac{(10^n-1)(2\cdot 10^n+1)}{9}=t_k$$

avec $k=\frac{2(10^n-1)}{3}$.

Exemple

Déterminer les nombres de Fermat qui sont triangulaires.

On a

$$2^{2^n}+1=\frac{m(m+1)}{2}\iff 2^{2^n}+1=(m-1)(m+2)\iff m-1=1\text{ et }n=0$$

Le seul nombre de Fermat qui est triangulaire est $2^{2^0}+1=3$.

Exemple

Montrer qu'il existe une infinité d'entiers $n\in \mathbb{N}$ pour lesquels le nombre $2^n-1$ n'est pas triangulaire.

On prend $n=4t+3$, $t\in \mathbb{N}$. Supposons que $2^{4t+3}-1=\frac{x(x+1)}{2}$, $x\in \mathbb{N}$. Alors :

$$(2x+1{)}^2=2^{4t+6}-7\equiv 2^6-7=57\equiv 7(\mathrm{mod}10)$$

On obtient donc une contradiction.

10.10 Plus grand et plus petit élément

Dans beaucoup de problèmes, il est assez souvent utile de considérer le plus petit ou le plus grand élément vérifiant une certaine propriété. Ce choix donne lieu, souvent, à la construction d'autres éléments ou à une contradiction.

10.12. Principe des tiroirs

Lorsque $S$ varie, il y a moins de $(1000\cdot 10^{100})(1000\cdot 10^{200})=10^{306}$ valeurs de $\left(\sum _{x\in S}x,\sum _{x\in S}{x}^2\right)$.

Comme $\sum _{k=0}^{2000}\left(\genfrac{}{}{0ex}{}{2000}{k}\right)=2^{2000}$ et $\left(\genfrac{}{}{0ex}{}{2000}{1000}\right)$ est le plus grand terme de la somme, alors $\left(\genfrac{}{}{0ex}{}{2000}{1000}\right)>\frac{2^{2000}}{2001}$.

Il y a : $\left(\genfrac{}{}{0ex}{}{2000}{1000}\right)>\frac{2^{2000}}{2001}>\frac{10^{600}}{2001}>10^{306}$ sous-ensembles de cardinal 1000. D'après le principe des tiroirs, il existe deux sous-ensembles $C$ et $D$ de cardinal 1000 tels que

$$\sum _{x\in C}{x}^2=\sum _{x\in D}{x}^2\text{et}\sum _{x\in C}x=\sum _{x\in D}x.$$

En enlevant les éléments en commun à $C$ et $D$, on déduit l'existence de deux sous-ensembles $A$ et $B$ avec les propriétés requises.

Exemple (Roumanie)

Quel est le plus grand $n\in {\mathbb{N}}^{\ast }$ pour lequel il existe $n$ entiers naturels $x_1,x_2,\dots ,x_n$, non tous nuls, tels que pour toute suite ${\epsilon }_1,{\epsilon }_2,\dots ,{\epsilon }_n$, éléments de $\{-1,0,1\}$ et non tous nuls, on ait : $n^3\nmid ({\epsilon }_1{x}_1+{\epsilon }_2{x}_2+\cdots +{\epsilon }_n{x}_n)$.

Le résultat est vrai pour $n=9$ en choisissant $2^0,2^1,2^2,\dots ,2^8$ puisque dans ce cas :

$$|{\epsilon }_1{2}^0+{\epsilon }_2{2}^1+\cdots +{\epsilon }_9{2}^8|\le 2^0+2^1+\cdots +2^8<9^3.$$

Cependant, si $n\ge 10$, alors $2^{10}>10^3$, donc par le principe des tiroirs il existe deux sous-ensembles $A$ et $B$ de $\{x_1,x_2,\dots ,x_{10}\}$ dont les sommes sont congrues modulo $10^3$. Soit

$${\epsilon }_i=\{\begin{array}{ll}+1& \text{si }{x}_i\in A\text{ et }{x}_i\notin B\\ -1& \text{si }{x}_i\in B\text{ et }{x}_i\notin A\\ 0& \text{sinon.}\end{array}$$

Alors : $n^3\mid ({\epsilon }_1{x}_1+{\epsilon }_2{x}_2+\cdots +{\epsilon }_n{x}_n)$. En conclusion, $n=9$ est le plus petit entier $n\in {\mathbb{N}}^{\ast }$ tel qu'il existe $n$ entiers naturels $x_1,x_2,\dots ,x_n$, non tous nuls, tels que pour toute suite ${\epsilon }_1,{\epsilon }_2,\dots ,{\epsilon }_n$, éléments de $\{-1,0,1\}$ et non tous nuls, on ait : $n^3\nmid ({\epsilon }_1{x}_1+{\epsilon }_2{x}_2+\cdots +{\epsilon }_n{x}_n)$.

Exemple

Soit $(x_n{)}_{n\ge 1}$ la suite définie par $x_1=x_2=x_3=1$ et pour tout $n\ge 1$ : $x_{n+3}=x_n+x_{n+1}{x}_{n+2}$. Montrer que pour tout $m\in {\mathbb{N}}^{\ast }$, il existe $k\in {\mathbb{N}}^{\ast }$, avec $k\le m^3$, tel que : $m\mid x_k$.

Soit $r_t$ le reste de la division de $x_t$ par $m$ pour $t=0,1,\dots ,m^3+2$. Considérons les triplets $(r_0,r_1,r_2),(r_1,r_2,r_3),\dots ,(r_{m^3},r_{m^3+1},r_{m^3+2})$. Comme $r_t$ donne lieu à $m$ valeurs, alors par le principe des tiroirs il existe au moins deux triplets qui sont égaux. Soit $p$ le plus petit nombre tel que le triplet $(r_p,r_{p+1},r_{p+2})$ est égal à un autre triplet $(r_q,r_{q+1},r_{q+2})$, $p<q\le m^3$. On se propose de montrer que $p=0$. Supposons, par l'absurde, que $p\ge 1$, alors par hypothèses on a :

$$r_p\equiv r_{p-1}+r_p{r}_{p+1}(\mathrm{mod}m)\text{et}{r}_{q+2}\equiv r_{q-1}+r_q{r}_{q+1}(\mathrm{mod}m).$$

Comme $r_p=r_q$, $r_{p+1}=r_{q+1}$ et $r_{p+2}=r_{q+2}$, il s'ensuit que $r_{p-1}=r_{q-1}$, d'où $(r_{p-1},r_p,r_{p+1})=(r_{q-1},r_q,r_{q+1})$, ce qui est en contradiction avec la minimalité de $p$. Donc $p=0$, par suite $r_q=r_0=0$, et en conclusion $x_q\equiv 0(\mathrm{mod}m)$.

10.13 Principe d'inclusion-exclusion

Le lecteur est invité à consulter le « Tome 3 : Combinatoire 1 » de cette série de livre pour la définition, et les principales propriétés du principe d'inclusion-exclusion. On se contente ici de donner des applications de ce principe à la résolution de problèmes d'arithmétique.

Exemple

Combien y a-t-il d'entiers $n\in [1,1000]$ qui sont divisibles par 2, ou par 3, ou par 5 ?

Considérons les ensembles

$$S_1=\{2m:m\in [1,500]\},S_2=\{3n:n\in [1,333]\},S_3=\{5p:p\in [1,200]\}.$$

Alors, on a :

$$S_1\cap S_2=\{6q:q\in [1,166]\},S_1\cap S_3=\{10r:r\in [1,100]\},$$ $$S_2\cap S_3=\{15s:s\in [1,66]\},S_1\cap S_2\cap S_3=\{30u:u\in [1,33]\}.$$

D'après la formule d'inclusion-exclusion on déduit que :

$$|S_1\cup S_2\cup S_3|=|S_1|+|S_2|+|S_3|-|S_1\cap S_2|-|S_1\cap S_3|-|S_2\cap S_3|+|S_1\cap S_2\cap S_3|$$ $$=500+333+200-166-100-66+33=734.$$

Exemple

Combien y a-t-il d'entiers $n\in [1,120]$ qui ne sont pas divisibles par 2, 3 et 5 ?

Considérons les ensembles $S_1=\{2m:m\in [1,60]\}$, $S_2=\{3n:n\in [1,40]\}$, $S_3=\{5p:p\in [1,24]\}$. Alors, on a :

$$S_1\cap S_2=\{6q:q\in [1,20]\},S_1\cap S_3=\{10r:r\in [1,12]\},$$ $$S_2\cap S_3=\{15s:s\in [1,8]\},S_1\cap S_2\cap S_3=\{30u:u\in [1,4]\}.$$