Arithmétique des entiers relatifs

1Divisibilité dans $\Z$

Définition. Soient $a,b\in\Z$. On dit que $a$ divise $b$, et l’on note $a\mid b$, lorsqu’il existe $k\in\Z$ tel que $b=ak$. On dit aussi que $a$ est un diviseur de $b$, ou que $b$ est un multiple de $a$. On note $\mathcal{D}(b)=\ens{d\in\Z,\ d\mid b}$ l’ensemble des diviseurs de $b$.

Propriété — règles de calcul. Soient $a,b,c,u,v\in\Z$.

Théorème — entiers associés. Soient $a,b\in\Z$. Alors $\ a\mid b$ et $b\mid a\iff b=a$ ou $b=-a$. On dit alors que $a$ et $b$ sont associés. En particulier, deux entiers naturels qui se divisent mutuellement sont égaux.

Idée de preuve (exigible). Si $a=0$, $a\mid b$ donne $b=0$. Sinon $\abs{a}\leq\abs{b}$ et $\abs{b}\leq\abs{a}$, donc $\abs{a}=\abs{b}$.

2Division euclidienne

Théorème — division euclidienne. Soient $a\in\Z$ et $b\in\Z^{*}$. Il existe un unique couple $(q,r)\in\Z^{2}$ tel que

L’entier $q$ est le quotient, $r$ le reste de la division euclidienne de $a$ par $b$. De plus $\ b\mid a\iff r=0$.

Idée de preuve (exigible). Existence pour $b>0$ : $E=\ens{k\in\Z,\ bk\leq a}$ est non vide et majoré, donc admet un plus grand élément $q$ ; alors $bq\leq a<b(q+1)$ et $r=a-bq$ convient. Unicité : si $bq+r=bq'+r'$ avec $0\leq r,r'<b$, alors $b(q-q')=r'-r$ avec $\abs{r'-r}<b$, donc $r=r'$ puis $q=q'$. Le cas $b<0$ s’en déduit en remplaçant $b$ par $-b$. Pour $b>0$, $q=\left\lfloor\frac{a}{b}\right\rfloor$.

Méthode — disjonction selon le reste. pour étudier une propriété de $n\in\Z$ modulo $b$, écrire $n=bq+r$ avec $r\in\intent{0}{b-1}$ et traiter les $b$ cas : ils recouvrent $\Z$ sans se chevaucher, par unicité du reste.

3PGCD, algorithme d’Euclide, PPCM

Théorème — pgcd. Soient $a,b\in\Z$ non tous deux nuls. L’ensemble $\mathcal{D}(a)\cap\mathcal{D}(b)$ des diviseurs communs à $a$ et $b$ admet un plus grand élément, appelé pgcd de $a$ et $b$ et noté $a\wedge b$ ; il appartient à $\N^{*}$ et vérifie $\mathcal{D}(a)\cap\mathcal{D}(b)=\mathcal{D}(a\wedge b)$. Ainsi $a\wedge b$ est le plus grand des diviseurs communs au sens de la divisibilité : tout diviseur commun divise $a\wedge b$.

Propriété — règles de calcul. Pour $a,b,c\in\Z$ non tous nuls et $k\in\N^{*}$ :

Théorème — algorithme d’Euclide. Soient $a,b\in\N$ avec $b\neq 0$. On pose $r_{0}=a$, $r_{1}=b$ et, tant que $r_{k}\neq0$, on note $r_{k+1}$ le reste de la division euclidienne de $r_{k-1}$ par $r_{k}$. Si $r_{N+1}=0$ est le premier reste nul, alors $\ a\wedge b=r_{N}$ : le pgcd est le dernier reste non nul.

Idée de preuve (exigible). Terminaison : $(r_{k})_{k\geq1}$ est une suite d’entiers naturels strictement décroissante tant qu’elle ne s’annule pas, donc elle s’annule. Correction : à chaque étape $r_{k-1}\wedge r_{k}=r_{k}\wedge r_{k+1}$ d’après la règle ci-dessus ; par récurrence $a\wedge b=r_{N}\wedge r_{N+1}=r_{N}\wedge0=r_{N}$.

Théorème — relation de Bézout. Soient $a,b\in\Z$ non tous nuls et $d=a\wedge b$. Il existe $(u,v)\in\Z^{2}$ tel que

Un tel couple $(u,v)$, appelé couple de Bézout de $(a,b)$, s’obtient par l’algorithme d’Euclide étendu : on remonte les divisions successives en exprimant chaque reste comme combinaison de $a$ et $b$.

