Exercice 34

1. On appelle chaîne de $x$ à $y$ une suite comme dans l'énoncé.

• Réflexivité : $x \sim x$ par définition.

• Symétrie : une chaîne de $x$ à $y$, parcourue à l'envers, est une chaîne de $y$ à $x$, car la condition sur deux termes consécutifs est symétrique.

• Transitivité : si $x \sim y$ et $y \sim z$, on met bout à bout une chaîne de $x$ à $y$ et une chaîne de $y$ à $z$ ; les cas $x = y$ ou $y = z$ sont immédiats.

Si $x \,\mathcal{R}\, y$, la suite $(x,y)$ est une chaîne : $\sim$ contient $\mathcal{R}$. Soit enfin $\approx$ une équivalence contenant $\mathcal{R}$, et $(x_{0}, \dots, x_{k})$ une chaîne de $x$ à $y$. Pour chaque $i$, on a $x_{i-1} \approx x_{i}$, directement ou grâce à la symétrie de $\approx$. Par transitivité de $\approx$, on obtient $x \approx y$. $$\boxed{\sim \text{ est la plus petite relation d'équivalence contenant } \mathcal{R}.}$$

2. On a $0 \,\mathcal{R}\, 3$ et $3 \,\mathcal{R}\, 6$, mais $6 - 0 = 6 \notin \{3,5\}$ : la relation n'est pas transitive. Pour les classes, on remarque que la chaîne $x,\ x + 3,\ x + 6,\ x + 1$ relie $x$ à $x + 1$, puisque $(x + 6) - (x + 1) = 5$. Donc $x \sim x + 1$ pour tout $x$, et de proche en proche, tous les entiers sont équivalents. $$\boxed{\text{Il n'y a qu'une classe : } \mathbb{Z} \text{ tout entier.}}$$

3. Avec $\{4,6\}$, chaque pas d'une chaîne change $x$ en $x \pm 4$ ou $x \pm 6$, ce qui conserve la parité ; inversement, la chaîne $x,\ x + 6,\ x + 2$ relie $x$ à $x + 2$. $$\boxed{\text{Pour } \{4,6\} : \text{ deux classes, les entiers pairs et les entiers impairs.}}$$ Dans le cas général, notons $d = \mathrm{pgcd}(a,b)$. Chaque pas d'une chaîne modifie l'entier d'un multiple de $d$, donc $x \sim y$ entraîne $d \mid y - x$. Réciproquement, le théorème de Bézout fournit des entiers $u$ et $v$ tels que $d = au + bv$ ; en faisant $|u|$ pas de $\pm a$ puis $|v|$ pas de $\pm b$, on relie $x$ à $x + d$, et de proche en proche $x$ à $x + md$ pour tout $m \in \mathbb{Z}$. $$\boxed{x \sim y \iff y \equiv x \ [\mathrm{pgcd}(a,b)] : \text{ les classes sont les } \mathrm{pgcd}(a,b) \text{ classes de congruence.}}$$ On retrouve la question 2, avec $\mathrm{pgcd}(3,5) = 1$, et le début de la question 3, avec $\mathrm{pgcd}(4,6) = 2$.