Démonstrations capes - Arithmétique

Prouvons d'abord l'unicité. Si $a=bq+r=bq'+r'$, avec $0\leq r<b$ et $0\leq r'<b$, alors en effectuant la différence, on trouve $0=b(q-q')+r-r'$, c'est-à-dire $$r-r'=b(q'-q).$$ Mais, puisque $0\leq r<b$ et $-b<-r'\leq 0$, on a $-b<r-r'<b$ et donc $|r-r'|<b$. Si $q'$ était différent de $q$, alors $|b(q'-q)|$ serait supérieur ou égal à $b$, une contradiction. Donc $r=r'$ et $b=b'$.

Prouvons maintenant l'existence. Si $a$ est un multiple de $b$, le résultat est évident, avec $r=0$. Sinon, puisque $(a+1)b>a$, alors $a$ est compris entre deux multiples consécutifs de $b$. Autrement dit, il existe $q\in\mathbb N$ tel que $qb<a<(q+1)b$. Posons alors $r=a-qb$. Il vient $0<r<b$, et donc le couple $(q,r)$ convient.

L'unicité se prouve exactement de la même façon que dans $\mathbb N$. Prouvons maintenant l'existence. On l'a déjà fait si $a\geq 0$ et $b>0$. Supposons ensuite $a<0$ et $b>0$. Si $a$ est un multiple de $b$, le résultat est évident. Sinon, effectuons la division euclidienne de $-a$ par $b$. Il existe un couple d'entiers $(q_1,r_1)$ avec $0<r_1<b$ tels que $-a=bq_1+r_1$. Prenant l'opposé de cette équation, on trouve $a=b(-q_1)-r_1$. Malheureusement, $-r_1$ n'est pas élément de $[0,b[$, mais il le devient si on ajoute $b$. Concrètement, on a donc $$a=b(-q_1)+r_1+b-b=b(-q_1-1)+r_1+b.$$ On pose alors $q=-q_1-1$ et $r=r_1+b$. Puisque $-b<r_1<0$, on a bien $0<r_1+b=r<b$.

On traite enfin le cas $a<0$ et $b<0$. Comme précédemment, si $a$ est un multiple de $b$, il n'y a rien à faire. Sinon, on effectue la division euclidienne de $-a$ par $-b$ : il existe un couple d'entiers $(q_1,r_1)$ tels que $-a=-bq_1+r_1$ avec $0<r_1<b$. Prenant l'opposé, on trouve $$a=bq_1-r_1=b(q_1-1)+(r_1+b).$$ On conclut exactement comme ci-dessus en posant $q=q_1-1$ et $r=r_1+b$.

Il suffit de prouver que l'ensemble des diviseurs communs à $a$ et $b$ est égal à l'ensemble des diviseurs communs de $b$ et de $r$. Écrivons donc $a=bq+r$ et soit $d$ un diviseur commun de $a$ et de $b$. Alors, écrivant $r=a-bq$, $d$ divise aussi $r$ et c'est donc un diviseur commun à $b$ et $r$.

Réciproquement, si $d$ est un diviseur commun de $b$ et de $r$, écrivant $a=bq+r$, on trouve que $d$ divise $a$, et donc que $d$ est un diviseur commun de $a$ et $b$.

Si on veut faire la démonstration "niveau Terminale", on doit la faire sans certains outils, comme la notion de sous-groupes de $\mathbb Z$. Mais on va imiter la preuve du fait que les sous-groupes de $\mathbb Z$ sont les $n\mathbb Z$. On peut supposer que $a$ est non-nul. On note $$G=\{au+bv; (u,v)\in\mathbb Z^2\}\cap\mathbb N^*.$$ Alors $G$ est non-vide car $|a|$ est élément de $G$. Notons $D$ le plus petit élément de $G$. On va prouver que $D=d$, le pgcd de $a$ et $b$.

D'une part, puisque $D\in G$, $D$ s'écrit $D=au+bv$. Puisque $d|a$ et que $d|b$, alors $d|D$ et donc $d\leq D$.

D'autre part, on va démontrer que $D$ divise $a$ et que $D$ divise $b$. Ainsi, on aura aussi $D|d$, donc $D\leq d$, ce qui prouvera que $D=d$. Pour prouver que $D$ divise $a$, effectuons la division euclidienne de $a$ par $D$ : $a=Dq+r$, avec $0\leq r\leq D-1$. On isole le reste, et on remplace $D$ par $au+bv$. Il vient $$r=a-Dq=a-(au+bv)q=a(1-uq)+bvq.$$ Mais alors, $r=0$ car sinon, $r\in G$ avec $r<D$ ce qui contredit la définition de $D$. Donc $D|a$. Le même raisonnement, mais en effectuant cette fois la division euclidienne de $b$ par $D$, prouve que $D|b$.

On peut donner une autre démonstration, par récurrence. Remarquons d'abord que, quitte à échanger le rôle de $a$ et de $b$, et à changer $u$ en $-u$ et/ou $v$ en $-v$, on peut supposer $a\geq b\geq 0$ et $a\neq 0$. Soit $n\geq 1$ et notons $\mathcal P(n)$ la propriété suivante : ``Pour tout $(a,b)\in\mathbb N^2$ avec $n\geq a\geq b$ et $a\neq 0$, il existe $(u,v)\in\mathbb Z^2$ tels que $au+bv=d$, où $d=\textrm{pgcd(a,b)}$''. On va prouver par récurrence que pour tout $n\geq 1$, la propriété $\mathcal P(n)$ est vraie. Remarquons d'abord que $\mathcal P(1)$ est vraie. En effet, les seuls cas possibles sont $(a,b)=(1,0)$ et $(a,b)=(1,1)$. Dans les deux cas, le pgcd est 1 et on peut choisir $u=1$, $v=0$. Soit maintenant $n\geq 1$ tel que $\mathcal P(n)$ est vraie, et démontrons $\mathcal P(n+1)$. On fixe donc $a,b\in\mathbb N^2$ tels que $n+1\geq a\geq b$ et $a\neq 0$. On distingue trois cas :

Le sens direct est l'égalité de Bézout démontrée ci-dessus. Le sens réciproque est très facile. En effet, si $d|a$ et $d|b$, alors $d|au+bv=1$, et donc tout diviseur commun à $a$ et $b$ divise $1$ (et est donc égal à $1$ ou $-1$). Ainsi, le pgcd de $a$ et de $b$ est égal à $1$.

C'est une conséquence du théorème de Bézout. En effet, l'hypothèse $a|bc$ donne l'existence d'un entier $k$ tel que $bc=ka$. Puisque $a\wedge b=1$, on sait également qu'il existe un couple d'entiers $(u,v)$ tel que $au+bv=1$. On multiplie par $c$ cette dernière égalité, et on trouve $auc+bvc=c$, soit $auc+kav=c$, soit encore $a(uc+kv)=c$. C'est bien que $a|c$.

Écrivons $n={a_q a_{q-1}\dots a_1a_0}$ en base 10, c'est-à-dire que $$n=10^q a_q+10^{q-1}a_{q-1}+\dots+10 a_1+a_0.$$ Pour la divisibilité par 3 ou par 9, on remarque que 10 est congru à 1 modulo 3 ou modulo 9. Par une récurrence facile, on en déduit que $10^k$ est congru à 1 modulo 3 ou modulo 9 pour tout $k\geq 1$.. Ainsi, utilisant la compatibilité de la congruence avec les opérations, on en déduit que $$n\equiv a_q+\dots+a_0\ [3]$$ et $$n\equiv a_q+\dots+a_0\ [9].$$ D'autre part, $n$ est divisible par $3$ si et seulement si $n\equiv 0\ [3]$, donc si et seulement si $$a_q+\dots+a_0\equiv 0\ [3],$$ c'est-à-dire si et seulement si la somme des chiffres de $n$ est divisible par 3. La démonstration du critère de divisibilité par 9 est exactement identique.

Concernant le critère de divisibilité par 5, on remarque cette fois que $10\equiv 0\ [5]$, et donc que $10^k\equiv 0\ [5]$ pour $k\geq 1$. On en déduit que $$n\equiv a_0\ [5]$$ et on conclut exactement de la même façon.

Le critère de divisibilité modulo 11 est un peu plus subtil. On remarque cette fois que $10\equiv -1\ [11]$, puis que $100=10^2\equiv -10\equiv 1\ [11]$. Par une récurrence à nouveau, on a $10^k\equiv 1\ [11]$ si $k$ est pair, et $10^k\equiv -1\ [11]$ si $k$ est impair. Ainsi, $$n\equiv (a_0+a_2+a_4+\dots)-(a_1+a_3+a_5+\dots)\ [11],$$ ce qui démontre le résultat voulu.

On commence par démontrer que si $n$ est un entier, alors $n^2$ pair entraine que $n$ est pair. Par contraposée, il suffit de démontrer que si $n$ est impair, alors $n^2$ est impair. Mais si $n$ est impair, alors $n$ s'écrit $2k+1$, et donc $n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$ est impair, ce qui prouve ce premier résultat.

Supposons ensuite qu'il existe deux entiers naturels $a,b$, avec $b\neq 0$, tels que $\sqrt 2=\frac ab$. On peut toujours supposer (quitte à réduire la fraction), que $a$ et $b$ sont premiers entre eux. Mettons cette égalité au carré. On trouve $a^2=2b^2$. Ainsi, $a^2$ est un entier pair. Par le rappel effectué ci-dessus, $a$ est un entier pair. Il s'écrit donc $a=2a'$. Mais puisque $a^2=2b^2$, on a aussi $b^2=2a'^2$. Ainsi, $b^2$ est pair et donc, par le même raisonnement, $b$ est pair : il existe un entier $b'$ tel que $b=2b'$. Mais $2$ divise $a$ et $2$ divise $b$ : ceci contredit que $a$ et $b$ sont premiers entre eux.

Le sens réciproque est évident. Si $n$ admet un diviseur premier inférieur ou égal à $\sqrt n$, puisque $\sqrt n<n$ (on sait que $n\geq 2$), il admet un diviseur autre que 1 et lui-même, donc il n'est pas premier.

D'autre part, supposons que $n$ ne soit pas premier, et soit $p$ le plus petit diviseur de $n$ tel que $p\geq 2$ (un tel diviseur existe car $n$ n'est pas premier). Alors :

Procédons par l'absurde et supposons qu'il existe un nombre fini de nombres premiers qui sont $p_1,\dots,p_r$. Posons $m=p_1\times p_2\times\dots\times p_r+1$. Soit $q$ un diviseur premier de $m$. Alors $q$ ne peut pas être égal à aucun des $p_i$, puisque si $q=p_i$, alors $q$ divise le produit $p_1\times p_2\times\dots\times p_r$, $q$ divise aussi $m=p_1\times p_2\times\dots\times p_r+1$ et donc $q$ divise $1$, ce qui est faux. $q$ est donc un nombre premier différent de $p_1,\dots,p_r$ ce qui est absurde. L'ensemble des nombres premiers est donc infini.

Existence : On démontre cette propriété par récurrence forte. Posons donc, pour $n\geq 2$, la propriété $$\mathcal P(n) : ``\textrm{Pour tout }2\leq k\leq n,\ k \textrm{ se factorise en produit de facteurs premiers}''.$$ Alors $\mathcal P(2)$ est vraie puisque $2=2^1$ et que $2$ est premier. Soit maintenant $n\geq 2$ tel que $\mathcal P(n)$ est vraie, et prouvons que $\mathcal P(n+1)$ est vraie. Il suffit de prouver que $n+1$ se factorise en produit de facteurs premiers. Si $n+1$ est premier, c'est évident. Sinon, soit $p$ un diviseur premier de $n+1$ et écrivons $n+1=p\times k$. Alors $2\leq k\leq n$ et donc d'après l'hypothèse de récurrence, $k$ se factorise en produit de facteurs premiers. C'est donc aussi le cas de $n+1$.

Unicité : Suppons que $n$ se factorise de deux façons différentes $$n=p_1^{\alpha_1}\dots p_r^{\alpha_r}=p_1^{\beta_1}\dots p_r^{\beta_r}$$ avec $\alpha_i,\beta_i\in\mathbb N$ et, par exemple, $\alpha_1<\beta_1$ (on autorise maintenant les $\alpha_i$ et les $\beta_i$ à s'annuler pour gérer le fait que les nombres premiers qui interviennent dans les deux décompositions peuvent être différents). Mais alors, on simplifie par $p_1^{\alpha_1}$ et donc on écrit $$p_1^{\beta_1-\alpha_1}p_2^{\beta_2}\dots p_r^{\beta_r}=p_2^{\alpha_2}\dots p_r^{\alpha_r}.$$ Ainsi, $p_1$ divise le produit $p_2^{\alpha_2}\dots p_r^{\alpha_r}$. Puisque $p_1$ est premier, par le lemme de Gauss, $p_1$ divise l'un des $p_i$, $i\geq 2$, ce qui est absurde.

D'abord, si $b|a$, alors $b$ est un diviseur commun à $a$ et $b$. C'est nécessairement le plus grand, puisque les diviseurs de $b$ sont inférieurs ou égaux à $b$, et donc $\textrm{pgcd}(a,b)=b$. Réciproquement, si $\textrm{pgcd}(a,b)=b$, alors $b$ est un diviseur commun à $a$ et $b$ et donc $b$ divise $a$.

Il est d'abord clair que $p_1^{\delta_1}\cdots p_r^{\delta_r}$ est un diviseur commun à $a$ et $b$. Soit maintenant $d$ un diviseur commun à $a$ et $b$. Soit $p$ un diviseur premier de $d$. Alors $p|a$ (c'est une conséquence de l'unicité de la décomposition en produit de facteurs premiers) et donc $p$ est un des $p_1,\dots,p_r$. On peut alors écrire $d=p_1^{\gamma_1}\cdots p_r^{\gamma_r}$. Puisque $d|a$, on a $p_1^{\gamma_1}|p_1^{\alpha_1}\cdots p_r^{\alpha_r}$. Par le théorème de Gauss, on obtient $p_1^{\gamma_1}|p_1^{\alpha_1}$ et donc $\gamma_1\leq \alpha_1$. Par symétrie, on a aussi $\gamma_1\leq \beta_1$ et plus généralement, $\gamma_i\leq \min(\alpha_i,\beta_i)$, $i=1,\dots,r$. On a donc que $d| p_1^{\delta_1}\cdots p_r^{\delta_r}$. Ce dernier nombre est bien le pgcd de $a$ et de $b$.

Notons $d=\textrm{pgcd}(a,b)$ et $e=\textrm{pgcd}(ka,kb)$. On a $d|a$, $d|b$ donc $kd|ka$ et $kd|kb$. $kd$ est donc un diviseur commun de $ka$ et $kb$ ce qui entraîne que $kd|e$. On peut donc écrire $e=kdu$, avec $u$ un entier. On a $e|ka$ et donc $kdu|ka$ soit $du|a$. De même, on a $du|b$ et donc, par définition du pgcd, $du|d$. C'est que $u=1$ et donc que $e=kd$, comme désiré.

Supposons d'abord que $\textrm{pgcd(a,b)}=\delta$. Si $\frac a\delta$ et $\frac b\delta$ ne sont pas premiers entre eux, alors soit $d\geq 2$ un diviseur commun à $a$ et $b$. Alors $d\delta|a$ et $d\delta|b$, ce qui contredit que $\delta$ est le pgcd de $a$ et $b$. Réciproquement, si $\textrm{pgcd}\left(\frac a\delta,\frac b\delta\right)=1$, alors $\textrm{pgcd}(a,b)=\delta$ par la formule d'homogénéité du pgcd.

Supposons d'abord que $n|a-b$ et écrivons les divisions euclidiennes respectives de $a$ et $b$ par $n$, à savoir $a=nq+r$ et $b=nq'+r'$, avec $0\leq r,r'<n$. Prenons la différence, on obtient $a-b=n(q-q')+(r-r')$. Puisque $n|a-b$ et $n|n(q-q')$, il est aussi clair que $n|r-r'$. Mais comme $|r-r'|<n$, ceci n'est possible que si $r-r'=0$, c'est-à-dire si $r=r'$.

Supposons maintenant que $a$ et $b$ ont même reste dans la division euclidienne modulo $n$, c'est-à-dire que $a=nq+r$ et $b=nq'+r$. Alors, faisant la différence, on trouve $a-b=n(q-q')$ ce qui prouve immédiatement que $n|a-b$.

On a :

Soit $k,l$ tels que $a=a'+km$ et $b=b'+lm$. Alors $a+b=a'+b'+(k+l)m$ et donc $a+b\equiv a'+b'\ [m]$. De même, $ab=(a'+km)(b'+lm)=a'b'+m(kb'+la'+klm)$ et donc $ab\equiv a'b'\ [m]$.

Remarquons d'abord que l'hypothèse entraîne que $a$ et $p$ sont premiers entre eux. On remarque ensuite que $p$ ne divise aucun entier $ka$, pour $1\leq k\leq p-1$. En effet, puisque $p\wedge a=1$, on aurait par le théorème de Gauss $p|k$, ce qui est impossible puisqu'on a aussi $1\leq k<p$.

Considérons maintenant les nombres $a,2a,\dots,(p-1)a$. Ils ont tous des restes différents dans leur division par $p$. Pour démontrer ceci, procédons par l'absurde et supposons que ce n'est pas le cas. Soit $1\leq k<l\leq p-1$ tels que $ka$ et $la$ ont même reste dans la division par $p$. Ceci entraîne que $p|(l-k)a$, et on vient de démontrer que c'est impossible.

Pour $1\leq k\leq p-1$, notons $r_k$ le reste de $ka$ dans la division euclidienne de $ka$ par $p$. Les entiers $r_k$ sont tous différents, ils sont éléments de $\{1,\dots,p-1\}$, et il y en a exactement $p-1$. C'est donc qu'ils sont exactement, à l'ordre près, les entiers $1,\dots,p-1$. On en déduit que \begin{eqnarray*} a\times 2a\times\dots\times (p-1)a&\equiv&r_1\times\cdots\times r_{p-1}\ [p]\\ &\equiv& 1\times 2\times\dots\times (p-1)\ [p] \end{eqnarray*} Ceci se réécrit en disant que $$(p-1)!a^{p-1}\equiv (p-1)!\ [p]$$ ou encore que $p$ divise $(p-1)!a^{p-1}-(p-1)!=(p-1)!(a^{p-1}-1)$. Or, $p$ est premier avec $(p-1)!=1\times 2\times\dots\times(p-1)$, et donc par le théorème de Gauss, $p$ divise $a^{p-1}-1$.

Puisque $m\wedge n=1$, il existe d'après le théorème de Bézout un couple d'entiers $(u,v)$ tel que $mu+nv=1$. Posons $x_0=bmu+anv$. Alors $x_0$ est solution du système. En effet, $x_0=b(1-nv)+anv=b+n(va-vb)\equiv b\ [n]$ et $x_0=bmu+a(1-mu)=a+m(bu-au)\equiv a\ [m]$.

Posons ensuite $x=x_0+kmn$. Alors on a $x=x_0+n(km)\equiv x_0\ [n]$ et de même $x\equiv x_0\ [m]$. Ainsi, $x$ est bien une solution du système.

Enfin, fixons $x$ une solution du système. Alors on a $$\left\{ \begin{array}{rcl} x-x_0&\equiv&0\ [m]\\ x-x_0&\equiv&0\ [n] \end{array}\right.$$ Ainsi, il existe des entiers $s$ et $t$ tels que $x-x_0=sm$ et $x-x_0=tn$. On en déduit que $sm=tn$ et donc que $m|tn$. Mais $m\wedge n=1$ et donc $m|t$ par le théorème de Gauss. Ainsi, $t$ s'écrit $t =km$ et $x=x_0+kmn$.