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

Soient \(a, b \in \mathbb{Z}\). On dit que \(b\) divise \(a\), et l’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\). L’ensemble des multiples de \(b\) se note \(b\mathbb{Z}\).

• La relation \(\mid\) est réflexive et transitive sur \(\mathbb{Z}\).
• 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|\).

Si \(a = kd\) et \(b = \ell d\), alors \(au + bv = (ku + \ell v)d\). Ensuite, si \(a = kb\) avec \(a \neq 0\), alors \(k \neq 0\), donc \(|a| = |k|\,|b| \geq\, |b|\). Enfin, si \(a \mid b\) et \(b \mid a\) avec \(a \neq 0\), alors \(b \neq 0\) et l’on obtient \(|a| \leq\, |b| \leq\, |a|\). Le cas \(a = 0\) impose \(b = 0\).

(Division euclidienne) 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 plus, \(b \mid a\) si et seulement si \(r = 0\).

Existence : posons \(q = \lfloor a/b \rfloor\). Alors \(q \leq\, a/b < q + 1\), donc \(bq \leq\, a < bq + b\). Par conséquent \(r = a – bq\) vérifie \(0 \leq\, r < b\). Unicité : si \(bq + r = bq_1 + r_1\) avec les mêmes contraintes, alors \(b\,|q – q_1| = |r_1 – r| < b\). Donc \(|q – q_1| < 1\), d’où \(q = q_1\) puis \(r = r_1\).

Divisons \(-58\) par \(9\). On a \(-63 = 9 \times (-7)\) et \(-63 \leq\, -58 < -54\). Donc \(-58 = 9 \times (-7) + 5\) : le quotient vaut \(-7\) et le reste \(5\). Attention, l’écriture \(-58 = 9 \times (-6) – 4\) n’est pas la division euclidienne, car le reste doit être positif.

Soient \(a, b \in \mathbb{Z}\) non tous deux nuls. L’ensemble de leurs diviseurs communs est fini et contient \(1\). Son plus grand élément s’appelle le PGCD de \(a\) et \(b\), noté \(a \wedge b\). Par convention, \(0 \wedge 0 = 0\).

Si \(a = bq + r\) avec \(a, b, q, r \in \mathbb{Z}\), alors \(a\) et \(b\) ont les mêmes diviseurs communs que \(b\) et \(r\). En particulier \(a \wedge b = b \wedge r\).

Un diviseur commun de \(a\) et \(b\) divise \(r = a – bq\). Réciproquement, un diviseur commun de \(b\) et \(r\) divise \(a = bq + r\). Les deux ensembles de diviseurs communs coïncident, donc leurs plus grands éléments aussi.

Pour calculer \(a \wedge b\), enchaînez les divisions euclidiennes en remplaçant le couple \((a, b)\) par \((b, r)\). Arrêtez-vous au premier reste nul : le PGCD est le reste précédent. Par exemple :

\[\begin{aligned} 42 = 1 \times 30 + 12,\\ 30 = 2 \times 12 + 6,\\ 12 = 2 \times 6 + 0. \end{aligned}\]

Donc \(42 \wedge 30 = 6\).

Soient \(a, b \in \mathbb{Z}^*\). Le plus petit élément de \(\mathbb{N}^*\) qui est multiple commun de \(a\) et \(b\) s’appelle le PPCM de \(a\) et \(b\), noté \(a \vee b\). Par convention, \(a \vee 0 = 0\).

Pour tous \(a, b \in \mathbb{Z}\), \(d \mid a\) et \(d \mid b\) équivaut à \(d \mid a \wedge b\). De même, \(a \mid m\) et \(b \mid m\) équivaut à \(a \vee b \mid m\). Enfin, pour \(a, b \in \mathbb{N}\) :

\[(a \wedge b)(a \vee b) = ab.\]

(Relation de Bézout) Soient \(a, b \in \mathbb{Z}\). Il existe \(u, v \in \mathbb{Z}\) tels que

\[au + bv = a \wedge b.\]

Un tel couple \((u, v)\) s’appelle un couple de Bézout. Il n’est pas unique.

Suivons l’algorithme d’Euclide. Montrons par récurrence que chaque reste \(r_k\) s’écrit \(au_k + bv_k\). C’est vrai pour \(r_0 = a\) avec \((1, 0)\) et pour \(r_1 = b\) avec \((0, 1)\). Ensuite, si \(r_{k+1} = r_{k-1} – q_k r_k\), alors on pose \(u_{k+1} = u_{k-1} – q_k u_k\) et \(v_{k+1} = v_{k-1} – q_k v_k\). Le dernier reste non nul, égal à \(a \wedge b\), est donc bien combinaison de \(a\) et \(b\).

