Arithmétique dans Z : cours de maths en L1 en PDF.

Soient \(a\) et \(b\) deux entiers relatifs. On dit que \(b\) divise \(a\), et on note \(b \mid a\), s’il existe \(k \in \mathbb{Z}\) tel que \(a = kb\). On dit aussi que \(a\) est un multiple de \(b\), ou que \(b\) est un diviseur de \(a\). L’ensemble des multiples de \(b\) se note \(b\mathbb{Z}\).

Soient \(a, b, c\) des entiers relatifs.

• Réflexivité : \(a \mid a\). Transitivité : si \(a \mid b\) et \(b \mid c\), alors \(a \mid c\).
• Si \(a \mid b\) et \(b \mid a\), alors \(|a| = |b|\).
• Si \(d \mid a\) et \(d \mid b\), alors \(d \mid au + bv\) pour tous \(u, v \in \mathbb{Z}\).
• Si \(b \mid a\) et \(a \neq 0\), alors \(|b| \leq\, |a|\).

Montrons d’abord la combinaison linéaire. Si \(a = kd\) et \(b = \ell d\), alors \(au + bv = (ku + \ell v)d\), donc \(d\) divise \(au + bv\). Ensuite, si \(a = kb\) avec \(a \neq 0\), alors \(k \neq 0\), donc \(|k| \geq\, 1\) et \(|a| = |k|\,|b| \geq\, |b|\). Enfin, si \(a \mid b\) et \(b \mid a\), deux cas se présentent. Si \(a = 0\), alors \(b\) est multiple de \(0\), donc \(b = 0\). Sinon \(b \neq 0\) aussi, et l’inégalité précédente donne \(|a| \leq\, |b| \leq\, |a|\). La transitivité se prouve de la même façon.

Cherchons les entiers \(n\) tels que \(n + 2\) divise \(3n + 11\). Comme \(n + 2\) divise \(3(n+2)\), il divise la différence \(3n + 11 – 3(n + 2) = 5\). Par conséquent \(n + 2 \in \{-5, -1, 1, 5\}\), autrement dit \(n \in \{-7, -3, -1, 3\}\). Réciproquement, chacune de ces valeurs convient.

Soient \(a \in \mathbb{Z}\) et \(b \in \mathbb{N}^{*}\). Il existe un unique couple \((q, r) \in \mathbb{Z}^2\) tel que

\[a = bq + r \quad \text{et} \quad 0 \leq\, r < b.\]

L’entier \(q\) est le quotient et \(r\) le reste de la division euclidienne de \(a\) par \(b\).

Existence. Considérons l’ensemble \(E = \{a – bk \mid k \in \mathbb{Z}\} \cap \mathbb{N}\). Il est non vide : pour \(k = -|a|\), on a \(a + b|a| \geq\, a + |a| \geq\, 0\). Il possède donc un plus petit élément \(r = a – bq\). Par construction \(r \geq\, 0\). De plus, \(r – b = a – b(q+1)\) est strictement plus petit que \(r\), donc il n’appartient pas à \(E\). Ainsi \(r – b < 0\), c’est-à-dire \(r < b\).

Unicité. Supposons \(a = bq + r = bq^{\prime} + r^{\prime}\) avec \(0 \leq\, r, r^{\prime} < b\). Alors \(b(q – q^{\prime}) = r^{\prime} – r\), et \(|r^{\prime} – r| < b\). Donc \(b\) divise un entier de valeur absolue strictement inférieure à \(b\). D’après la propriété précédente, cet entier est nul. Par conséquent \(r = r^{\prime}\), puis \(q = q^{\prime}\).

Pour \(a = -23\) et \(b = 6\), on écrit \(-23 = 6 \times (-4) + 1\). Le quotient vaut donc \(-4\) et le reste \(1\). Attention, l’écriture \(-23 = 6 \times (-3) – 5\) ne convient pas, car le reste doit être positif.

Pour \(b \geq\, 1\), l’entier \(b\) divise \(a\) si et seulement si le reste de la division euclidienne de \(a\) par \(b\) est nul. De plus, tout entier s’écrit d’une unique façon \(bq + r\) avec \(r \in \{0, 1, \ldots, b – 1\}\).

Le PGCD de deux entiers \(a\) et \(b\) non tous deux nuls est le plus grand entier naturel qui divise à la fois \(a\) et \(b\). On le note \(a \wedge b\) ou \(\operatorname{pgcd}(a, b)\). Par convention, \(0 \wedge 0 = 0\). On dit que \(a\) et \(b\) sont premiers entre eux lorsque \(a \wedge b = 1\).

