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.

3.2 Exemples

Méthode

Pour montrer qu'un entier naturel est composé, revenir à la définition : faire apparaître cet entier comme produit de deux entiers différents de 1.

Exemple

Montrer que les entiers suivants sont composés :

1. $n^4-n^2+16$ pour $n\in \mathbb{Z}$.
2. $4n^3+6n^2+4n+1$ pour $n\in {\mathbb{N}}^{\ast }$.
3. $2^{4n+2}+1$ pour $n\in {\mathbb{N}}^{\ast }$.

① $n^4-n^2+16=(n^2+4{)}^2-9n^2=(n^2-3n+4)(n^2+3n+4)$, et $n^2-3n+4,n^2+3n+4$ sont pairs car $n^2-n\equiv 0(\mathrm{mod}3)$.

② $4n^3+6n^2+4n+1=(2n+1)(2n^2+2n+1)$, et $1<2n+1<2n^2+2n+1$.

③ $2^{4n+2}+1=(2^{2n+1}+1{)}^2-2\cdot 2^{2n+1}=(2^{2n+1}+2^{n+1}+1)(2^{2n+1}-2^{n+1}+1)$, et $2^{2n+1}+2^{n+1}+1>1,2^{2n+1}-2^{n+1}+1>1$ car $n\ge 1$.

Exemple

Soit $n\in \mathbb{N}\setminus \{0,1\}$. Montrer que $5^n-3^n$ est composé.

Il suffit de remarquer que $5^n-3^n$ est pair et $\ne 2$.

Exemple

Soit $(a,b,c,d)\in ({\mathbb{N}}^{\ast }{)}^4$ tel que $ab=cd$. Montrer que, pour tout $n\in {\mathbb{N}}^{\ast }$, $a^n+b^n+c^n+d^n$ est un nombre composé.

Si $\delta =a\wedge c$, alors il existe $(a^{\prime },c^{\prime })\in ({\mathbb{N}}^{\ast }{)}^2$ tel que $a=\delta a^{\prime },c=\delta c^{\prime },a^{\prime }\wedge c^{\prime }=1$. Comme $ab=cd$, alors $a^{\prime }b=c^{\prime }d$. Puisque $a^{\prime }|c^{\prime }d$ et $a^{\prime }\wedge c^{\prime }=1$, alors le théorème de Gauss montre que $a^{\prime }|d$, il existe ainsi $D\in {\mathbb{N}}^{\ast }$ tel que $d=a^{\prime }D$. On déduit que $b=c^{\prime }D$. On a alors : $a=\delta a^{\prime },b=D{c}^{\prime },c=\delta c^{\prime }$ et $d=D{a}^{\prime }$.

D'où :

$$a^n+b^n+c^n+d^n=({\delta }^n+D^n)((a^{\prime }{)}^n+(c^{\prime }{)}^n)\text{ et }{\delta }^n+D^n\ge 2,(a^{\prime }{)}^n+(c^{\prime }{)}^n\ge 2.$$

On conclut que $a^n+b^n+c^n+d^n$ est un nombre composé.

Exemple

Soit $(a,b)\in {\mathbb{N}}^2$ tel que $\frac{a^3+b^3}{2}$ soit un nombre premier. Montrer que $a=b=1$.

⋄ Si $a$ et $b$ sont pairs : alors $4$ divise $\frac{a^3+b^3}{2}$, contradiction.

⋄ Si $a$ est pair et $b$ impair (ou si $a$ est impair, et $b$ est pair) : alors $\frac{a^3+b^3}{2}\notin \mathbb{N}$.

Par suite, $a$ et $b$ sont tous les deux impairs. On a :

$$\frac{a^3+b^3}{2}=\frac{a+b}{2}\cdot (a^2-ab+b^2),\text{ avec }\frac{a+b}{2}\in \mathbb{N},a^2-ab+b^2\in \mathbb{N}.$$

Puisque $\frac{a^3+b^3}{2}$ est un nombre premier alors on déduit que $\frac{a+b}{2}=1$ ou $a^2-ab+b^2=1$.

• Si $a^2-ab+b^2=1$, alors $(2a-b{)}^2+3b^2=4$, d'où $b=|2a-b|=1$, puis $a=b=1$.
• Si $\frac{a+b}{2}=1$, alors $a=b=1$.

Méthode

