Prépa, 1re année › Arithmétique dans $\mathbb{Z}$ › Lemme de Gauss
Lemme de Gauss : énoncé (MPSI)
Théorème
Lemme de Gauss
Soient $a, b, c \in \mathbb{Z}$. Si $a \mid bc$ et $a \wedge b = 1$, alors $a \mid c$.
Démonstration : Lemme de Gauss
Démonstration
Preuve du lemme de Gauss
Comme $a \wedge b = 1$, il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$. En multipliant par $c$ : $$c = acu + bcv.$$ Or $a \mid acu$ et $a \mid bc$, donc $a \mid bcv$. Ainsi $a$ divise la somme, c'est-à-dire $a \mid c$.
S’entraîner
- Expressions premières entre elles
- Équation diophantienne $323x + 391y = c$
- PGCD de deux nombres de la forme $2^k - 1$
- Un principe de chiffrement à clé publique (type CCINP)
- Théorème de Wilson et carrés congrus à $-1$ (type Mines-Ponts)