Soient \(a, b, q\) trois entiers. Alors les couples \((a, b)\) et \((b, a – bq)\) ont les mêmes diviseurs communs. En particulier, si \(r\) est le reste de la division de \(a\) par \(b \geq\, 1\), alors \(a \wedge b = b \wedge r\).

Posons \(r = a – bq\). Si \(d\) divise \(a\) et \(b\), alors \(d\) divise la combinaison \(a – bq = r\). Réciproquement, si \(d\) divise \(b\) et \(r\), alors \(d\) divise \(bq + r = a\). Les deux ensembles de diviseurs communs coïncident, donc leurs plus grands éléments aussi.

Pour calculer un PGCD par l’algorithme d’Euclide, on effectue des divisions euclidiennes successives : on divise \(a\) par \(b\), puis \(b\) par le reste, et ainsi de suite. Le PGCD est le dernier reste non nul. On présente les calculs ligne par ligne, afin de pouvoir remonter ensuite l’algorithme.

Calculons \(42 \wedge 15\). On écrit successivement :

\[\begin{aligned} 42 = 2 \times 15 + 12 \\ 15 = 1 \times 12 + 3 \\ 12 = 4 \times 3 + 0. \end{aligned}\]

Le dernier reste non nul vaut \(3\), donc \(42 \wedge 15 = 3\).

(Identité de Bézout.) Soient \(a\) et \(b\) deux entiers et \(d = a \wedge b\). Il existe des entiers \(u\) et \(v\) tels que \(au + bv = d\). De plus, l’ensemble \(a\mathbb{Z} + b\mathbb{Z} = \{au + bv \mid u, v \in \mathbb{Z}\}\) est exactement \(d\mathbb{Z}\).

Le cas \(a = b = 0\) est immédiat. Sinon, l’ensemble \(I = a\mathbb{Z} + b\mathbb{Z}\) contient un entier strictement positif, par exemple \(a^2 + b^2\). Soit \(\delta\) le plus petit élément strictement positif de \(I\), écrit \(\delta = au_0 + bv_0\). Divisons \(a\) par \(\delta\) : \(a = \delta q + r\) avec \(0 \leq\, r < \delta\). Alors \(r = a(1 – qu_0) + b(-qv_0)\) appartient à \(I\). Par minimalité de \(\delta\), on obtient \(r = 0\), donc \(\delta \mid a\). De même, \(\delta \mid b\), donc \(\delta \leq\, d\).

D’autre part, \(d\) divise \(a\) et \(b\), donc il divise \(au_0 + bv_0 = \delta\). Ainsi \(d \leq\, \delta\), puis \(\delta = d\). Enfin, tout élément de \(I\) est multiple de \(d\), et tout multiple \(kd = a(ku_0) + b(kv_0)\) est dans \(I\). Donc \(I = d\mathbb{Z}\).

Un entier \(d \geq\, 0\) divisant \(a\) et \(b\) est égal à \(a \wedge b\) si et seulement s’il existe \(u, v\) tels que \(au + bv = d\). De plus, tout diviseur commun de \(a\) et \(b\) divise \(a \wedge b\). Enfin, pour \(k \in \mathbb{N}\), on a \((ka) \wedge (kb) = k\,(a \wedge b)\).

(Théorème de Bézout.) Les entiers \(a\) et \(b\) sont premiers entre eux si et seulement s’il existe \(u, v \in \mathbb{Z}\) tels que \(au + bv = 1\).

Le sens direct découle de l’identité de Bézout avec \(d = 1\). Réciproquement, si \(au + bv = 1\), tout diviseur commun positif de \(a\) et \(b\) divise \(1\), donc vaut \(1\). Ainsi \(a \wedge b = 1\).

Pour déterminer des coefficients de Bézout, on remonte l’algorithme d’Euclide. On isole le dernier reste non nul dans l’avant-dernière division. Ensuite, on remplace chaque reste par son expression tirée de la division précédente. À la fin, on vérifie toujours l’égalité obtenue par un calcul direct.

Reprenons \(42 \wedge 15 = 3\). D’abord \(3 = 15 – 12\). Ensuite \(12 = 42 – 2 \times 15\). Par conséquent \(3 = 15 – (42 – 2 \times 15) = 3 \times 15 – 42\). On obtient \(u = -1\) et \(v = 3\), et l’on vérifie : \(-42 + 45 = 3\).

