Arithmétique (spécialité Mathématiques Expertes)

Diviseurs et multiples

Soit $a$ et $b$ deux entiers relatifs. On dit que $a$ divise $b$ (ou que $b$ est divisible par $a$, ou encore que $b$ est un multiple de $a$) s'il existe un entier relatif $k$ tel que :

$$b = ka$$

On note alors $a \mid b$ (« $a$ divise $b$ »).

Exemple. $45 = (-9) \times (-5)$, donc $-9$ divise $45$ : on note $-9 \mid 45$.

Remarques.

• $0$ est un multiple de tout entier $a$, car $0 = a \times 0$.
• $1$ divise tout entier $a$, car $a = 1 \times a$ ; et tout entier divise $0$.
• Si $b$ divise $a$ et $a \neq 0$, alors $|b| \leqslant |a|$.
• Si $a \mid b$ et $b \mid a$, alors $a = b$ ou $a = -b$.
• L'ensemble des multiples d'un entier $n$ se note $n\mathbb{Z}$. Par exemple $6\mathbb{Z} = \{\ldots, -12, -6, 0, 6, 12, \ldots\}$.
• L'ensemble des diviseurs (positifs et négatifs) de $6$ est $\{-6, -3, -2, -1, 1, 2, 3, 6\}$.

Propriétés de la divisibilité

Propriété (signes). Pour $a, b \in \mathbb{Z}$ avec $b \neq 0$ :

$$b \mid a \iff (-b) \mid a \iff b \mid (-a) \iff (-b) \mid (-a)$$

Propriété (transitivité). Si $a \mid b$ et $b \mid c$, alors $a \mid c$.

Démonstration. Si $a \mid b$ et $b \mid c$, il existe $k, k' \in \mathbb{Z}$ tels que $b = ka$ et $c = k'b$. Donc $c = k'ka = (kk')a$ : en posant $l = kk'$, on a $c = la$, donc $a \mid c$.

Propriété (combinaison linéaire). Soit $a, b, c$ des entiers relatifs non nuls. Si $a \mid b$ et $a \mid c$, alors $a$ divise toute combinaison linéaire de $b$ et $c$ :

$$\text{il existe } (\alpha, \beta) \in \mathbb{Z}^2 \text{ tel que } a \mid (\alpha b + \beta c)$$

Démonstration. Il existe $k, k' \in \mathbb{Z}$ tels que $b = ka$ et $c = k'a$, donc $\alpha b + \beta c = (\alpha k + \beta k')a$, ce qui prouve que $a \mid (\alpha b + \beta c)$.

Conséquence immédiate. Si un entier $N$ divise deux entiers consécutifs $n$ et $n+1$, alors $N$ divise $(n+1) - n = 1$, donc $N = 1$ ou $N = -1$.

Méthode : utiliser une combinaison linéaire pour résoudre un problème de divisibilité.

Déterminons les entiers relatifs $n$ tels que $(2n+5)$ divise $(n-1)$.

On a toujours $(2n+5) \mid (2n+5)$. Si de plus $(2n+5) \mid (n-1)$, alors par combinaison linéaire :

$$(2n+5) \mid \big(-2(n-1) + (2n+5)\big) \iff (2n+5) \mid 7$$

Les diviseurs de $7$ sont $-7, -1, 1, 7$, ce qui donne $n \in \{-6, -3, -2, 1\}$.

Attention : cette condition est nécessaire mais pas automatiquement suffisante — il faut vérifier la réciproque pour chaque valeur trouvée. En remplaçant, on vérifie que $(2n+5) \mid (n-1)$ est bien vraie pour chacune de ces quatre valeurs (par exemple pour $n=-6$ : $2n+5=-7$ et $n-1=-7$, et $-7 \mid -7$). Les solutions sont donc exactement $n \in \{-6, -3, -2, 1\}$.

Division euclidienne dans $\mathbb{Z}$

Théorème. Soit $a$ un entier relatif et $b$ un entier naturel non nul. Il existe un unique couple d'entiers $(q, r)$ tel que :

$$a = bq + r \quad \text{et} \quad 0 \leqslant r < b$$

$q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.

Exemple. $412 = 15 \times 27 + 7$ : dans la division euclidienne de $412$ par $15$, le quotient est $27$ et le reste $7$.

Remarque. $b \mid a$ si, et seulement si, le reste de la division euclidienne de $a$ par $b$ est nul.

Cas d'un dividende négatif. Pour déterminer la division euclidienne d'un entier négatif, on part de la division euclidienne de sa valeur absolue puis on ajuste pour que le reste reste positif ou nul.

Exemple. Déterminons quotient et reste de la division de $-1000$ par $13$. On a $1000 = 13 \times 76 + 12$. Donc $-1000 = 13 \times (-76) - 12 = 13 \times (-76) - 13 + 13 - 12 = 13 \times (-77) + 1$. Comme $0 \leqslant 1 < 13$, le quotient de $-1000$ par $13$ est $-77$ et le reste est $1$.

Écriture d'un entier selon son reste

Propriété. Soit $b \geqslant 2$ un entier. Tout entier $a$ s'écrit sous une, et une seule, des formes $bq, bq+1, bq+2, \ldots, bq+(b-1)$, où $q$ est un entier relatif (c'est une reformulation directe de la division euclidienne, avec $r \in \{0, 1, \ldots, b-1\}$).