Définition. Soient $a,b\in\Z^{*}$. L’ensemble des multiples communs strictement positifs de $a$ et $b$ est non vide (il contient $\abs{ab}$) : il admet un plus petit élément, appelé ppcm de $a$ et $b$ et noté $a\vee b$. Les multiples communs de $a$ et $b$ sont exactement les multiples de $a\vee b$, et $\ \boxed{(a\wedge b)\,(a\vee b)=\abs{ab}}$. En particulier, si $a\wedge b=1$ alors $a\vee b=\abs{ab}$.

4Entiers premiers entre eux

Définition. Deux entiers $a$ et $b$ sont premiers entre eux lorsque $a\wedge b=1$, c’est-à-dire lorsque leurs seuls diviseurs communs sont $1$ et $-1$.

Théorème — théorème de Bézout. Soient $a,b\in\Z$. Alors

Idée de preuve (exigible). ($\Rightarrow$) c’est la relation de Bézout avec $d=1$. ($\Leftarrow$) si $au+bv=1$, tout diviseur commun $d$ de $a$ et $b$ divise $au+bv=1$, donc $d\in\ens{-1,1}$ : $a\wedge b=1$.

Théorème — lemme de Gauss. Soient $a,b,c\in\Z$. Si $a\mid bc$ et $a\wedge b=1$, alors $a\mid c$.

Idée de preuve (exigible). Par Bézout, $au+bv=1$ ; en multipliant par $c$, $c=acu+(bc)v$. Or $a$ divise $ac$ et $a$ divise $bc$ par hypothèse, donc $a$ divise cette combinaison linéaire, c’est-à-dire $c$.

Propriété — conséquences à connaître. Soient $a,b,c,n\in\Z$.

Définition. Soient $a_{1},\dots,a_{n}\in\Z$ non tous nuls. Ils sont premiers entre eux dans leur ensemble lorsque $a_{1}\wedge\cdots\wedge a_{n}=1$, et premiers entre eux deux à deux lorsque $a_{i}\wedge a_{j}=1$ pour tous $i\neq j$. On a la relation de Bézout généralisée : il existe $u_{1},\dots,u_{n}\in\Z$ tels que $\sum_{i=1}^{n}a_{i}u_{i}=a_{1}\wedge\cdots\wedge a_{n}$.

5Nombres premiers

Définition. Un entier $p\geq2$ est premier lorsque ses seuls diviseurs positifs sont $1$ et $p$. On note $\mathcal{P}$ l’ensemble des nombres premiers : $\mathcal{P}=\ens{2,3,5,7,11,13,17,19,23,29,\dots}$. Un entier $n\geq2$ non premier est dit composé. L’entier $1$ n’est pas premier.

Propriété. Tout entier $n\geq2$ admet un diviseur premier, et son plus petit diviseur $>1$ est premier. Si $n\geq2$ n’a aucun diviseur premier $p\leq\sqrt{n}$, alors $n$ est premier.

Méthode — crible d’Ératosthène. pour lister les nombres premiers $\leq N$ : écrire $2,3,\dots,N$, puis, tant qu’il reste un entier non barré $p\leq\sqrt{N}$, barrer tous les multiples de $p$ strictement supérieurs à $p$. Les entiers non barrés sont les nombres premiers $\leq N$ : on s’arrête à $\sqrt{N}$ car tout composé $n\leq N$ a un diviseur premier $\leq\sqrt{n}$.

Théorème. L’ensemble $\mathcal{P}$ des nombres premiers est infini.

Idée de preuve (exigible). Par l’absurde, si $\mathcal{P}=\ens{p_{1},\dots,p_{k}}$, l’entier $N=p_{1}\cdots p_{k}+1$ est $\geq2$, donc admet un diviseur premier $p=p_{i}$ ; alors $p$ divise $N$ et $N-1$, donc $p\mid1$ : absurde.

Théorème — lemme d’Euclide. Soit $p\in\mathcal{P}$ et $a,b\in\Z$. Alors $\ p\mid ab\Longrightarrow p\mid a$ ou $p\mid b$. Plus généralement, si $p$ divise un produit $a_{1}\cdots a_{n}$, il divise l’un des $a_{i}$.

Idée de preuve. Si $p\nmid a$, alors $p\wedge a=1$ (les diviseurs positifs de $p$ sont $1$ et $p$), et le lemme de Gauss donne $p\mid b$.

Théorème — décomposition en facteurs premiers. Tout entier $n\geq2$ s’écrit

