Cours d'arithmétique : divisibilité dans ℤ, division euclidienne, nombres premiers, PGCD, PPCM, théorèmes de Bézout, Gauss et Fermat, congruences et bases.
Soient $a$ et $b$ deux entiers relatifs tels que $b \neq 0$. On dit que l'entier relatif $b$ divise $a$ s'il existe un entier relatif $k$ tel que $a = kb$. On écrit $b \mid a$, et on dit que $a$ est divisible par $b$, ou que $a$ est un multiple de $b$.
Pour $a$, $b$, $c \in \mathbb{Z}$ :
Soient $a$ et $b$ deux entiers relatifs tels que $b \neq 0$. Il existe un entier relatif $q$ et un entier naturel $r$ tels que :
$$a = bq + r \quad \text{où} \quad 0 \leq r < |b|$$$a$ s'appelle le dividende, $b$ le diviseur, $q$ le quotient et $r$ le reste.
Remarque : si $r$ est le reste de la division euclidienne par $b$, alors $r \in \{0, 1, \dots, b - 1\}$.
On dit que l'entier $d$ est un diviseur effectif de l'entier relatif $a$ si $d \mid a$ et $|d| \neq 1$ et $|d| \neq |a|$.
On dit qu'un entier relatif non nul $p$ est premier s'il est différent de $1$ et s'il n'admet pas de diviseurs effectifs. Un nombre premier $p$ admet exactement deux diviseurs positifs : $1$ et $|p|$. Pour l'étude des nombres premiers, on se contente d'étudier les nombres premiers positifs.
Remarque : cette propriété permet de déterminer si un nombre est premier ou non.
L'ensemble des nombres premiers est infini.
On dit que le nombre $d$ est le plus grand commun diviseur de deux entiers relatifs $a$ et $b$ lorsque $d$ divise $a$ et $d$ divise $b$ et qu'il n'y a pas de plus grand diviseur commun de ces deux nombres. On note $d = \operatorname{PGCD}(a, b) = a \wedge b$.
On dit que deux entiers relatifs $a$ et $b$ sont premiers entre eux si $a \wedge b = 1$.
On dit que l'entier naturel $m$ est le plus petit commun multiple de deux entiers relatifs $a$ et $b$ lorsque $m$ est un multiple de $a$ et de $b$ et qu'il n'y a pas de plus petit multiple commun non nul de ces deux nombres. On note $m = \operatorname{PPCM}(a, b) = a \vee b$.
Soient $a$ et $b$ des entiers relatifs non nuls :
$$a \wedge b = d \iff \exists (\alpha, \beta) \in \mathbb{Z}^2 \ ; \ \begin{cases} a = \alpha d \\ b = \beta d \\ \alpha \wedge \beta = 1 \end{cases}$$ $$a \wedge b = d \Rightarrow \exists (u, v) \in \mathbb{Z}^2 \ ; \ d = au + bv$$Soient $a$ et $b$ des entiers relatifs non nuls :
$$a \wedge b = 1 \iff \exists (u, v) \in \mathbb{Z}^2 \ ; \ 1 = au + bv$$Soient $a$, $b$ et $c$ des entiers relatifs non nuls :
$$\begin{cases} c \mid ab \\ c \wedge a = 1 \end{cases} \Rightarrow c \mid b$$Soient $a$, $b$ et $c$ des entiers relatifs non nuls :
$$\begin{cases} a \mid c \ \text{et} \ b \mid c \\ a \wedge b = 1 \end{cases} \Rightarrow ab \mid c$$Soient $a$ et $b$ deux entiers relatifs et $n$ un entier naturel non nul. On dit que $a$ est congru à $b$ modulo $n$ si $n \mid (b - a)$. On écrit $a \equiv b \ [n]$.
La relation de congruence est donc une relation d'équivalence.
Soit $n$ un entier naturel non nul. Si $a \equiv b \ [n]$ et $c \equiv d \ [n]$, alors :
Si $a \equiv b \ [n]$ alors, pour tout $k$ dans $\mathbb{N}$ : $a^k \equiv b^k \ [n]$.
Soient $a$, $b$, $c$ des entiers relatifs non nuls, $n \in \mathbb{N}^*$ et $d = n \wedge c$ :
$$ac \equiv bc \ [n] \iff a \equiv b \ \left[\frac{n}{d}\right]$$ $$\begin{cases} ac \equiv bc \ [n] \\ c \wedge n = 1 \end{cases} \Rightarrow a \equiv b \ [n] \quad ; \quad \begin{cases} a \equiv b \ [n] \\ m \mid n \end{cases} \Rightarrow a \equiv b \ [m]$$ $$\begin{cases} ac \equiv bc \ [p] \\ p \text{ premier et } p \nmid c \end{cases} \Rightarrow a \equiv b \ [p]$$Soit $n$ un entier naturel non nul. L'ensemble des entiers relatifs qui ont le même reste $r$ dans la division euclidienne par $n$ s'appelle la classe d'équivalence de $r$, et se note :
$$\bar{r} = \{m \in \mathbb{Z} \ / \ m \equiv r \ [n]\} = \{nk + r \ \text{où} \ k \in \mathbb{Z}\}$$ $$\mathbb{Z}/n\mathbb{Z} = \{\bar{0}, \bar{1}, \bar{2}, \bar{3}, \dots, \overline{n-1}\} \quad \text{(ensemble quotient)}$$On définit dans $\mathbb{Z}/n\mathbb{Z}$ deux lois :
Si $p$ est premier, alors dans $\mathbb{Z}/p\mathbb{Z}$ on a : $\bar{a} \times \bar{b} = \bar{0} \iff \bar{a} = \bar{0}$ ou $\bar{b} = \bar{0}$.
Chaque entier relatif $m$ non nul s'écrit d'une façon unique comme le produit de facteurs premiers :
$$m = \varepsilon\, p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3} \times \dots \times p_n^{\alpha_n} = \varepsilon \prod_{k=1}^{n} p_k^{\alpha_k} \quad \text{où } \varepsilon \in \{-1, 1\}$$Soit $a = \varepsilon \displaystyle\prod_{k=1}^{n} p_k^{\alpha_k}$ un entier relatif.
Soient $a = \displaystyle\prod_{k=1}^{n} p_k^{\alpha_k}$ et $b = \displaystyle\prod_{k=1}^{n} p_k^{\beta_k}$ deux entiers. On a :
$$a \wedge b = \prod_{k=1}^{n} p_k^{\inf(\alpha_k, \beta_k)} \quad ; \quad a \vee b = \prod_{k=1}^{n} p_k^{\sup(\alpha_k, \beta_k)}$$L'équation $(E) : ax + by = c$ admet une solution si et seulement si $(a \wedge b) \mid c$.
Si le couple $(x_0, y_0)$ est une solution de $(E)$, alors l'ensemble des solutions de $(E)$ est :
$$S = \left\{\left(x_0 + \frac{kb}{a \wedge b} \ ; \ y_0 - \frac{ka}{a \wedge b}\right) \ ; \ k \in \mathbb{Z}\right\}$$Soient $a_1, a_2, \dots, a_n$ des entiers relatifs non nuls. Le plus grand entier naturel $d$ qui divise en même temps tous les nombres $a_1, a_2, \dots, a_n$ s'appelle le plus grand commun diviseur de ces nombres, et se note $d = a_1 \wedge a_2 \wedge \dots \wedge a_n$. On a :
$$a_1 \wedge a_2 \wedge \dots \wedge a_n = (a_1 \wedge a_2 \wedge \dots \wedge a_{n-2}) \wedge (a_{n-1} \wedge a_n)$$Si $d = a_1 \wedge a_2 \wedge \dots \wedge a_n$, alors il existe $(\alpha_i)_{1 \leq i \leq n}$ telle que $d = \displaystyle\sum_{i=1}^{n} \alpha_i a_i$.
De plus, $a_1 \wedge a_2 \wedge \dots \wedge a_n = 1$ si et seulement s'il existe $(\alpha_i)_{1 \leq i \leq n}$ telle que $1 = \displaystyle\sum_{i=1}^{n} \alpha_i a_i$.
On dit que les entiers relatifs non nuls $a_1, a_2, \dots, a_n$ sont premiers entre eux (dans leur ensemble) si $a_1 \wedge a_2 \wedge \dots \wedge a_n = 1$.
Soient $a_1, a_2, \dots, a_n$ des entiers relatifs non nuls. Le plus petit entier naturel $m$ qui est multiple en même temps de tous les nombres $a_1, a_2, \dots, a_n$ s'appelle le plus petit commun multiple de ces nombres, et se note $m = a_1 \vee a_2 \vee \dots \vee a_n$.
Si $p$ est un nombre premier et $a$ un entier relatif non nul et non divisible par $p$, alors $a^{p-1} - 1$ est divisible par $p$, c'est-à-dire :
$$\boxed{\ a^{p-1} \equiv 1 \ [p]\ } \qquad \text{ou encore} \qquad a^p \equiv a \ [p]$$Soit $b$ un entier naturel tel que $b > 1$. Chaque entier naturel non nul $n$ s'écrit d'une façon unique sous la forme :
$$n = a_m b^m + a_{m-1} b^{m-1} + \dots + a_1 b + a_0$$où les $(a_i)$ sont des entiers naturels tels que $0 \leq a_i \leq b - 1$ et $a_m \neq 0$. On note alors $n = \overline{a_m a_{m-1} \dots a_1 a_0}^{\,(b)}$ : c'est l'écriture de l'entier $n$ dans la base $b$.
Effectuer, dans la base 9 : $\overline{6432}^{\,(7)} \times \overline{54}^{\,(8)}$.
Solution.
$$\overline{6432}^{\,(7)} \times \overline{54}^{\,(8)} = (6 \times 7^3 + 4 \times 7^2 + 3 \times 7 + 2) \times (5 \times 8 + 4) = 100188$$ $$100188 = 1 \times 9^5 + 6 \times 9^4 + 2 \times 9^3 + 3 \times 9^2 + 8 \times 9 + 0$$ $$\boxed{\ \overline{6432}^{\,(7)} \times \overline{54}^{\,(8)} = \overline{162380}^{\,(9)}\ }$$Soit $x$ un entier naturel non nul tel que $x = a_n 10^n + a_{n-1} 10^{n-1} + \dots + a_1 10 + a_0$ où $0 \leq a_i \leq 9$. On a :
Un exercice de ce chapitre vous bloque ? Solutions pas à pas.