Méthode : raisonner par disjonction des cas.

Montrons que pour tout entier naturel $n$, le nombre $A = n(n-2)(n+2)$ est un multiple de $3$.

Tout entier $n$ s'écrit sous l'une des trois formes $3k$, $3k+1$ ou $3k+2$ (avec $k$ entier naturel). On étudie chaque cas :

• Si $n = 3k$ : $A = 3k(3k-2)(3k+2)$, qui est bien un multiple de $3$.
• Si $n = 3k+1$ : $A = (3k+1)(3k-1)(3k+3) = 3(3k+1)(3k-1)(k+1)$, multiple de $3$.
• Si $n = 3k+2$ : $A = (3k+2)(3k)(3k+4)$, multiple de $3$ (facteur $3k$).

Dans tous les cas, $A$ est un multiple de $3$.

PGCD de deux entiers

Définition. Soit $a$ et $b$ deux entiers relatifs non tous les deux nuls. Le plus grand commun diviseur de $a$ et $b$, noté $\text{PGCD}(a,b)$, est le plus grand des diviseurs communs (positifs) à $a$ et $b$.

Cette notion prolonge directement la divisibilité étudiée dans la notion précédente : l'ensemble des diviseurs communs à $a$ et $b$ est exactement l'ensemble des diviseurs de $\text{PGCD}(a,b)$.

Algorithme d'Euclide

Propriété. Soit $a$ un entier relatif et $b$ un entier naturel non nul. Si $a = bq + r$ est la division euclidienne de $a$ par $b$, alors :

$$\text{PGCD}(a,b) = \text{PGCD}(b,r)$$

Idée de la démonstration. La relation $a = bq+r$, c'est-à-dire $r = a - bq$, exprime $r$ comme combinaison linéaire de $a$ et $b$ (voir la notion précédente) : tout diviseur commun à $a$ et $b$ divise donc aussi $r$, et réciproquement tout diviseur commun à $b$ et $r$ divise $a = bq + r$. Les couples $(a,b)$ et $(b,r)$ ont donc exactement les mêmes diviseurs communs, donc le même PGCD.

Algorithme. On effectue des divisions euclidiennes en cascade : on divise $a$ par $b$, puis $b$ par le reste obtenu, puis ce reste par le reste suivant, etc., jusqu'à obtenir un reste nul. Le PGCD de $a$ et $b$ est alors le dernier reste non nul.

Exemple. Calculons $\text{PGCD}(198, 84)$ :

$198 = 2 \times 84 + 30$ $84 = 2 \times 30 + 24$ $30 = 1 \times 24 + 6$ $24 = 4 \times 6 + 0$

Le dernier reste non nul est $6$, donc $\text{PGCD}(198, 84) = 6$.

Nombres premiers entre eux

