1. Rappels
Divisibilité, division euclidienne, congruences modulo \(n\) (compatibles avec \(+\), \(\times\) et puissances).
2. PGCD et théorème de Bézout
Bézout : \(a\wedge b = 1\) (premiers entre eux) \(\Leftrightarrow\exists(u ; v)\in\mathbb{Z}^2,\ au + bv = 1\).
Plus généralement, il existe \(u\), \(v\) tels que \(au + bv = a\wedge b\) (identité de Bézout, obtenue en remontant l'algorithme d'Euclide).
3. Théorème de Gauss
Si \(a\mid bc\) et \(a\wedge b = 1\), alors \(a\mid c\).
Conséquences : si \(a\mid n\), \(b\mid n\) et \(a\wedge b = 1\), alors \(ab\mid n\). Si \(p\) premier divise \(ab\), alors \(p\mid a\) ou \(p\mid b\).
4. Équation \(ax + by = c\)
Elle admet des solutions entières si et seulement si \(d = a\wedge b\) divise \(c\). Si \((x_0 ; y_0)\) est une solution, les solutions sont :
5. Petit théorème de Fermat
Si \(p\) est premier et \(p\nmid a\), alors \(a^{p-1}\equiv1\ [p]\). Pour tout \(a\) : \(a^p\equiv a\ [p]\).
6. Congruence \(ax\equiv b\ [n]\)
Si \(a\wedge n = 1\), on trouve un inverse \(a'\) de \(a\) modulo \(n\) (\(aa'\equiv1\ [n]\), par Bézout) et \(x\equiv a'b\ [n]\).
Exemple
\(3x\equiv2\ [7]\) : \(3\times5 = 15\equiv1\ [7]\), donc \(x\equiv5\times2 = 10\equiv3\ [7]\).