Arithmétique dans Z

Preuve. Montrons par exemple les résultats 3) et 7) :

• Pour le résultat 3) : supposons que $a \mid b$ et $b \mid c$ ; il existe donc $(k ; k') \in \mathbb{Z}^2$ tel que $b = ak$ et $c = bk'$. Il s'ensuit donc que $c = akk'$. Par suite : $a \mid c$ car $kk' \in \mathbb{Z}$.
• Pour le résultat 7) : supposons que $a \mid b$ et $a \mid c$ ; il existe donc $(k_1 ; k_2) \in \mathbb{Z}^2$ tel que $b = a k_1$ et $c = a k_2$. Il s'ensuit donc que : $\alpha b + \beta c = \alpha a k_1 + \beta a k_2 = a(\alpha k_1 + \beta k_2)$. Par suite : $a \mid \alpha b + \beta c$

Preuve. Soit $a$ et $b$ deux éléments de $\mathbb{Z}$ tels que : $a \neq 0$. On suppose que $a > 0$.

• Si $b \ge 0$ alors $b \in \mathbb{N}$ et d'après le théorème précédent on aura :
  \[(\exists! (q;r) \in \mathbb{N}^2) : b = aq+r \text{et} 0 \le r < a\]
• Si $b < 0$ alors $-b \in \mathbb{N}^*$ et d'après le théorème précédent on aura :
  \[(\exists! (q';r') \in \mathbb{N}^2) : -b = aq' + r' \text{et} 0 \le r' < a\]
  • Si $r' = 0$ alors : $-b = aq'$, c'est-à-dire que $b = a(-q') + 0$. On obtient l'unique couple $(-q';0)$.
  • Si $r' \neq 0$ alors $0 < r' < a$ et donc $-a < -r' < 0$, c'est-à-dire que : $0 < a – r' < a$. et en posant : $r = a – r'$ et $q = -(q' + 1)$, on obtient : $b = aq + r \text{et} 0 \le r < a$. Puisque $q'$ et $r'$ sont uniques, alors il en est de même pour $q$ et $r$.

De la même façon, on montre le théorème pour $a < 0$ (à vérifier). D'où le résultat.

Preuve. Soit $n \in \mathbb{N}^* – \{1\}$ un nombre non premier et $p$ le plus petit diviseur positif de $n$ distinct de $1$. D'après la proposition précédente, le nombre $p$ est premier et de plus : $\big( \exists k \in \mathbb{N}^* \big) \; n = pk$. Puisque $k$ est un diviseur de $n$ et $k \neq 1$, alors $p \le k$, ce qui donne : $p^2 \le n$. D'où le résultat. Voici deux questions qui se posent naturellement :

• Comment savoir si un entier $N \ge 2$ est premier ? La proposition ci-dessus donne une réponse : On dresse la liste des nombres premiers $p$ tels que $p^2 \le N$, c'est-à-dire $p \le E(\sqrt{N})$ ($x \mapsto E(x)$ est la fonction partie entière). Alors $N$ est premier si, et seulement s'il n'est multiple d'aucun des nombres obtenus. À titre d'exemple : Montrons que le nombre $2017$ est premier. D'abord $E(\sqrt{2017}) = 44$. Les nombres premiers inférieures ou égales à $44$ sont :
  \[2 – 3 – 5 – 7 – 11 – 13 – 17 – 19 – 23 – 29 – 31 – 37 – 41 – 43\]
  Par division euclidienne ou critère de divisibilité, on vérifie qu'aucun de ces nombres ne divise $2017$. Donc, $2017$ est un nombre premier.
• Soit $N \ge 2$ un entier donné, comment trouver tous les nombres premiers inférieurs ou égaux à $N$ ? Le crible d'Ératosthène fournit une méthode. Dans la liste des entiers de $2$ à $N$, on supprime tous les multiples de $2$, puis tous les multiples de $3$, et ainsi de suite. Après avoir supprimé tous les multiples d'un certain entier, le plus petit des entiers qui restent dans la liste, s'il y en a, est premier, et tous les nombres premiers entre $2$ et $N$ sont obtenus successivement par ce procédé.

Preuve. De très nombreuses preuves de ce résultat existent. Proposons ici la démonstration d'Euclide, sans doute la plus connue, en raisonnant par l'absurde. Supposons que l'ensemble $\mathbb{P}$ soit fini. On peut alors écrire $\mathbb{P} = \{p_1; p_2; \dots ; p_k\}$. D'après le théorème précédent, l'entier $N = p_1 \cdot p_2 \dots p_k + 1$ admet au moins un facteur premier $p$. Ce nombre premier est donc l'un des $p_i$. On a alors $p \mid N$ et $p \mid p_1 \cdot p_2 \dots p_k$, il s'ensuit donc que $p \mid N – p_1 \cdot p_2 \dots p_k$, c'est-à-dire $p \mid 1$, ce qui est impossible. L'hypothèse de départ est donc fausse.

Preuve. Soit $n$ un entier naturel supérieur ou égal à $2$. On a alors la discussion suivante :

• Si $n$ est premier, alors : $n = n$.
• Si $n$ n'est pas premier, alors le plus petit diviseur positif $p_1$ de $n$ distinct de $1$ est premier ; d'où $n = p_1 q_1$.
  • Si $q_1$ est premier, alors $n = p_1 q_1$ et donc $n$ est le produit de deux nombres premiers.
  • Si $q_1$ n'est pas premier, alors le plus petit diviseur $p_2$ de $n$ distinct de $1$ est premier ; il s'ensuit que $q_1 = p_2 . q_2$ et donc $n = p_1 . p_2 . q_2$. On a à nouveau deux cas : $q_2$ premier ou non premier et ainsi de suite.

On en déduit de ce qui précède que tout entier naturel $n \ge 2$ peut s'écrire sous la forme : $n = p_1 p_2 \dots p_k$, où $p_1, p_2, \dots, p_k$ sont tous des nombres premiers (non nécessairement distincts). Par conséquent, tout entier naturel $n \ge 2$ peut s'écrire sous la forme : $n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$ où $p_1, p_2, \dots, p_k$ sont des nombres premiers deux à deux distincts et $\alpha_1, \alpha_2, \dots, \alpha_k$ des entiers naturels non nuls. Dans le cas où $n \in \mathbb{Z}^- – \{0; 1\}$, on a : $-n \in \mathbb{N}^* – \{1\}$ et donc $-n$ s'écrit sous la forme : $-n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$, c'est-à-dire que $n = – p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$. On admet l'unicité de l'écriture $n = \varepsilon \, p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$.

Preuve.

• Les résultats 1), 2), 3), 4) et 7) sont des conséquences immédiates de la définition précédente.
• Le résultat 5) découle de fait que : $(D_a \cap D_b) \cap D_c = D_a \cap (D_b \cap D_c)$.
• Pour le résultat 6) : On suppose que $a \mid b$, donc : $(\exists k \in \mathbb{Z}) ; b=ak$. Par conséquent :
  \[D_a \cap D_b = D_a \cap D_{ka} = D_a \text{(car : } D_a \subset D_{ka})\]
  Il s'ensuit donc que : $a \mid b \implies a \wedge b = |a|$. Réciproquement, si $a \wedge b = |a|$ alors $|a| \mid b$, c'est-à-dire que : $a \mid b$. D'où : $a \mid b \iff a \wedge b = |a|$.