Définition. Deux entiers relatifs $a$ et $b$, non tous deux nuls, sont dits premiers entre eux si $\text{PGCD}(a,b) = 1$, c'est-à-dire si leur seul diviseur positif commun est $1$.

Exemple. $\text{PGCD}(14,15) = 1$ (algorithme d'Euclide : $15 = 1 \times 14 + 1$ puis $14 = 14 \times 1 + 0$) : $14$ et $15$ sont premiers entre eux. Attention à ne pas confondre avec la notion de nombre premier : ni $14 = 2\times7$ ni $15 = 3\times5$ n'est un nombre premier, mais le couple $(14,15)$ est bien premier entre eux.

Théorème de Bézout

Théorème (Bézout). Soit $a$ et $b$ deux entiers relatifs non tous deux nuls. Il existe un couple d'entiers relatifs $(u,v) \in \mathbb{Z}^2$ tel que :

$au + bv = \text{PGCD}(a,b)$

Idée de la démonstration. On raisonne à partir de l'algorithme d'Euclide appliqué à $(a,b)$ : à chaque étape, le reste obtenu s'écrit comme combinaison linéaire des deux termes de l'étape précédente (la relation $r = a - bq$ déjà utilisée pour justifier $\text{PGCD}(a,b) = \text{PGCD}(b,r)$). En remontant ainsi l'algorithme étape par étape, depuis le dernier reste non nul jusqu'aux termes de départ $a$ et $b$, on exprime finalement $\text{PGCD}(a,b)$ comme une combinaison $au+bv$ — c'est la méthode dite de l'algorithme d'Euclide étendu, illustrée ci-dessous.

Corollaire (caractérisation des entiers premiers entre eux). Deux entiers relatifs $a$ et $b$ sont premiers entre eux si, et seulement si, il existe $(u,v) \in \mathbb{Z}^2$ tel que :

$au + bv = 1$

Démonstration. Si $\text{PGCD}(a,b)=1$, le théorème de Bézout donne directement un couple $(u,v)$ tel que $au+bv=1$. Réciproquement, si un tel couple existe, tout diviseur commun $d$ à $a$ et $b$ divise $au+bv=1$ (propriété de combinaison linéaire) : donc $d=1$, et $\text{PGCD}(a,b)=1$.

Méthode : trouver un couple de Bézout par remontée de l'algorithme d'Euclide.

Reprenons $\text{PGCD}(198,84)=6$, calculé plus haut :

$198 = 2 \times 84 + 30 \qquad 84 = 2 \times 30 + 24 \qquad 30 = 1 \times 24 + 6 \qquad 24 = 4 \times 6 + 0$

On remonte l'algorithme à partir de l'avant-dernière ligne, en isolant à chaque fois le reste :

$6 = 30 - 1 \times 24$

En remplaçant $24 = 84 - 2\times 30$ :

$6 = 30 - (84 - 2\times30) = 3\times30 - 84$

En remplaçant enfin $30 = 198 - 2\times84$ :

$6 = 3\times(198-2\times84) - 84 = 3\times198 - 7\times84$

On obtient $198 \times 3 + 84 \times(-7) = 6$. Vérification par substitution directe : $3\times198 = 594$ et $7\times84=588$, donc $594-588=6$ : le couple $(u,v)=(3,-7)$ convient bien.

Remarque (culture mathématique). Cette technique de remontée porte le nom d'algorithme d'Euclide étendu ; son usage pour résoudre $au+bv=\text{PGCD}(a,b)$ remonte à Bachet de Méziriac (1612), avant d'être formalisé par Bézout (1766) — d'où le nom donné aujourd'hui au théorème.

Théorème de Gauss

Théorème (Gauss). Soit $a, b, c$ trois entiers relatifs. Si $a$ divise $bc$ et si $a$ est premier avec $b$ (c'est-à-dire $\text{PGCD}(a,b)=1$), alors $a$ divise $c$.

Démonstration. Comme $a$ et $b$ sont premiers entre eux, le corollaire du théorème de Bézout donne des entiers $u,v$ tels que $au+bv=1$. En multipliant par $c$ :

$auc + bvc = c$

Le terme $auc$ est multiple de $a$. Comme $a \mid bc$, il existe $k$ tel que $bc=ak$, donc $bvc = v(bc) = v(ak) = a(vk)$ est aussi multiple de $a$. La somme $auc+bvc$ est donc multiple de $a$, c'est-à-dire $a \mid c$.

Exemple. Montrons que si $12 \mid 7n$ pour un entier $n$, alors $12 \mid n$. On vérifie d'abord que $12$ et $7$ sont premiers entre eux (algorithme d'Euclide : $12=1\times7+5$, $7=1\times5+2$, $5=2\times2+1$, $2=2\times1+0$, dernier reste non nul $1$). Le théorème de Gauss, appliqué avec $a=12$, $b=7$, $c=n$, donne alors directement $12 \mid n$.

Équations diophantiennes linéaires $ax+by=c$

On appelle équation diophantienne une équation dont on cherche les solutions entières. On s'intéresse ici aux équations $ax+by=c$, d'inconnues $(x,y) \in \mathbb{Z}^2$, où $a, b, c$ sont des entiers relatifs donnés avec $(a,b) \neq (0,0)$.

Propriété (existence de solutions). Soit $d = \text{PGCD}(a,b)$. L'équation $ax+by=c$ admet des solutions entières si, et seulement si, $d$ divise $c$.

Démonstration. Si $(x,y)$ est solution, $d$ divise $a$ et $b$, donc $d$ divise $ax+by=c$. Réciproquement, si $d \mid c$, on écrit $c=dk$ ; le théorème de Bézout donne $(u,v)$ tels que $au+bv=d$, donc $a(ku)+b(kv) = k(au+bv) = kd = c$ : le couple $(x_0,y_0)=(ku,kv)$ est une solution particulière.

Propriété (solution générale). Lorsque $d \mid c$, si $(x_0,y_0)$ est une solution particulière de $ax+by=c$, l'ensemble des solutions entières est :

$x = x_0 + \dfrac{b}{d}\,k, \qquad y = y_0 - \dfrac{a}{d}\,k, \qquad k \in \mathbb{Z}$

Idée de la démonstration. Si $(x,y)$ est une autre solution, en soustrayant $ax_0+by_0=c$ à $ax+by=c$ on obtient $a(x-x_0) = b(y_0-y)$, puis, en divisant par $d$ : $\dfrac{a}{d}(x-x_0) = \dfrac{b}{d}(y_0-y)$. Or $\dfrac{a}{d}$ et $\dfrac{b}{d}$ sont premiers entre eux (car $au+bv=d$ donne, en divisant par $d$, $\dfrac{a}{d}u+\dfrac{b}{d}v=1$) : le théorème de Gauss donne alors $\dfrac{a}{d} \mid (y_0-y)$, d'où $y_0-y=\dfrac{a}{d}k$ pour un entier $k$, puis $x-x_0=\dfrac{b}{d}k$ en revenant à l'égalité de départ. Réciproquement, tout couple de cette forme est bien solution.

Méthode et exemple complet. Résolvons dans $\mathbb{Z}^2$ l'équation $91x+39y=65$.

1. Existence. Algorithme d'Euclide : $91 = 2\times39+13$ puis $39=3\times13+0$, donc $\text{PGCD}(91,39)=13$. Comme $65 = 5\times13$, on a $13 \mid 65$ : l'équation admet des solutions.

2. Solution particulière (Bézout). En isolant le reste de la première ligne : $13 = 91 - 2\times39$, donc $91\times1 + 39\times(-2) = 13$. En multipliant par $k=65/13=5$ : $91\times5 + 39\times(-10) = 65$. Une solution particulière est $(x_0,y_0)=(5,-10)$. Vérification : $91\times5=455$, $39\times(-10)=-390$, et $455-390=65$. ✓

3. Solution générale. Avec $d=13$, $\dfrac{b}{d}=\dfrac{39}{13}=3$ et $\dfrac{a}{d}=\dfrac{91}{13}=7$ :

$x = 5+3k, \qquad y = -10-7k, \qquad k \in \mathbb{Z}$

Vérification finale (dans l'équation d'origine). Pour tout $k$ : $91(5+3k)+39(-10-7k) = 455+273k-390-273k = 65$. ✓ Par exemple, pour $k=-1$ : $(x,y)=(2,-3)$, et $91\times2+39\times(-3)=182-117=65$. ✓

Nombres premiers

Définition. Un entier $p \geqslant 2$ est premier si ses seuls diviseurs positifs sont $1$ et $p$.

Exemples. $2, 3, 5, 7, 11, 13, 17, \ldots$ sont premiers. Attention : $1$ n'est pas premier (il n'a qu'un seul diviseur positif), et $2$ est le seul nombre premier pair.

Propriété (admise). Tout entier $n \geqslant 2$ possède au moins un diviseur premier.

Théorème (décomposition en facteurs premiers, admis). Tout entier $n \geqslant 2$ se décompose de manière unique (à l'ordre des facteurs près) en un produit de nombres premiers :

$$n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}$$

Exemple. $360 = 2^3 \times 3^2 \times 5$.

Lien avec le PGCD. Le PGCD de deux entiers peut aussi se calculer à partir de leurs décompositions en facteurs premiers : on prend les facteurs premiers communs, chacun affecté du plus petit exposant apparaissant dans les deux décompositions.

Propriété (lemme d'Euclide, admise). Si $p$ est un nombre premier et si $p$ divise un produit $ab$ (avec $a, b$ entiers), alors $p$ divise $a$ ou $p$ divise $b$. En particulier, si $p$ divise $b^2$, alors $p$ divise $b$.

Test de primalité. Pour savoir si un entier $n \geqslant 2$ est premier, il suffit de tester s'il est divisible par un entier compris entre $2$ et $\sqrt{n}$ : si aucun de ces entiers ne le divise, $n$ est premier.

Remarque (culture mathématique). Il existe une infinité de nombres premiers, un résultat démontré par Euclide il y a plus de deux mille ans.

Définition

Soit $n \geqslant 2$ un entier naturel, et $a, b$ deux entiers relatifs. On dit que $a$ et $b$ sont congrus modulo $n$, et on note $a \equiv b \, [n]$ (ou $a \equiv b \pmod{n}$), si $a$ et $b$ ont le même reste dans la division euclidienne par $n$.

Exemples. $11 = 4 \times 2 + 3$ et $7 = 4 \times 1 + 3$ ont le même reste $3$ dans la division par $4$, donc $11 \equiv 7 \, [4]$. De même, $38 \equiv 14 \, [12]$ (tous deux de reste $2$ dans la division par $12$).

Si l'on compte de $6$ en $6$ à partir de $5$, tous les entiers obtenus sont congrus à $5$ modulo $6$ : $\ldots, -7, -1, 5, 11, 17, 23, \ldots$

Propriétés

Soit $n \geqslant 2$ un entier, $a, b$ deux entiers relatifs.

1. $a \equiv b \, [n] \iff n \mid (a-b)$.

2. En particulier (cas $b=0$) : $a \equiv 0 \, [n] \iff n \mid a$.

3. Si $n' \geqslant 2$ divise $n$, alors $a \equiv b \, [n] \implies a \equiv b \, [n']$.

Démonstration du point 1. Si $a \equiv b \, [n]$, il existe $q, q', r$ tels que $a = nq+r$ et $b = nq'+r$ (même reste $r$), donc $a - b = n(q-q')$, soit $n \mid (a-b)$. Réciproquement, si $n \mid (a-b)$, il existe $k$ tel que $a = b + kn$ ; en écrivant $b = nq+r$ avec $0 \leqslant r < n$, on obtient $a = n(q+k)+r$, qui est la division euclidienne de $a$ par $n$ de même reste $r$ : donc $a \equiv b \, [n]$.

Congruence et division euclidienne

Propriété. Tout entier relatif $a$ est congru modulo $n$ à un unique entier $r$ tel que $0 \leqslant r \leqslant n-1$ : il s'agit précisément du reste de la division euclidienne de $a$ par $n$.

Compatibilité avec les opérations

Théorème. La relation de congruence modulo $n$ est compatible avec l'addition et la multiplication : si $a \equiv a' \, [n]$ et $b \equiv b' \, [n]$, alors

$$a+b \equiv a'+b' \, [n] \quad \text{et} \quad ab \equiv a'b' \, [n]$$

Conséquences. Pour tout entier $k$ : si $a \equiv a' \, [n]$ alors $ka \equiv ka' \, [n]$. Pour tout entier naturel $p \geqslant 1$ : si $a \equiv a' \, [n]$ alors $a^p \equiv a'^{\,p} \, [n]$ (on le démontre par récurrence sur $p$, en appliquant la compatibilité avec la multiplication à chaque étape).

Attention ! On ne peut pas « simplifier » une congruence comme une égalité. Par exemple $16 \equiv 20 \, [4]$, mais $8 \not\equiv 10 \, [4]$ (on n'a pas le droit de diviser les deux membres par $2$).

Petit théorème de Fermat

Théorème (petit théorème de Fermat, admis). Soit $p$ un nombre premier et $a$ un entier relatif. Si $p$ ne divise pas $a$, alors :

$a^{p-1} \equiv 1 \, [p]$

Corollaire. Pour tout entier relatif $a$ (y compris lorsque $p$ divise $a$) :

$a^{p} \equiv a \, [p]$

Démonstration du corollaire. Si $p \nmid a$, on multiplie les deux membres de $a^{p-1}\equiv1\,[p]$ par $a$ : $a^p \equiv a\,[p]$. Si $p \mid a$, alors $a \equiv 0\,[p]$, donc $a^p \equiv 0 \equiv a \,[p]$ également (compatibilité des congruences avec les puissances). Dans les deux cas, $a^p\equiv a\,[p]$.

Exemple. Retrouvons, à l'aide du petit théorème de Fermat, le reste de la division euclidienne de $2^{10}$ par $7$ (déjà calculé dans le QCM de cette notion). Ici $p=7$ est premier et ne divise pas $a=2$, donc le théorème donne $2^{6} \equiv 1 \, [7]$ — ce que l'on vérifie directement : $2^6=64=9\times7+1$. On en déduit :

$2^{10} = 2^{6}\times2^{4} \equiv 1\times2^{4} = 16 \equiv 2 \, [7]$

Remarque — lien avec le QCM de cette notion. Le calcul du QCM utilisait l'observation $2^3\equiv1\,[7]$, plus fine que ce que garantit directement Fermat (qui n'assure que $2^6\equiv1\,[7]$, avec l'exposant $p-1=6$) — les deux sont d'ailleurs cohérentes : $2^6=(2^3)^2\equiv1^2=1\,[7]$. Mais le petit théorème de Fermat a l'avantage de s'appliquer systématiquement, avec l'exposant $p-1$, même quand aucun raccourci comme $2^3\equiv1\,[7]$ n'est visible à l'œil : c'est exactement le même résultat qui est retrouvé ci-dessus par cette méthode générale.

Application : critères de divisibilité

Les congruences permettent de justifier les critères de divisibilité usuels. Par exemple, pour le critère de divisibilité par $9$ :

Comme $10 \equiv 1 \, [9]$, la propriété des puissances donne $10^k \equiv 1 \, [9]$ pour tout entier $k \geqslant 0$. Si un entier $N$ s'écrit en base dix $N = a_p \times 10^p + a_{p-1} \times 10^{p-1} + \cdots + a_1 \times 10 + a_0$ (les $a_i$ étant ses chiffres), alors par compatibilité de la congruence avec l'addition et la multiplication :

$$N \equiv a_p + a_{p-1} + \cdots + a_1 + a_0 \, [9]$$

Autrement dit, $N$ est congru modulo $9$ à la somme de ses chiffres. En particulier, $N$ est divisible par $9$ si, et seulement si, la somme de ses chiffres l'est. Le même raisonnement (avec $10 \equiv 1 \, [3]$) justifie le critère de divisibilité par $3$.

On retrouve de la même manière les autres critères usuels : un entier est divisible par $2$ (resp. $5$, $10$) si son dernier chiffre est divisible par $2$ (resp. $5$, $10$), et divisible par $4$ si le nombre formé par ses deux derniers chiffres l'est.