Pour trouver un couple de Bézout de \(a\) et \(b\), écrivez trois colonnes \(r_k\), \(u_k\), \(v_k\). Démarrez avec les lignes \((a, 1, 0)\) et \((b, 0, 1)\). Ensuite, chaque nouvelle ligne vaut « ligne d’avant-hier moins \(q_k\) fois ligne d’hier ». Par exemple, pour \(a = 42\) et \(b = 30\) :

\[\begin{array}{c|c|c|c} q_k r_k u_k v_k \\ \hline 42 1 0 \\ 30 0 1 \\ 1 12 1 -1 \\ 2 6 -2 3 \end{array}\]

On lit \(42 \times (-2) + 30 \times 3 = 6\). Vérifiez toujours l’égalité finale.

Deux entiers \(a\) et \(b\) sont dits premiers entre eux si \(a \wedge b = 1\), autrement dit si leurs seuls diviseurs communs sont \(1\) et \(-1\).

(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 est la relation de Bézout. Réciproquement, si \(au + bv = 1\), tout diviseur commun de \(a\) et \(b\) divise \(1\). Par conséquent \(a \wedge b = 1\).

(Lemme de Gauss) Soient \(a, b, c \in \mathbb{Z}\). Si \(a \mid bc\) et \(a \wedge b = 1\), alors \(a \mid c\).

Écrivons \(au + bv = 1\). En multipliant par \(c\), il vient \(c = acu + bcv\). Or \(a\) divise \(acu\) et \(bcv\), donc \(a\) divise \(c\).

• Si \(a \mid n\), \(b \mid n\) et \(a \wedge b = 1\), alors \(ab \mid n\).
• Si \(a \wedge b = 1\) et \(a \wedge c = 1\), alors \(a \wedge bc = 1\).
• Si \(d = a \wedge b \neq 0\), alors \(a = da^{\prime}\) et \(b = db^{\prime}\) avec \(a^{\prime} \wedge b^{\prime} = 1\).

L’hypothèse \(a \wedge b = 1\) est indispensable. Par exemple, \(6 \mid 4 \times 3\) mais \(6\) ne divise ni \(4\) ni \(3\). De même, \(4 \mid 12\) et \(6 \mid 12\) sans que \(24\) divise \(12\).

L’équation \(ax + by = c\) admet une solution entière si et seulement si \(d = a \wedge b\) divise \(c\). Dans ce cas, si \((x_0, y_0)\) est une solution, et si \(a = da^{\prime}\), \(b = db^{\prime}\), l’ensemble des solutions est

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

Si une solution existe, \(d\) divise \(ax + by = c\). Réciproquement, si \(c = dc^{\prime}\), un couple de Bézout \((u, v)\) donne la solution \((uc^{\prime}, vc^{\prime})\). Ensuite, si \((x, y)\) est solution, on soustrait : \(a(x – x_0) = -b(y – y_0)\). En divisant par \(d\), on obtient \(a^{\prime}(x – x_0) = -b^{\prime}(y – y_0)\). Or \(a^{\prime} \wedge b^{\prime} = 1\), donc le lemme de Gauss donne \(b^{\prime} \mid x – x_0\). On écrit \(x = x_0 + kb^{\prime}\), puis on trouve \(y = y_0 – ka^{\prime}\). Enfin, ces couples sont bien solutions.

Résolvons \(3x + 5y = 7\). D’abord, \(3 \times 2 + 5 \times (-1) = 1\), donc \((14, -7)\) est solution. Une solution plus simple est \((-1, 2)\), car \(-3 + 10 = 7\). Ainsi, les solutions sont les couples \((-1 + 5k, 2 – 3k)\) avec \(k \in \mathbb{Z}\).

Le PGCD de \(a_1, \ldots, a_n\) est défini par récurrence : \(a_1 \wedge \cdots \wedge a_n = (a_1 \wedge \cdots \wedge a_{n-1}) \wedge a_n\). Les entiers sont premiers entre eux dans leur ensemble si ce PGCD vaut \(1\). Ils sont premiers entre eux deux à deux si \(a_i \wedge a_j = 1\) pour tous \(i \neq j\).

Les entiers \(6, 10, 15\) sont premiers entre eux dans leur ensemble, car \(6 + 10 – 15 = 1\). Cependant, ils ne sont pas premiers entre eux deux à deux, puisque \(6 \wedge 10 = 2\). Enfin, si \(a_1, \ldots, a_n\) sont premiers entre eux deux à deux et divisent tous \(N\), alors leur produit divise \(N\).

Un entier \(p \geq\, 2\) est premier si ses seuls diviseurs positifs sont \(1\) et \(p\). On note \(\mathcal{P}\) l’ensemble des nombres premiers.

• Tout entier \(n \geq\, 2\) admet un diviseur premier.
• Si \(n \geq\, 2\) n’est pas premier, il admet un diviseur premier \(p\) tel que \(p^2 \leq\, n\).
• Si \(p\) est premier et \(p \nmid a\), alors \(p \wedge a = 1\).
• (Lemme d’Euclide) Si \(p\) est premier et \(p \mid ab\), alors \(p \mid a\) ou \(p \mid b\).

Le plus petit diviseur \(d \geq\, 2\) de \(n\) existe et il est premier. En effet, un diviseur de \(d\) compris strictement entre \(1\) et \(d\) diviserait \(n\). Si de plus \(n = dm\) n’est pas premier, alors \(m \geq\, d\), donc \(d^2 \leq\, dm = n\). Ensuite, \(p \wedge a\) divise \(p\) : il vaut \(1\) ou \(p\), et il vaut \(1\) si \(p \nmid a\). Enfin, le lemme d’Euclide découle alors du lemme de Gauss.

(Euclide) L’ensemble des nombres premiers est infini.

Supposons \(\mathcal{P}\) fini, égal à \(\{p_1, \ldots, p_r\}\). Posons \(N = p_1 p_2 \cdots p_r + 1 \geq\, 2\). D’après la proposition, \(N\) admet un diviseur premier \(p_i\). Or \(p_i\) divise aussi le produit \(p_1 \cdots p_r\). Donc \(p_i\) divise \(1\), ce qui est absurde.

Dans le crible, il suffit de barrer les multiples des nombres premiers \(p\) tels que \(p^2 \leq\, N\). En effet, un nombre composé \(n \leq\, N\) possède un diviseur premier \(p\) avec \(p^2 \leq\, n\). De plus, pour chaque \(p\), on peut commencer à barrer à partir de \(p^2\). Pour \(N = 100\), seuls \(2, 3, 5, 7\) servent.

(Théorème fondamental de l’arithmétique) Tout entier \(n \geq\, 2\) s’écrit de façon unique, à l’ordre près des facteurs, comme produit de nombres premiers :

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

Existence, par récurrence forte : si \(n\) est premier, c’est fini. Sinon \(n = ab\) avec \(2 \leq\, a, b < n\), et on concatène les décompositions de \(a\) et \(b\). Unicité : supposons \(p_1 \cdots p_k = q_1 \cdots q_\ell\) avec des facteurs premiers. Alors \(p_1\) divise le produit des \(q_j\). Par le lemme d’Euclide, il divise l’un d’eux, donc il lui est égal. On simplifie, puis on conclut par récurrence sur \(k\).

Soient \(p\) premier et \(n \in \mathbb{Z}^*\). La valuation \(p\)-adique de \(n\), notée \(v_p(n)\), est le plus grand entier \(\alpha\) tel que \(p^\alpha \mid n\). Ainsi, \(|n| = \prod_{p \in \mathcal{P}} p^{v_p(n)}\), produit dans lequel presque tous les exposants sont nuls.

Pour tous \(a, b \in \mathbb{Z}^*\) et tout \(p\) premier :

• \(v_p(ab) = v_p(a) + v_p(b)\) ;
• \(a \mid b\) si et seulement si \(v_p(a) \leq\, v_p(b)\) pour tout \(p\) premier ;
• \(v_p(a \wedge b) = \min(v_p(a), v_p(b))\) et \(v_p(a \vee b) = \max(v_p(a), v_p(b))\).

La première égalité vient de l’unicité de la décomposition. Ensuite, si \(b = ak\), alors \(v_p(b) = v_p(a) + v_p(k) \geq\, v_p(a)\). Réciproquement, si les inégalités sont vraies, \(k = \prod p^{v_p(b) – v_p(a)}\) convient. Enfin, un entier \(d\) divise \(a\) et \(b\) si et seulement si \(v_p(d) \leq\, \min(v_p(a), v_p(b))\) pour tout \(p\). Le plus grand est obtenu avec l’égalité. Le raisonnement est symétrique pour le PPCM.

On a \(360 = 2^3 \times 3^2 \times 5\) et \(84 = 2^2 \times 3 \times 7\). Donc \(360 \wedge 84 = 2^2 \times 3 = 12\) et \(360 \vee 84 = 2^3 \times 3^2 \times 5 \times 7 = 2520\). On vérifie que \(12 \times 2520 = 30240 = 360 \times 84\).

Pour les grands nombres, l’algorithme d’Euclide est bien plus rapide que la factorisation. En effet, on ne connaît pas d’algorithme efficace pour factoriser un entier de plusieurs centaines de chiffres. C’est d’ailleurs sur cette difficulté que repose le chiffrement RSA.

Soit \(n \in \mathbb{N}^*\). On dit que \(a\) est congru à \(b\) modulo \(n\), et l’on note \(a \equiv b \ [n]\), si \(n \mid a – b\). De façon équivalente, \(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]\). Par conséquent, \(a^k \equiv b^k \ [n]\) pour tout \(k \in \mathbb{N}\).