\begin{remarque} Pour tout $(x;y) \in \mathbb{N}^2$ :
$x \mid y \iff D_x \subset D_y$ \end{remarque}

Preuve. On a déjà démontré cette proposition dans l'activité 4 et ceci en utilisant l'égalité :

Preuve. Soit $a, b$ et $c$ des entiers relatifs non nuls et $n$ un entier naturel.

1. Si $c \mid a \wedge b$ alors $c \mid a$ et $c \mid b$ car $a \wedge b \mid a$ et $a \wedge b \mid b$. Par conséquent : $c \mid a \wedge b \implies (c \mid a \text{ et } c \mid b)$. La réciproque se découle immédiatement de la définition du plus grand commun diviseur.
2. Pour la relation $(ca) \wedge (cb) = |c|(a \wedge b)$, il suffit d'utiliser les décompositions des entiers $a$ et $b$ en produit de facteurs premiers.
3. Supposons que : $c \in D_a \cap D_b$. Il existe donc $(a' ; b') \in \mathbb{Z}^2$ tel que : $a = ca'$ et $b = cb'$. Il en résulte donc que : $a \wedge b = (ca') \wedge (cb') = |c| (a' \wedge b') = |c| (a' \wedge b')$ ; d'où : $\left(\dfrac{a}{c}\right) \wedge \left(\dfrac{b}{c}\right) = \dfrac{a \wedge b}{|c|}$.

