1$\text{Théorème 1 : Euclide dans } \mathbb N$
$\forall (a, b) \in \mathbb N \times \mathbb N^*, \exists (q, r) \in \mathbb N^2 \begin{cases}a = bq + r \\ 0 \le r < b\end{cases}$
2$\text{Théorème 2 : Euclide dans } \mathbb Z$
$\forall (a, b) \in \mathbb Z \times \mathbb Z^*, \exists (q, r) \in \mathbb Z^2 \begin{cases}a = bq + r \\ 0 \le r < |b|\end{cases}$
3$\text{Propriété 1 : Lien entre divisibilité et division euclidienne}$
$a | b \Longleftrightarrow \text{ le reste de la division euclidienne de } a \text{ par } b \text{ est nul}$
4$\text{Proposition 1.a : Transitivité de la divisibilité}$
$\begin{cases}a|b \\ b|a \end{cases}\implies a|c$
5$\text{Proposition 1.b : Cas symetrique de la divisibilité}$
$a = \pm b \Longleftrightarrow \begin{cases}a|b \\ b|a \end{cases}$
6$\text{Propriété 1.c : Divisibilité des combinaisons linéaires}$
$\begin{cases}a|b \\ a|c \end{cases} \implies a|bu + cv$
7$\text{Propriété 1.d : Divisibilité après multiplication}$
$a|b \implies ca|cb$
8$\text{Propriété 1.e : Lien entre divisibilité et relation d'ordre classique}$
$\begin{cases}a|b \\ b \neq 0 \end{cases} \implies |a| \le |b|$
9$\text{Proposition 2 : Relation d'ordre}$
$\text{La divisibilité est une relation d'ordre sur } \mathbb N$
10$\text{Proposition 3 : Relation d'équivalence}$
$\text{La congruence est une relation d'équivalence}$
11$\text{Propriété 2.a : Opération de base sur les congruences}$
$\begin{cases}a \equiv b \pmod n \\ a' \equiv b' \pmod n \end{cases} \implies \begin{cases}-a \equiv -b \pmod n \\ a + a' \equiv b + b' \pmod n \\ aa' \equiv bb' \pmod n\end{cases}$
12$\text{Propriété 2.b : Multiplication de congruences}$
$a \equiv b \pmod n \implies ac \equiv bc \pmod n$
13$\text{Propriété 2.c : Exponentiation de congruences}$
$a \equiv b \pmod n \implies a^k \equiv b^k \pmod n$
14$\text{Propriété 2.d : Lien entre congruence et divisibilité}$
$\begin{cases}a \equiv b \pmod n \Longleftrightarrow n|b-a \\ n|a \Longleftrightarrow a \equiv 0 \pmod n \end{cases}$
15$\text{Théorème 3 : Somme de groupe}$
$H + K \text{ est un sous-groupe de } (G, +)$
16$\text{Proposition 4 : Unicité du PGCD}$
$\text{Pour tout }(a, b) \in \mathbb Z^2, \text{ il existe un unique entier naturel } d \text{ tel que } PGCD(a, b) = d$
17$\text{Proposition 5 : Lien entre ensemble des diviseurs communs et PGCD}$
$D(a) \cap D(b) = D(a \wedge b)$
18$\text{Proposition 6 : PGCD et signe}$
$a \wedge b = -a \wedge b = a \wedge -b = -a \wedge -b$
19$\text{Proposition 7 : Homogénéité du PGCD}$
$PGCD(ac, bc) = |c|PGCD(a, b)$
20$\text{Théorème 4 : Algorithme d'Euclide}$
$PGCD(a, b) = PGCD(b, r)$
21$\text{Proposition 9 : Lien entre PPCM et PGCD}$
$PGCD(a, b) \times PPCM(a, b) = |a \times b|$
22$\text{Théorème 5 : Bézout}$
$a \text{ et } b \text{ sont premiers entre eux } \Longleftrightarrow \exists (u, v) \in \mathbb Z^2, au + bv = 1$
23$\text{Théorème 6 : Gauss}$
$a \wedge b = 1 \implies (a | bc \Longleftrightarrow a | c)$
24$\text{Théorème 7 : Sans nom}$
$a \wedge bc = 1 \Longleftrightarrow \begin{cases}a \wedge b = 1 \\ a \wedge c = 1 \end{cases}$
25$\text{Corollaire 1 : Itération du théorème sans nom}$
$\forall i \in \llbracket1, n\rrbracket, a \wedge b_i = 1 \Longleftrightarrow a \wedge \prod_{i=1}^nb_i = 1$
26$\text{Corollaire 2 : Puissances de nombre premiers entre eux}$
$a \wedge b = 1 \implies a^n \wedge b^m = 1$
27$\text{Corollaire 3 : Divisibilité du produit de nombres premiers entre eux}$
$\begin{cases}a \wedge b = 1 \\ a|c \\ b|c \end{cases} \implies ab|c$
28$\text{Proposition 10 : Critère de primalité}$
$p \in \mathbb P \Longleftrightarrow D(p) \cap \llbracket 2, \lfloor \sqrt{p} \rfloor \rrbracket = \emptyset$
29$\text{Proposition 11 : Nombres premiers premiers entre eux}$
$p \neq p' \implies p \wedge p' = 1$
30$\text{Proposition 12 : Nombres premiers divisant un produit}$
$p|ab \implies p|a \text{ ou } p|b$
31$\text{Théorème 8 : Théorème d'Euclide sur les nombres premiers}$
$\text{Il y a une infinité de nombres premiers}$
32$\text{Proposition 13 : Lien entre p-valuation et divisibilité}$
$p^k|a \Longleftrightarrow v_p(a) \ge k$
33$\text{Proposition 14.a : p-valuation du produit}$
$v_p(ab) = v_p(a) + v_p(b)$
34$\text{Proposition 14.b : p-valuation d'une puissance}$
$v_p(a^k) = kv_p(b)$
35$\text{Proposition 14.c : Minoration de la p-valuation de la somme}$
$v_p(a + b) \ge \min(v_p(a), v_p(b))$
36$\text{Proposition 14.c : p-valuation de la somme dans le cas inégal}$
$v_p(a) \neq v_p(b) \implies v_p(a+b) = \min(v_p(a), v_p(b))$
37$\text{Théorème 9 : Décomposition en facteurs premiers}$
$n = \prod_{p \in \mathbb P}p^{v_p(n)}$
$\text{Cette décomposition est unique}$
38$\text{Corollaire 5 : Equivalence entre divisibilité et p-valuations}$
$a|b \Longleftrightarrow \forall p \in \mathbb P, v_p(a) \le v_p(b)$
39$\text{Corollaire 6.a : Lien entre PGCD et p-valuation}$
$PGCD(a, b) = \prod_{p \in \mathbb P}p^{\min(v_p(a), v_p(b))}$
40$\text{Corollaire 6.b : Lien entre PPCM et p-valuation}$
$PGCD(a, b) = \prod_{p \in \mathbb P}p^{\max(v_p(a), v_p(b))}$
41$\text{Corollaire 7 : Lien entre nombres premiers entre eux et primalité des diviseurs communs}$
$a \wedge b = 1 \Longleftrightarrow D(a) \cap D(b) \cap \mathbb P = \emptyset$
42$\text{Théorème 10.a : Petit théorème de Fermat (cas général)}$
$a^p \equiv a \pmod p$
43$\text{Théorème 10.b : Petit théorème de Fermat (cas non multiple)}$
$p \text{ ne divise pas } a \implies a^{p-1} \equiv 0 \pmod p$
44$\text{Proposition 15 : Lien entre nombres premiers entre eux et nombres premiers dans leur ensemble}$
$a_1, a_2, ..., a_n \text{ premiers entre eux } \implies a_1, a_2, .., a_n \text{ premiers dans leur ensemble}$