On a \((a + c) – (b + d) = (a – b) + (c – d)\), qui est multiple de \(n\). Ensuite, \(ac – bd = a(c – d) + d(a – b)\), qui est aussi multiple de \(n\). La propriété sur les puissances s’obtient par récurrence sur \(k\).

On ne simplifie pas une congruence comme une égalité. Par exemple, \(2 \times 3 \equiv 2 \times 8 \ [10]\), mais \(3 \not\equiv 8 \ [10]\). La simplification par \(a\) n’est permise que si \(a \wedge n = 1\).

Un entier \(a\) est inversible modulo \(n\) s’il existe \(u \in \mathbb{Z}\) tel que \(au \equiv 1 \ [n]\). Un tel \(u\) s’appelle un inverse de \(a\) modulo \(n\).

L’entier \(a\) est inversible modulo \(n\) si et seulement si \(a \wedge n = 1\). Dans ce cas, pour tout \(b\), la congruence \(ax \equiv b \ [n]\) équivaut à \(x \equiv ub \ [n]\), où \(u\) est un inverse de \(a\).

Dire que \(au \equiv 1 \ [n]\), c’est 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, si \(ax \equiv b\), on multiplie par \(u\) et l’on obtient \(x \equiv ub\). Réciproquement, si \(x \equiv ub\), alors \(ax \equiv aub \equiv b\).