Pour montrer qu'un entier naturel est composé, revenir à la définition : faire apparaître cet entier comme produit de deux entiers différents de 1. À cet effet, on pourra dans certains cas, utiliser des polynômes comme dans les exemples ci-dessous.

Exemple

Soit $n\in {\mathbb{N}}^{\ast }$ tel qu'il existe $p$ premier avec $p\ge 5$ et $p|n$. Montrer que $4^n-2^n+1$ est composé.

Par hypothèse, il existe $m\in {\mathbb{N}}^{\ast }$ tel que $n=mp$. On a : $4^n-2^n+1=A_p(2^m)$ où $A_p=X^{2p}-X^p+1\in \mathbb{Z}[X]$. En notant $A_1=X^2-X+1\in \mathbb{Z}[X]$, on montre que $A_1$ divise $A_p$ dans $\mathbb{C}[X]$. En effet :

$$A_1=(X+j)(X+j^2),A_p(j)=A_p(j^2)=j^{2p}+j^p+1=\frac{j^{3p}-1}{j^p-1}=0,A_p(j^2)=0.$$

Il en résulte que $A_1|A_p$ dans $\mathbb{Z}[X]$, puis que $A_1(2^m)|A_p(2^m)$ dans $\mathbb{Z}$. Enfin, il est facile de voir que $1<A_1(2^m)<A_p(2^m)$.

Exemple

Montrer que, si $n\in {\mathbb{N}}^{\ast }$ est tel que $4^n+2^n+1$ soit un nombre premier, alors $n$ est une puissance de $3$.

Notons, pour tout $\beta \in {\mathbb{N}}^{\ast }$, ${\beta }_k=4^k+2^k+1$ et $B_k=X^{2k}+X^k+1\in \mathbb{Z}[X]$, de sorte que ${\beta }_k=B_k(2)$.

L'étude du cas $n=1$ est facile à faire. On suppose $n\ge 2$ et ${\beta }_n$ premier. Il existe $(k,m)\in {\mathbb{N}}^2$ tel que :

