1. Divisibilité
\(a\) divise \(b\) (noté \(a\mid b\)) s'il existe \(k\in\mathbb{Z}\) tel que \(b = ka\).
Si \(a\mid b\) et \(a\mid c\), alors \(a\mid(bu + cv)\) pour tous \(u, v\in\mathbb{Z}\).
2. Division euclidienne
Pour \(a\in\mathbb{Z}\) et \(b\in\mathbb{N}^*\), il existe un unique couple \((q ; r)\) tel que \(a = bq + r\) et \(0\le r < b\).
3. Congruences
\(a\equiv b\ [n]\) si \(n\) divise \(a - b\) (même reste dans la division par \(n\)).
Si \(a\equiv b\ [n]\) et \(c\equiv d\ [n]\), alors \(a + c\equiv b + d\ [n]\), \(ac\equiv bd\ [n]\) et \(a^k\equiv b^k\ [n]\).
Exemple
Reste de \(2^{100}\) modulo \(7\) : \(2^3 = 8\equiv1\ [7]\), donc \(2^{100} = (2^3)^{33}\times2\equiv2\ [7]\).
4. PGCD et PPCM
- \(\text{PGCD}(a, b)\) : plus grand diviseur commun. \(a\wedge b\).
- Algorithme d'Euclide : \(\text{PGCD}(a, b) = \text{PGCD}(b, r)\) où \(r\) est le reste de \(a\) par \(b\).
- \(\text{PGCD}(a, b)\times\text{PPCM}(a, b) = |ab|\).
5. Nombres premiers
- Tout entier \(n\ge2\) admet un diviseur premier. Si \(n\) n'est pas premier, il a un diviseur premier \(p\le\sqrt{n}\).
- Il existe une infinité de nombres premiers.
- Décomposition : tout \(n\ge2\) s'écrit de façon unique \(n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}\).
- Nombre de diviseurs positifs : \((\alpha_1 + 1)(\alpha_2 + 1)\cdots(\alpha_k + 1)\).
6. Systèmes de numération
\(n = \overline{a_k\dots a_1a_0}_{(b)} = a_kb^k + \dots + a_1b + a_0\) avec \(0\le a_i < b\). Exemple : \(\overline{1011}_{(2)} = 8 + 2 + 1 = 11\).