Preuve. Tout diviseur $d$ commun de $a$ et $b$ s'écrit sous la forme : $d = p_1^{\gamma_1} p_2^{\gamma_2} \dots p_k^{\gamma_k}$ avec $0 \le \gamma_i \le \alpha_i$ et $0 \le \gamma_i \le \beta_i$ pour tout $i \in \{1 ; 2 ; \dots ; k\}$. Il s'ensuit donc que : $\gamma_i \le \inf(\alpha_i ; \beta_i)$. Comme : $(\inf(\alpha_i ; \beta_i) = \alpha_i \text{ si } \alpha_i \le \beta_i)$ et $(\inf(\alpha_i ; \beta_i) = \beta_i \text{ si } \alpha_i > \beta_i)$, alors :

Preuve.

• Les résultats 1), 2), 3) et 4) sont des conséquences de la définition et la remarque précédentes.
• Le résultat 5) découle de fait que : $(a\mathbb{Z} \cap b\mathbb{Z}) \cap c\mathbb{Z} = a\mathbb{Z} \cap (b\mathbb{Z} \cap c\mathbb{Z})$.
• Pour le résultat 6) : On sait que : $a \mid b \iff b\mathbb{Z} \subset a\mathbb{Z} \iff a\mathbb{Z} \cap b\mathbb{Z} = b\mathbb{Z}$. On en déduit donc que : $(a\mathbb{Z} \cap b\mathbb{Z}) \cap \mathbb{N}^* = b\mathbb{Z} \cap \mathbb{N}^*$. Ainsi : $a \mid b \iff a \vee b = |b|$.
• Pour le résultat 7) : On a le produit $ab$ est un multiple commun de $a$ et $b$ ; et par définition de $a \vee b$, on en déduit que $ab$ est un multiple de $a \vee b$, c'est-à-dire que : $a \vee b \mid ab$.

Preuve. Tout multiple $m$ commun de $a$ et $b$ s'écrit sous la forme : $m = p_1^{\gamma_1} p_2^{\gamma_2} \dots p_k^{\gamma_k} \times c$ avec $\alpha_i \le \gamma_i$ et $\beta_i \le \gamma_i$ pour tout $i \in \{1 ; 2 ; \dots ; k\}$ et $c \in \mathbb{N}^*$. Il s'ensuit donc que : $\gamma_i \ge \sup(\alpha_i ; \beta_i)$. Comme : $(\sup(\alpha_i ; \beta_i) = \alpha_i \text{ si } \alpha_i \ge \beta_i)$ et $(\sup(\alpha_i ; \beta_i) = \beta_i \text{ si } \alpha_i < \beta_i)$, alors :

Preuve. Si $d$ est un diviseur de $a$ alors $d$ s'écrit sous la forme : $d = p_1^{\beta_1} p_2^{\beta_2} \dots p_k^{\beta_k}$ avec $0 \le \beta_i \le \alpha_i$ et $i \in \{1 ; 2 ; \dots ; k\}$. Par conséquent, le nombre de diviseurs positifs de $a$ est le nombre des entiers $d$ lorsque $\beta_i$ varie sur l'ensemble $\{0 ; 1 ; \dots ; \alpha_i\}$. Dans ce cas, il y a $1 + \alpha_i$ choix pour la valeur de $\beta_i$. Enfin, et d'après le principe fondamental de dénombrement, le nombre total des diviseurs de $a$ vaut : $(1 + \alpha_1)(1 + \alpha_2) \dots (1 + \alpha_n)$. Signalons au passage que le nombre de diviseurs de $a$ dans $\mathbb{Z}$ est : $2(1 + \alpha_1)(1 + \alpha_2) \dots (1 + \alpha_n)$.