$$\{\begin{array}{l}n=3^{k}m\\ m\not\equiv 0(\mathrm{mod}3)\end{array}(k\text{ est la 3-valuation de }n).$$

Ainsi, $B_n(X)=X^{3^k\cdot 2m}+X^{3^{k}m}+1=B_m(X^{3^k})$.

Supposons que $m\ge 2$. Comme $m\not\equiv 0(\mathrm{mod}3)$, on a :

$$B_m(j)=B_m(j^2)=j^{2m}+j^m+1=\frac{j^{3m}-1}{j^m-1}=0\text{donc }{B}_1|B_m\text{ dans }\mathbb{C}[X].$$

Puisque $(B_1,B_m)\in (\mathbb{Z}[X]{)}^2$, il en résulte que $B_1|B_m$ dans $\mathbb{Z}[X]$, puis $B_1(2^{3^k})|B_m(2^{3^k})=B_n(2)={\beta }_n$ dans $\mathbb{Z}$. Comme $1<B_1(2^{3^k})<{\beta }_n$, ${\beta }_n$ est composé, contradiction. En conclusion, $m=1$, $n=3^k$.

Méthode

Pour montrer des congruences, on peut quelquefois utiliser un raisonnement par récurrence, la récurrence ne se faisant pas, en général, sur le module de la congruence.

Exemple

Soient $p$ premier et $\ge 3$, $n\in \mathbb{N}$. Montrer que :

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

On fait une récurrence sur $n$. Le cas $n=0$ est trivial, et $n=1$ est facile en développant $(1+p{)}^p$ par la formule du binôme de Newton. Supposons que le résultat est vrai pour $n$, il existe $m\in \mathbb{N}$ tel que $(1+p{)}^{p^n}=1+p^{n+1}+m{p}^{n+2}$, d'où :

$$(1+p{)}^{p^{n+1}}={\left[(1+p{)}^{p^n}\right]}^p=(1+p^{n+1}+m{p}^{n+2}{)}^p=1+p(p^{n+1}+m{p}^{n+2})+\sum _{k=2}^p\left(\genfrac{}{}{0ex}{}{p}{k}\right)p^{(n+1)k}(1+mp{)}^k.$$

Puisque, pour tout $k\in [[2,p]]$, $(n+1)k\ge n+3$, on conclut que : $(1+p{)}^{p^{n+1}}\equiv 1+p^{n+2}(\mathrm{mod}{p}^{n+3})$.

Méthode

Pour montrer qu'un nombre premier divise un entier, on peut utiliser le théorème de Gauss.

Exemple

Soit $p$ un nombre premier. Montrer que, pour tout $k\in [[1,p-1]]$, $p|(\genfrac{}{}{0ex}{}{p}{k})$.

Généralisation : soient $p$ un nombre premier, $n\in \mathbb{N}\setminus \{0,1\}$, et $(i_1,\dots ,i_n)\in [[0,p-1]]$ tel que $i_1+\cdots +i_n=p$. Montrer que $\frac{p!}{i_1!\cdots i_n!}$ est un entier divisible par $p$.

Comme $p!=k!(p-k)!(\genfrac{}{}{0ex}{}{p}{k})$, alors $p$ divise $k!(p-k)!(\genfrac{}{}{0ex}{}{p}{k})$. On a, pour tout $k\in [[1,p-1]]$, $p\wedge k=p\wedge (p-k)=1$, donc $p\wedge (k!(p-k)!)=1$. Le théorème de Gauss permet de conclure que $p|(\genfrac{}{}{0ex}{}{p}{k})$.

Pour la généralisation, $\frac{p!}{i_1!\cdots i_n!}$ est un entier car c'est le coefficient de $X_1^{i_1}\cdots X_n^{i_n}$ dans le développement de $(X_1+\cdots +X_n{)}^p$ par la formule du multinôme de Newton. La suite de la preuve est identique à celle présentée ci-haut.

Méthode

Dans les questions de divisibilité ou de pgcd et ppcm, il peut être utile d'envisager les décompositions primaires des entiers qui interviennent.

Exemple

Soient $a,b,c,k\in {\mathbb{N}}^{\ast }$ tels que $ab=c^k$ et $a\wedge b=1$. Montrer qu'il existe $(\alpha ,\beta )\in ({\mathbb{N}}^{\ast }{)}^2$ tel que $a={\alpha }^k$ et $b={\beta }^k$.

Considérons les décompositions primaires $a=\prod _{i=1}^N{p}_i^{r_i},b=\prod _{i=1}^N{p}_i^{s_i}$, où $N\in {\mathbb{N}}^{\ast }$, $p_1,\dots ,p_N$ sont premiers deux à deux distincts, et $r_1,\dots ,r_N,s_1,\dots ,s_N\in \mathbb{N}$. Puisque $a\wedge b=1$, alors $r_i=0$ ou $s_i=0$ pour tout $i\in [[1,N]]$. Or, $c^k=\prod _{i=1}^N{p}_i^{r_i+s_i}$, d'où, par unicité de la décomposition primaire de $c^k$ : ($k|r_i$ et $k|s_i$) pour tout $i\in [[1,N]]$. Il existe alors ${\alpha }_1,\dots ,{\alpha }_N,{\beta }_1,\dots ,{\beta }_N\in \mathbb{N}$ tels que $r_i=k{\alpha }_i$ et $s_i=k{\beta }_i$ pour tout $i\in [[1,N]]$. En notant $\alpha =\prod _{i=1}^N{p}_i^{{\alpha }_i}$ et $\beta =\prod _{i=1}^N{p}_i^{{\beta }_i}$, on a : $a={\alpha }^k$ et $b={\beta }^k$.

Exemple

Pour tout $(a,b,c)\in ({\mathbb{Z}}^{\ast }{)}^3$, montrer que :

$$(a\vee b)\cdot (a\vee c)\cdot (b\vee c)\cdot (a\wedge b\wedge c)=(a\vee b\vee c)\cdot |abc|.$$

Notons $A=(a\vee b)\cdot (a\vee c)\cdot (b\vee c)\cdot (a\wedge b\wedge c)$ et $B=(a\vee b\vee c)\cdot |abc|$. Soient $p$ un nombre premier, et $\alpha ,\beta ,\gamma$ les $p$-valuations de $a,b,c$ respectivement. Comme $a,b,c$ ont des rôles symétriques on peut supposer que $\alpha \le \beta \le \gamma$. On a :

$$v_p(A)=v_p(a\vee b)+v_p(a\vee c)+v_p(b\vee c)+v_p(a\wedge b\wedge c)=\max (\alpha ,\beta )+\max (\alpha ,\gamma )+\max (\beta ,\gamma )+\min (\alpha ,\beta ,\gamma )=\beta +\gamma +\gamma +\alpha ,$$

$$v_p(B)=v_p(a\vee b\vee c)+v_p(a)+v_p(b)+v_p(c)=\max (\alpha ,\beta ,\gamma )+\alpha +\beta +\gamma =\gamma +\alpha +\beta +\gamma .$$

Par suite, $v_p(A)=v_p(B)$ pour tout $p\in P$, d'où $A=B$.

Méthode

À partir de la décomposition primaire d'un entier $n\ge 2$, on peut exprimer le nombre $d(n)$ des diviseurs $\ge 1$ de $n$ et la somme $\sigma (n)$ de ces diviseurs, ainsi que, pour tout $k\in {\mathbb{N}}^{\ast }$, la somme ${\sigma }_k(n)$ des puissances $k$-èmes des diviseurs de $n$.

Exemple

Pour tout $n\in \mathbb{N}\setminus \{0,1\}$, on note $d(n)$ le nombre de diviseurs $\ge 1$ de $n$, et $\sigma (n)$ la somme des diviseurs $\ge 1$ de $n$. Montrer que, si la décomposition primaire de $n$ est $n=\prod _{i=1}^N{p}_i^{r_i}$, alors :

$$d(n)=\prod _{i=1}^N(r_i+1)\text{et}\sigma (n)=\prod _{i=1}^N\frac{p_i^{r_i+1}-1}{p_i-1}.$$

Remarquons que l'application $(s_1,\dots ,s_N)\mapsto \prod _{i=1}^N{p}_i^{s_i}$ est une bijection de $\prod _{i=1}^N\{0,\dots ,r_i\}$ sur l'ensemble des diviseurs $\ge 1$ de $n$. D'où :

$$d(n)=\text{Card}\left(\prod _{i=1}^N\{0,\dots ,r_i\}\right)=\prod _{i=1}^N(r_i+1),$$

$$\sigma (n)=\sum _{1\le i\le N,0\le s_i\le r_i}\left(\prod _{i=1}^N{p}_i^{s_i}\right)=\prod _{i=1}^N\left(\sum _{k=0}^{r_i}{p}_i^k\right)=\prod _{i=1}^N\frac{p_i^{r_i+1}-1}{p_i-1}.$$

Exemple

Soit $k\in {\mathbb{N}}^{\ast }$. Pour tout $n\in {\mathbb{N}}^{\ast }$, on note ${\sigma }_k(n)$ la somme des puissances $k$-èmes des diviseurs $\ge 1$ de $n$ : ${\sigma }_k(n)=\sum _{1\le d\le n,d|n}{d}^k$. Montrer que, si la décomposition primaire de $n$ est $n=\prod _{i=1}^N{p}_i^{r_i}$, alors :

$${\sigma }_k(n)=\prod _{i=1}^N\frac{p_i^{k(r_i+1)}-1}{p_i^k-1}.$$

En déduire que ${\sigma }_k$ est une fonction arithmétique multiplicative, c'est-à-dire :

$$\forall (a,b)\in ({\mathbb{N}}^{\ast }{)}^2,a\wedge b=1\Rightarrow {\sigma }_k(ab)={\sigma }_k(a){\sigma }_k(b).$$

Même raisonnement que dans l'exemple ci-dessus.

Montrons que ${\sigma }_k$ est une fonction multiplicative. Soit $(a,b)\in ({\mathbb{N}}^{\ast }{)}^2$ tel que $a\wedge b=1$. Considérons les décompositions primaires $a=\prod _{i=1}^N{p}_i^{r_i},b=\prod _{i=1}^N{p}_i^{s_i}$. Comme $a\wedge b=1$, alors $r_i=0$ ou $s_i=0$ pour tout $i\in [[1,N]]$. Soit $i\in [[1,N]]$, supposons par exemple $s_i=0$, alors :

$$\frac{p_i^{k(r_i+s_i+1)}-1}{p_i^k-1}=\frac{p_i^{k(r_i+1)}-1}{p_i^k-1}\cdot \frac{p_i^{k(s_i+1)}-1}{p_i^k-1}.$$

On conclut que ${\sigma }_k(ab)={\sigma }_k(a){\sigma }_k(b)$.

Astuces et Techniques de Divisibilité

Technique 1 : Décomposition avec Produits Égaux

Si les entiers strictement positifs $a,b,c$ et $d$ vérifient $ab=cd$, alors on peut écrire $a=mu$, $b=nv$, $c=nu$ et $d=mv$. Ces relations sont très utiles dans la résolution de problèmes.

Technique 2 : Utilisation de la Primitivité

Comme $ab=cd$, alors $b=\frac{cd}{a}$, par suite : $$a+b+c+d=a+\frac{cd}{a}+c+d=\frac{(a+c)(a+d)}{a}.$$

Puisque $a+b+c+d$ est un entier, alors $\frac{(a+c)(a+d)}{a}$ l'est aussi. S'il était égal à un nombre premier $p$, alors on aurait : $$(a+c)(a+d)=ap.(1)$$

Le nombre premier $p$ divise $(a+c)(a+d)$, donc $p\mid (a+c)$ ou $p\mid (a+d)$. Supposons que $p\mid (a+c)$, alors $a+c\ge p$. En combinant avec $(1)$ on déduit que $a+d\le a$, ce qui est impossible pour $d\ge 1$.

Exemple : Équations et Carrés Parfaits

Énoncé : Montrer que si les entiers strictement positifs $a$ et $b$ vérifient $2a^2+a=3b^2+b$, alors $a-b$ et $2a+2b+1$ sont des carrés parfaits.

L'équation $2a^2+a=3b^2+b$ est équivalente à : $$(a-b)(2a+2b+1)=b^2.(1)$$

L'idée de la preuve est de montrer que $a-b$ et $2a+2b+1$ sont premiers entre eux. Posons $d=(a-b)\wedge (2a+2b+1)$. Si $d>1$, alors il existe un diviseur premier $p$ de $d$. D'après $(1)$ on obtient $p\mid b^2$, or comme $p$ est premier alors $p\mid b$. La relation $p\mid (2a+2b+1)$ implique que $p\mid 1$, ce qui est impossible. Donc, $d=1$, et de $(1)$ on déduit que $a-b$ et $2a+2b+1$ sont tous les deux des carrés parfaits.

Exemple : Divisibilité et Puissances

Énoncé : Soient $n$, $a$ et $b$ des entiers naturels avec $a\ne b$. Montrer que si $n\mid (a^n-b^n)$ alors $n\mid \frac{a^n-b^n}{a-b}$.

Soient $p$ un nombre premier, et $p^{\alpha }$ la plus grande puissance de $p$ divisant $n$. On se propose de montrer que $p^{\alpha }\mid \frac{a^n-b^n}{a-b}$, ce qui donne le résultat demandé. Posons $t=a-b$.

Cas 1 : Si $p\nmid t$, alors $p^{\alpha }\wedge t=1$. Puisque $n\mid (a^n-b^n)$, on a : $p^{\alpha }\mid (a^n-b^n)$. Or, $a^n-b^n=t\cdot \frac{a^n-b^n}{t}$, d'où : $$p^{\alpha }\text{ divise }\frac{a^n-b^n}{t}.$$

Cas 2 : Si $p\mid t$, alors d'après le théorème binomial de Newton on a : $$\frac{a^n-b^n}{t}=\frac{(b+t{)}^n-b^n}{t}=\sum _{i=1}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)b^{n-i}{t}^{i-1}.(1)$$

Soit $p^{\beta }$ la plus grande puissance de $p$ divisant $i$ (où $i\ge 1$), alors $2\beta \le p^{\beta }\le i$, d'où $\beta \le i-1$. Par conséquent, la puissance de $p$ contenu dans $\left(\genfrac{}{}{0ex}{}{n}{i}\right)t^{i-1}=\left(\genfrac{}{}{0ex}{}{n}{i}\right)\left(\genfrac{}{}{0ex}{}{n-1}{i-1}\right)t^{i-1}$ est égale au moins à $\alpha -\beta +(i-1)\ge \alpha$, et chaque terme du membre de droite dans $(1)$ est divisible par $p^{\alpha }$. Donc : $$p^{\alpha }\text{ divise }\frac{a^n-b^n}{t}.$$

Remarque sur la Décomposition Primaire

Pour montrer que $b\mid a$, on peut utiliser la décomposition primaire $b=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$ de $b$. Le problème se réduit alors à montrer que $p_i^{{\alpha }_i}\mid a$ pour $i=1,2,\dots ,k$. La question est alors plus simple grâce aux propriétés des nombres premiers.