(Lemme de Gauss.) Soient \(a, b, c\) trois entiers. Si \(a\) divise \(bc\) et si \(a \wedge b = 1\), alors \(a\) divise \(c\).

D’après le théorème de Bézout, il existe \(u, v\) tels que \(au + bv = 1\). En multipliant par \(c\), on obtient \(c = acu + bcv\). Or \(a\) divise \(acu\), et \(a\) divise \(bcv\) puisqu’il divise \(bc\). Par conséquent \(a\) divise leur somme \(c\).

Si \(a \mid c\), \(b \mid c\) et \(a \wedge b = 1\), alors \(ab \mid c\). De plus, si \(a\) est premier avec \(b\) et avec \(c\), alors \(a\) est premier avec \(bc\).

Écrivons \(c = ak\). Alors \(b\) divise \(ak\) et \(b \wedge a = 1\), donc \(b \mid k\) par le lemme de Gauss. Ainsi \(k = b\ell\) et \(c = ab\ell\). Pour le second point, on multiplie deux relations \(au + bv = 1\) et \(au^{\prime} + cw = 1\). On obtient \(a(\ldots) + bc\,vw = 1\), ce qui conclut par le théorème de Bézout.

Soient \(a\) et \(b\) deux entiers non nuls. Le PPCM de \(a\) et \(b\), noté \(a \vee b\), est le plus petit entier strictement positif multiple à la fois de \(a\) et de \(b\).

Pour \(a, b \in \mathbb{N}^{*}\), on a \((a \wedge b) \times (a \vee b) = ab\). De plus, les multiples communs de \(a\) et \(b\) sont exactement les multiples de \(a \vee b\).

Posons \(d = a \wedge b\), \(a = da^{\prime}\) et \(b = db^{\prime}\). Alors \(a^{\prime} \wedge b^{\prime} = 1\), car \(d(a^{\prime} \wedge b^{\prime}) = a \wedge b = d\). Soit \(m\) un multiple commun de \(a\) et \(b\). On écrit \(m = da^{\prime}k\). Comme \(db^{\prime}\) divise \(da^{\prime}k\), on obtient \(b^{\prime} \mid a^{\prime}k\), puis \(b^{\prime} \mid k\) par le lemme de Gauss. Ainsi \(m\) est multiple de \(da^{\prime}b^{\prime}\). Réciproquement, \(da^{\prime}b^{\prime}\) est un multiple commun. Donc \(a \vee b = da^{\prime}b^{\prime}\), et \(d \times da^{\prime}b^{\prime} = ab\).

Soit \(d = a \wedge b\). L’équation \(ax + by = c\) a des solutions entières si et seulement si \(d \mid c\). Dans ce cas, on pose \(a = da^{\prime}\), \(b = db^{\prime}\), et l’on fixe une solution particulière \((x_0, y_0)\). Les solutions sont alors exactement les couples

\[(x, y) = (x_0 + kb^{\prime},\ y_0 – ka^{\prime}), \quad k \in \mathbb{Z}.\]

La condition \(d \mid c\) est nécessaire, car \(d\) divise \(ax + by\). Elle est suffisante : si \(c = dc^{\prime}\) et \(au + bv = d\), alors \((uc^{\prime}, vc^{\prime})\) est solution. Soit ensuite \((x, y)\) une solution. Par différence, \(a(x – x_0) = -b(y – y_0)\), puis, en divisant par \(d\), \(a^{\prime}(x – x_0) = -b^{\prime}(y – y_0)\). Ainsi \(b^{\prime}\) divise \(a^{\prime}(x – x_0)\), avec \(a^{\prime} \wedge b^{\prime} = 1\). Le lemme de Gauss donne \(x – x_0 = kb^{\prime}\), puis \(y – y_0 = -ka^{\prime}\). Réciproquement, ces couples sont bien solutions.

Pour résoudre une équation diophantienne \(ax + by = c\) : on calcule \(d = a \wedge b\) et l’on vérifie que \(d \mid c\) ; on divise l’équation par \(d\) ; on trouve une solution particulière, à vue ou par l’algorithme d’Euclide remonté ; enfin, on soustrait et on applique le lemme de Gauss.

Résolvons \(3x + 5y = 1\). On voit que \((2, -1)\) est solution, car \(6 – 5 = 1\). Les solutions sont donc les couples \((2 + 5k, -1 – 3k)\), avec \(k \in \mathbb{Z}\).

