9 Arithmétique

#9 Arithmétique

$ \textbf{Compatibilité avec le produit} \\ \text{Si $k$ est premier avec $a_1, \dots, a_n$, alors $k$ est premier avec $a_1\dots a_n$} $

$\textbf{Lien entre diviseurs et multiples} \\ (\mathscr D(b) \subset \mathscr D(a)) \iff(b|a) \iff(a\mathbb Z \subset b\mathbb Z)$

$ \textbf{Division euclidienne} \\ \text{Avec $a \in \mathbb Z$ et $b \in \mathbb N$, il existe un unique $(q, r) \in (\mathbb Z \times [\![0;b[\![)$ tq} \\ a = bq + r $

$ \textbf{Idéaux de $\mathbb Z$} \\ \text{$\mathbb Z$ est principal} \\ \text{Ses idéaux sont exactement les $n\mathbb Z, n \in \mathbb N$} $

$ \textit{Caractérisation de la divisibilité par la DE} \\ \text{$b$ divise $a \iff$ le reste de la DE de $a$ par $b$ est nul} $

$ \textbf{Plus Grand Commun Diviseur} \\ \begin{array}{rl} \ \text{(i)} & \text{max$(\mathscr D(a) \cap \mathscr D(b))$ si $(a, b) \neq (0, 0)$} \\ \text{(ii)} & 0 \text{ sinon} \ \end{array} $

$ \textbf{Lemme d'antyphérèse} \\ \mathscr D(a) \cap \mathscr D(b) = \mathscr D(b) \cap \mathscr D(r) $

$ a\wedge b = b\wedge r \quad \scriptsize \text{en particulier} $

$ \textbf{Ensemble de diviseurs communs} \\ \mathscr D(a) \cap \mathscr D(b) = \mathscr D(a \wedge b) \quad \scriptsize \text{démo par antyphérèse}$

$ \textbf{Caractérisation du pgcd par la définition du max d'un ensemble} \\ \text{!! Cela signifie que $a \wedge b$ est le plus grand (au sens divisibilité) élément de l'ensemble $\mathscr D(a) \cap \mathscr D(b)$ des diviseurs communs à $a$ et $b$. !!} \\ \text{Donc en revenant à la définition première du plus grand élément, on peut montrer qu'un candidat $\delta$ est pgcd de $a$ et $b$ en montrant :} \\ \begin{array}{rl} \ \text{(i)} & \delta \text{ divise $a$ et divise $b$ (i.e. $\delta \in \mathscr D(a) \cap \mathscr D(b)$)} \\ \text{(ii)} & \forall d \in \mathscr D(a) \cap \mathscr D(b), \quad d \text{ divise } \delta \ \end{array} $

$ \textbf{Coefficients de Bézout} \\ \scriptsize \textit{Ils découlent de la principalité de $\mathbb Z$ !} \\ \begin{array}{rl} \text{Il existe } (u, v) \in \mathbb Z^2, & au + bv &= &a \wedge b \\ \text{Autrement dit } & a\mathbb Z + b\mathbb Z &= &(a \wedge b)\mathbb Z \end{array} \\ \scriptsize \textbf{ !! réfléchir au « autrement dit » et le maîtriser !!} $

$ \textit{Distributivité du produit sur le pgcd} \\ k(a \wedge b) = ka \wedge kb $

$ \textbf{Algorithme d'Euclide} \\ \text{Voir image} - \text{ à maîtriser parfaitement} $

$ \textbf{Nombres premiers entre eux} \\ a \wedge b = 1 $

$ \textbf{Caractérisation du pgcd par les nombres premiers entre eux} \\ \delta = a \wedge b \iff a = a'\delta, b = b'\delta \text{ et } a' \wedge b' = 1 $

$ \textbf{Théorème de Bachet-Bézout} \\ a \wedge b = 1 \iff au + bv = 1 \quad \scriptsize (\exists u, v \in \mathbb Z) $

$ \textbf{Lemme de Gau$\beta$} \\ a | bc \Rightarrow a | c \text{ si $a \wedge b$ = 1} $

$ \textbf{Écriture irréductible, unique, d'un rationnel} \\ r = \frac{a}{b}, \quad a \wedge b = 1 \quad \scriptsize \text{est une écriture unique} $

$ \textbf{Équations diophantiennes} \\ ax + by = c $

$ \Large \text{Méthode} $
0001

$ \Large \text{Exemple} - \large 1658x + 156y = 6 $

$ \textbf{Indépendance divisorielle} \\ \text{Un produit de diviseurs premiers entre eux deux à deux est encore un diviseur} $

$ \textit{Pour deux diviseurs} \\ (\text{$a | c \quad$ et $\quad b | c \quad$ et $ \quad a \wedge b = 1$}) \Rightarrow (ab | c) \quad\quad \text{i.e.} \\ (a \wedge b) \Rightarrow (a\mathbb Z \cap b\mathbb Z = ab\mathbb Z) $

$ \textbf{Pour plusieurs entiers} \\ \begin{array}{rl} \ \text{(i)} & \mathscr D(a_1) \cap \dots \cap \mathscr D(a_n) = \mathscr D(a_1 \wedge \dots \wedge a_n) \quad \text{ i.e. } \quad \text{un entier $d$ divise $a_1, \dots, a_n \iff d$ divise $a_1 \wedge \dots \wedge a_n$} \\ \text{(ii)} & \text{Comme le pgcd est associatif, on peut toujours réduire les calculs à une suite de calculs de pgcd de deux entiers seulement.} \\ &\text{! Donc toutes les propriétés (Bézout, entiers premiers entre eux...) restent valables !} \ \end{array} $

$ \textbf{Plus petit multiple commun} \\ \begin{array}{rl} \text{(i)} & \text{min}(a\mathbb Z \cap b\mathbb Z) \text{ si $ab \neq 0$} \\ \text{(ii)} & 0 \text{ sinon} \end{array} $

$ \textbf{Ensemble de multiples communs} \\ a\mathbb Z \cap b\mathbb Z = (a \vee b)\mathbb Z $

$ \textbf{Caractérisation du ppcm par la définition du min d'un ensemble} \\ \text{!! La caractérisation du pgcd est valable pour le ppcm !!} \\ \begin{array}{rl} \text{(i)} & \text{$\mu$ est multiple de $a$ et de $b$} \\ \text{(ii)} & \forall m \in a\mathbb Z \cap b\mathbb Z \text{, $\quad m$ divise $\mu$} \end{array} $

$ \textit{Distributivité du produit sur le ppcm} \\ k(a \vee b) = ka \vee kb $

$ \textbf{Pour plusieurs entiers} \\ \begin{array}{rl} \ \text{(i)} & a_1\mathbb Z \cap \dots \cap a_n \mathbb Z = (a_1 \vee \dots \vee a_n)\mathbb Z \quad \text{ i.e. } \quad \text{un entier $m$ est multiple de $a_1, \dots, a_n \iff m$ est multiple de $a_1 \vee \dots \vee a_n$} \\ \text{(ii)} & \text{Comme le ppcm est associatif, on peut toujours réduire les calculs à une suite de calculs de ppcm de deux entiers seulement.} \\ &\text{! Donc toutes les propriétés restent valables !} \ \end{array} $

$ \textit{Si a, b premiers entre eux} \\ (a \vee b) = |ab| $

$ \textbf{Lien entre $a \wedge b$ et $a \vee b$} \\ (a \wedge b) \times (a \vee b) = |ab| $

$ \textbf{Nombres premiers} \\ \mathbb P = \{ n \in \mathbb N : n \text{ est divisible par deux nombres exactement (1 et lui-même)} \} $

$ \textbf{Caractérisation des nombres premiers : équivalence entre} \\ \begin{array}{rl} \text{(i)} & p \text{ est un nombre premier} \\ \text{(ii)} & p \text{ est premier avec tout entier qu'il ne divise pas} \\ \text{(iii)} & p \text{ est premier avec tout nombre premier contenu dans } [1, \sqrt p] \end{array} $

$ (i) \iff (iii) \text{ permet de construire le crible d'Ératosthène} $

$ \textbf{Il existe une infinité de nombres premiers} $

$ \textbf{Décomposition primaire} \\ \text{Tout entier naturel $n \geq 2$ admet une décomposition en facteurs premiers, unique à l'ordre près} $

$ \textbf{Compatibilité avec le produit} \\ \text{Si $k$ est premier avec $a_1, \dots, a_n$, alors $k$ est premier avec $a_1\dots a_n$} $

$ \text{Si $p \in \mathbb P$ et $p | ab$, alors $p$ divise $a$ ou $b$} $

$ \textbf{Valuation p-adique} \\ \begin{array}{rl} \ \text{(i)} & n = \pm \prod_{p \in \mathbb P} p^{v_p(n)} \\ \text{(ii)} & v_p(ab) = v_p(a) + v_p(b) \quad \text{et} \quad v_p(\frac{a}{d}) = v_p(a) - v_p(d) \\ \text{(iii)} & b | a \iff v_p(b) \leqslant v_p(a) \text{ pour tout $p \in \mathbb P$} \\ \text{(iv)} & a \wedge b = \prod_{p \in \mathbb P} p^{\text{min{$v_p(a),v_p(b)$}}} \quad \text{et} \quad a \vee b = \prod_{p \in \mathbb P} p^{\text{max{$v_p(a),v_p(b)$}}} \ \end{array} $

$ \textbf{Congruences} \\ a \equiv b \hspace 2mm [n] \iff n \text{ divise } a - b $

$ \textbf{Opérations sur les congruences} \\ \begin{array}{rl} \ \text{(i)} & (a \equiv b \hspace 2mm [n] \text{ et } c \equiv d \hspace 2mm [n]) \Rightarrow (a + c \equiv b + d \hspace 2mm [n]) \\ \text{(ii)} & (a \equiv b \hspace 2mm [n] \text{ et } c \equiv d \hspace 2mm [n]) \Rightarrow (ac \equiv bd \hspace 2mm [n]) \\ \text{(ii)'} & (a \equiv b \hspace 2mm [n]) \Rightarrow (a^p \equiv b^p \hspace 2mm [n]) \\ \text{(iii)} & (a \equiv b \hspace 2mm [n]) \Rightarrow (am \equiv bm \hspace 2mm [nm]) \ \end{array} $

$ \textbf{Preuve par 9} \\ \text{Tout nombre est congru à la somme de ses chiffres modulo 9} \\ \overline{c_r\dots c_1c_0} \equiv c_0 + c_1 + \dots + c_n \hspace 2mm [9] $

$ \mathbb Z / n\mathbb Z = \{ \widehat 0 ; \widehat 1 ; \dots ; \widehat{n - 1} \} \\ \text{ est un anneau commutatif, et un corps ($\mathbb F_p$) ssi n est premier} $

$ \textbf{Groupe des inversibles de $\mathbb Z / n\mathbb Z$} \\ \text U(\mathbb Z / n\mathbb Z) = \{ r \in \mathbb Z / n\mathbb Z : r \wedge n = 1 \} \\ \text{On note $\varphi(n) = $ card U$(\mathbb Z / n\mathbb Z)$ l'}\textbf{indicatrice d'Euler} $

$ \textbf{Petit théorème de Fermat} \\ a^p \equiv a \hspace 2mm [p] \\ \quad \\ \scriptsize \text{Si $a \wedge p = 1$ i.e. $p$ ne divise pas $a$, alors } \quad a^{p - 1} \equiv 1 \hspace 2mm [p] $

$ \text{Si $p \in \mathbb P$, $\forall k \in [\![1; p - 1]\!], \quad p | \binom{p}{k}$} $

$ \textbf{Théorème de Wilson} \\ p \text{ est premier$\iff (p - 1)! \equiv -1 \hspace 2mm [p]$} $