Preuve. Soit $a, b$ et $c$ des entiers relatifs et $n \in \mathbb{N}^*$.

1. [1)] On a : $n \mid a – a$ car $n \mid 0$ ; donc : $a \equiv a \pmod{n}$.
2. [2)] On a : $a \equiv b \pmod{n} \iff n \mid a – b \iff n \mid b – a \iff b \equiv a \pmod{n}$. Par suite : $a \equiv b \pmod{n} \iff b \equiv a \pmod{n}$
3. [3)] On a : $\begin{cases} a \equiv b \pmod{n}
   b \equiv c \pmod{n} \end{cases} \implies \begin{cases} n \mid a – b
   n \mid b – c \end{cases} \implies n \mid (a – b) + (b – c) \implies n \mid a – c$. Par suite : $a \equiv c \pmod{n}$.

Preuve. Soit $n$ un entier naturel non nul et $(a ; b ; c ; d) \in \mathbb{Z}^4$.

1. [1)] On pose : $a = nq_1 + r_1$ et $b = nq_2 + r_2$ avec $0 \le r_1 < n$ et $0 \le r_2 < n$. Si $r_1 = r_2$ alors : $a – b = nq_1 + r_1 – nq_2 – r_1 = n(q_1 – q_2)$. Par conséquent : $a \equiv b \pmod{n}$. Réciproquement : si $a \equiv b \pmod{n}$ alors il existe $k \in \mathbb{Z}$ tel que : $a – b = kn$. Il en résulte donc que : $r_1 – r_2 = (k – q_1 – q_2)n$, ce qui montre bien que $n \mid r_1 – r_2$. Comme $0 \le r_1 < n$ et $0 \le r_2 < n$ alors $|r_1 – r_2| < n$ ; d'où $r_1 – r_2 = 0$, c'est-à-dire que : $r_1 = r_2$.
2. [2)] Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors : $n \mid b – a$ et $n \mid d – c$ ; d'où : $n \mid (b – a) + (d – c)$, c'est-à-dire que : $n \mid (b + d) – (a + c)$. Ainsi : $a + c \equiv b + d \pmod{n}$. On a : $bd – ac = bd – bc + bc – ac = b(d – c) + c(b – a)$. Comme : $n \mid b – a$ et $n \mid d – c$ alors : $n \mid b(d – c) + c(b – a)$ ; c'est-à-dire que : $ac \equiv bd \pmod{n}$.
3. [3)] Soit $k \in \mathbb{Z}$. Si $a \equiv b \pmod{n}$ alors $n \mid b – a$ ; donc : $n \mid k(b – a)$, c'est-à-dire que : $ka \equiv kb \pmod{n}$.
4. [4)] Soit $(a;b) \in \mathbb{Z}^2$ tel que $a \equiv b \pmod{n}$. Montrons par récurrence que pour tout $p \in \mathbb{N} : a^p \equiv b^p \pmod{n}$. Initialisation : Pour $p = 0$, on a bien $a^0 \equiv b^0 \pmod{n}$ car $1 \equiv 1 \pmod{n}$. Hérédité : Soit $p \in \mathbb{N}$ fixé. Supposons que $a^p \equiv b^p \pmod{n}$ et montrons que $a^{p+1} \equiv b^{p+1} \pmod{n}$. On a par hypothèse : $a \equiv b \pmod{n}$ et $a^p \equiv b^p \pmod{n}$ ; donc d'après le résultat 2) : $a^p \times a \equiv b^p \times b \pmod{n}$ ce qui signifie que : $a^{p+1} \equiv b^{p+1} \pmod{n}$. Conclusion : Si $a \equiv b \pmod{n}$ et $p \in \mathbb{N}$, alors : $a^p \equiv b^p \pmod{n}$.