Un entier naturel \(p\) est premier s’il est supérieur ou égal à \(2\) et si ses seuls diviseurs positifs sont \(1\) et \(p\). Un entier \(n \geq\, 2\) non premier est dit composé.

Tout entier \(n \geq\, 2\) admet un diviseur premier : son plus petit diviseur \(p \geq\, 2\). Si \(n\) est composé, ce diviseur vérifie de plus \(p^2 \leq\, n\).

L’ensemble des diviseurs de \(n\) supérieurs ou égaux à \(2\) contient \(n\). Il a donc un plus petit élément \(p\). Si \(p\) avait un diviseur \(q\) avec \(1 < q < p\), alors \(q\) diviserait \(n\), ce qui contredirait la minimalité. Donc \(p\) est premier. Si \(n\) est composé, alors \(n = pm\) avec \(m \geq\, 2\) diviseur de \(n\). Par minimalité, \(m \geq\, p\), donc \(n \geq\, p^2\).

(Euclide.) Il existe une infinité de nombres premiers.

Supposons qu’il n’y en ait qu’un nombre fini, \(p_1, \ldots, p_k\). Posons \(N = p_1 p_2 \cdots p_k + 1 \geq\, 3\). D’après la proposition, \(N\) admet un diviseur premier \(p\), qui est l’un des \(p_i\). Alors \(p\) divise \(N\) et \(p_1 \cdots p_k\), donc il divise leur différence \(1\). C’est absurde, car \(p \geq\, 2\).

(Lemme d’Euclide.) Soit \(p\) premier. Pour tout entier \(a\), soit \(p \mid a\), soit \(p \wedge a = 1\). Par conséquent, si \(p\) divise un produit \(ab\), alors \(p\) divise \(a\) ou \(p\) divise \(b\).

Le PGCD \(p \wedge a\) est un diviseur positif de \(p\), donc il vaut \(1\) ou \(p\). S’il vaut \(p\), alors \(p \mid a\). Supposons maintenant \(p \mid ab\) et \(p \nmid a\). Alors \(p \wedge a = 1\), et le lemme de Gauss donne \(p \mid b\). Par récurrence, si \(p\) divise un produit de plusieurs facteurs, il divise l’un d’eux.

(Théorème fondamental de l’arithmétique.) Tout entier \(n \geq\, 2\) s’écrit comme produit de nombres premiers :

\[n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}, \quad p_1 < p_2 < \cdots < p_r \text{ premiers}, \quad \alpha_i \geq\, 1.\]

Cette écriture est unique.

Existence, par récurrence forte sur \(n\). Si \(n\) est premier, c’est fini. Sinon, \(n = ab\) avec \(2 \leq\, a, b < n\), et l’on multiplie les décompositions de \(a\) et de \(b\).

Unicité, par récurrence forte également. Supposons \(n = p_1 \cdots p_s = q_1 \cdots q_t\), avec des facteurs premiers répétés éventuellement. Le premier \(p_1\) divise le produit des \(q_j\). D’après le lemme d’Euclide, il divise l’un d’eux, disons \(q_j\). Comme \(q_j\) est premier, \(p_1 = q_j\). On simplifie par \(p_1\) et on applique l’hypothèse de récurrence à \(n / p_1 < n\).

Pour \(p\) premier et \(n \neq 0\), on note \(v_p(n)\) l’exposant de \(p\) dans la décomposition de \(|n|\) : c’est la valuation \(p\)-adique de \(n\). Elle vaut \(0\) si \(p \nmid n\), et \(v_p(ab) = v_p(a) + v_p(b)\).

Soient \(a, b \geq\, 1\). Alors \(a \mid b\) si et seulement si \(v_p(a) \leq\, v_p(b)\) pour tout \(p\) premier. De plus :

\[a \wedge b = \prod_{p} p^{\min(v_p(a), v_p(b))}, \qquad a \vee b = \prod_{p} p^{\max(v_p(a), v_p(b))}.\]

On a \(360 = 2^3 \times 3^2 \times 5\) et \(84 = 2^2 \times 3 \times 7\). Ainsi \(360 \wedge 84 = 2^2 \times 3 = 12\) et \(360 \vee 84 = 2^3 \times 3^2 \times 5 \times 7 = 2520\). On retrouve bien \(12 \times 2520 = 30240 = 360 \times 84\).