avec $r\geq1$, $p_{1}<p_{2}<\cdots<p_{r}$ premiers et $\alpha_{i}\in\N^{*}$ ; cette écriture est unique.

Idée de preuve (exigible). Existence par récurrence forte : si $n$ est premier c’est fini, sinon $n=ab$ avec $2\leq a,b<n$ et l’on applique l’hypothèse de récurrence. Unicité : si deux décompositions coïncident, un premier $p$ figurant à gauche divise le produit de droite, donc l’un de ses facteurs premiers par le lemme d’Euclide, donc lui est égal ; on simplifie par $p$ et l’on conclut par récurrence sur $n$.

Définition. Soit $p\in\mathcal{P}$ et $n\in\Z^{*}$. La valuation $p$-adique de $n$, notée $v_{p}(n)$, est le plus grand $k\in\N$ tel que $p^{k}\mid n$ ; c’est l’exposant de $p$ dans la décomposition de $\abs{n}$ (avec $v_{p}(n)=0$ si $p\nmid n$). On convient $v_{p}(0)=+\infty$. Ainsi, pour $n\geq2$,

produit où seuls un nombre fini de facteurs diffèrent de $1$.

Théorème — propriétés des valuations. Soient $a,b\in\Z^{*}$, $p\in\mathcal{P}$ et $k\in\N$.

6Congruences et calcul modulaire

Définition. Soient $n\in\N^{*}$ et $a,b\in\Z$. On dit que $a$ est congru à $b$ modulo $n$, et l’on note $a\equiv b\ [n]$, lorsque $n\mid(b-a)$. C’est le cas si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$.

Propriété. La relation $\equiv\ [n]$ est réflexive, symétrique et transitive. Elle est compatible avec les opérations : si $a\equiv b\ [n]$ et $c\equiv d\ [n]$, alors

Elle n’est pas compatible avec la division : voir l’encadré ci-dessous. La structure d’anneau $\Z/n\Z$ est hors programme : on calcule uniquement avec les congruences.

Théorème — inverse modulo $n$. Soient $n\in\N^{*}$ et $a\in\Z$. Il existe $a'\in\Z$ tel que $aa'\equiv1\ [n]$ si et seulement si $a\wedge n=1$. Un tel $a'$, unique modulo $n$, est appelé inverse de $a$ modulo $n$ ; on l’obtient par l’algorithme d’Euclide étendu : de $au+nv=1$ on tire $a'=u$.

Méthode — résoudre $ax\equiv b\ [n]$. poser $d=a\wedge n$.

• Si $d\nmid b$ : aucune solution. En effet $ax\equiv b\ [n]$ signifie $b=ax-nk$ pour un certain $k\in\Z$ ; or $d\mid a$ et $d\mid n$, donc $d$ diviserait $b$.
• Si $d\mid b$ : l’équation équivaut à $\frac{a}{d}x\equiv\frac{b}{d}\ \left[\frac{n}{d}\right]$, où $\frac{a}{d}$ est inversible modulo $\frac{n}{d}$ ; en notant $a'$ son inverse, $x\equiv a'\frac{b}{d}\ \left[\frac{n}{d}\right]$. Il y a alors exactement $d$ classes de solutions modulo $n$.

Méthode — résoudre $ax+by=c$ dans $\Z^{2}$. soit $d=a\wedge b$. Si $d\nmid c$, pas de solution. Sinon : (i) trouver une solution particulière $(x_{0},y_{0})$ par l’algorithme d’Euclide étendu ; (ii) soustraire pour obtenir $a(x-x_{0})=-b(y-y_{0})$, puis simplifier par $d$ et appliquer le lemme de Gauss. On obtient

et il faut vérifier que tous ces couples sont bien solutions (la double inclusion est exigée).

Théorème — petit théorème de Fermat. Soit $p\in\mathcal{P}$ et $a\in\Z$.

• Si $p\nmid a$, alors $\ a^{\,p-1}\equiv1\ [p]$.
• Sans hypothèse sur $a$ : $\ a^{p}\equiv a\ [p]$.

Idée de preuve (exigible). Pour $p\nmid a$, $k\mapsto$ reste de $ak$ modulo $p$ est une bijection de $\intent{1}{p-1}$ sur lui-même (si $ak\equiv ak'$ alors $k\equiv k'$ par Gauss, car $a\wedge p=1$). En multipliant les $p-1$ congruences $ak\equiv r_{k}\ [p]$ : $a^{\,p-1}(p-1)!\equiv(p-1)!\ [p]$, et l’on simplifie par $(p-1)!$, premier à $p$. La seconde forme s’en déduit en multipliant par $a$.