Résolvons \(7x \equiv 3 \ [12]\). D’abord, \(7 \times 7 = 49 = 4 \times 12 + 1\), donc \(7\) est son propre inverse modulo \(12\). Par conséquent \(x \equiv 21 \equiv 9 \ [12]\). On vérifie : \(7 \times 9 = 63 = 5 \times 12 + 3\).

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

On a \(k\binom\,{p}{k} = p\binom\,{p-1}{k-1}\). Ainsi, \(p\) divise \(k\binom\,{p}{k}\). Or \(p \wedge k = 1\) puisque \(1 \leq\, k < p\). Le lemme de Gauss donne donc \(p \mid \binom\,{p}{k}\).

(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 \(a^p \equiv a\) par récurrence pour \(a \in \mathbb{N}\). C’est clair pour \(a = 0\). Ensuite, la formule du binôme et le lemme donnent \((a + 1)^p \equiv a^p + 1 \ [p]\). Donc \((a + 1)^p \equiv a + 1\) si \(a^p \equiv a\). Pour \(a < 0\), on remplace \(a\) par un entier positif qui lui est congru. Enfin, si \(p \nmid a\), alors \(p \wedge a = 1\), et l’on simplifie \(a \cdot a^{p-1} \equiv a \cdot 1\) par \(a\).

Pour réduire \(a^N\) modulo un premier \(p\) ne divisant pas \(a\), faites la division euclidienne \(N = (p – 1)q + r\). Alors \(a^N = (a^{p-1})^q a^r \equiv a^r \ [p]\). Par exemple, \(3^{100} \equiv 3^{4} = 81 \equiv 4 \ [7]\), car \(100 = 6 \times 16 + 4\).

Le théorème fournit aussi un inverse : si \(p \nmid a\), alors \(a^{p-2}\) est un inverse de \(a\) modulo \(p\). Cependant, l’algorithme d’Euclide étendu reste en général plus rapide. Hors programme, le théorème se généralise en \(a^{\varphi(n)} \equiv 1 \ [n]\) lorsque \(a \wedge n = 1\), résultat étudié en spé.