Soit \(n \geq\, 1\). Deux entiers \(a\) et \(b\) sont congrus modulo \(n\) si \(n\) divise \(a – b\). On note \(a \equiv b \ [n]\). Autrement dit, \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).

Si \(a \equiv b \ [n]\) et \(c \equiv d \ [n]\), alors \(a + c \equiv b + d \ [n]\) et \(ac \equiv bd \ [n]\). En particulier, \(a^k \equiv b^k \ [n]\) pour tout \(k \in \mathbb{N}\).

La somme découle de \((a + c) – (b + d) = (a – b) + (c – d)\). Pour le produit, on écrit \(ac – bd = a(c – d) + d(a – b)\), qui est une combinaison de multiples de \(n\). La puissance s’obtient par récurrence sur \(k\).

On ne peut pas simplifier librement une congruence. Par exemple, \(2 \times 3 \equiv 2 \times 8 \ [10]\), mais \(3 \not\equiv 8 \ [10]\). En revanche, si \(ac \equiv bc \ [n]\) et \(c \wedge n = 1\), alors \(a \equiv b \ [n]\) d’après le lemme de Gauss.

L’entier \(a\) possède un inverse modulo \(n\), c’est-à-dire un entier \(u\) tel que \(au \equiv 1 \ [n]\), si et seulement si \(a \wedge n = 1\). Dans ce cas, l’équation \(ax \equiv c \ [n]\) équivaut à \(x \equiv uc \ [n]\).

Dire que \(au \equiv 1 \ [n]\) revient à dire qu’il existe \(v\) tel que \(au + nv = 1\). D’après le théorème de Bézout, cela équivaut à \(a \wedge n = 1\). Ensuite, on multiplie \(ax \equiv c\) par \(u\) pour obtenir \(x \equiv uc\), et inversement par \(a\).

Pour calculer le reste de \(a^k\) modulo \(n\), on remplace d’abord \(a\) par un représentant petit, éventuellement négatif. Ensuite, on cherche une puissance \(a^m \equiv 1\) ou \(a^m \equiv -1\). On écrit enfin la division euclidienne \(k = mq + r\), ce qui donne \(a^k \equiv (a^m)^q a^r\).

Cherchons le reste de \(5^{2026}\) modulo \(13\). On a \(5^2 = 25 \equiv -1 \ [13]\), donc \(5^4 \equiv 1 \ [13]\). Or \(2026 = 4 \times 506 + 2\). Ainsi \(5^{2026} \equiv 5^2 \equiv -1 \equiv 12 \ [13]\). Le reste vaut donc \(12\).

Si \(p\) est premier et \(1 \leq\, k \leq\, p – 1\), alors \(p\) divise \(\binom\,{p}{k}\).

La formule du capitaine donne \(k \binom\,{p}{k} = p \binom\,{p-1}{k-1}\). Ainsi \(p\) divise \(k \binom\,{p}{k}\). Or \(p \wedge k = 1\), car \(1 \leq\, k < p\). Le lemme de Gauss conclut.

(Petit théorème de Fermat.) Soit \(p\) un nombre premier. Pour tout \(a \in \mathbb{Z}\), on a \(a^p \equiv a \ [p]\). Si de plus \(p \nmid a\), alors \(a^{p-1} \equiv 1 \ [p]\).

Montrons d’abord le résultat pour \(a \in \mathbb{N}\), par récurrence. Il est clair pour \(a = 0\). Supposons \(a^p \equiv a \ [p]\). La formule du binôme et le lemme donnent \((a + 1)^p \equiv a^p + 1 \ [p]\), car les termes intermédiaires sont multiples de \(p\). Donc \((a+1)^p \equiv a + 1 \ [p]\).

Pour \(a < 0\), on se ramène à un entier naturel \(a + mp\), congru à \(a\). Enfin, si \(p \nmid a\), alors \(p\) divise \(a(a^{p-1} – 1)\) et \(p \wedge a = 1\). Le lemme de Gauss donne \(p \mid a^{p-1} – 1\).

Calculons le reste de \(2^{100}\) modulo \(11\). Le petit théorème de Fermat donne \(2^{10} \equiv 1 \ [11]\). Or \(100 = 10 \times 10\), donc \(2^{100} \equiv 1 \ [11]\). Le reste vaut \(1\).

La réciproque est fausse. Par exemple, \(341 = 11 \times 31\) n’est pas premier, et pourtant \(2^{340} \equiv 1 \ [341]\). Le théorème de Fermat sert donc surtout à prouver qu’un nombre est composé, et à calculer des puissances.