Congruences arithmétiques et propriétés

Division Euclidienne

• Définition : Pour $a, b \in \mathbb{Z}$ avec $b \neq 0$, il existe un unique couple $(q, r) \in \mathbb{Z}^2$ tel que $a = bq + r$ et 0 \leq r < |b|.
• Rôle du reste : Le reste $r$ est toujours positif et strictement inférieur à la valeur absolue du diviseur $b$.
• Exemple : La division euclidienne de 114 par 8 est $114 = 8 \times 14 + 2$.
  Attention : $114 = 8 \times 13 + 10$ n'est pas une division euclidienne car $10 \not< 8$.
• Conséquence : Tout entier $a$ peut s'écrire sous la forme $a = bq + r$, créant des partitions d'entiers (ex: pairs/impairs pour $b=2$).

Divisibilité

• Définition : $a$ divise $b$ (noté $a|b$) s'il existe $k \in \mathbb{Z}$ tel que $b = ka$.
• Propriétés :
  • $a|b \Longleftrightarrow (-a)|b \Longleftrightarrow a|(-b) \Longleftrightarrow (-a)|(-b)$.
  • Si $a|b$ et $b|c$, alors $a|c$ (Transitivité).
  • Si $a|b$ et $a|c$, alors $a|(b+c)$ et $a|(b-c)$.
  • Attention : Si $a|c$ et $b|c$, alors $(a+b)|c$ est faux (ex: $2|6$ et $3|6$ mais $5 \nmid 6$).
• Critères de divisibilité :
  • Par 3 : La somme des chiffres est divisible par 3.
  • Par 5 : Le chiffre des unités est 0 ou 5.
  • Par 9 : La somme des chiffres est divisible par 9.
  • Par 11 : La somme alternée des chiffres est divisible par 11.

Congruences

• Historique : Introduite par Gauss en 1801.
• Définition : $a \equiv b \pmod{n}$ si $a$ et $b$ ont le même reste dans la division euclidienne par $n$.
  Équivalence clé : $a \equiv b \pmod{n} \iff n | (a-b)$.
• Propriétés (Relation d'équivalence) :
  • Réflexivité : $a \equiv a \pmod{n}$.
  • Symétrie : Si $a \equiv b \pmod{n}$, alors $b \equiv a \pmod{n}$.
  • Transitivité : Si $a \equiv b \pmod{n}$ et $b \equiv c \pmod{n}$, alors $a \equiv c \pmod{n}$.
• Compatibilité des opérations : Si $a \equiv a' \pmod{n}$ et $b \equiv b' \pmod{n}$, alors :
  • $a+b \equiv a'+b' \pmod{n}$ (addition).
  • $ab \equiv a'b' \pmod{n}$ (multiplication).
  • $a^p \equiv (a')^p \pmod{n}$ pour $p \in \mathbb{N}^*$ (puissance).
• Inverse modulo $n$ : $a$ est inversible modulo $n$ s'il existe $b$ tel que $ab \equiv 1 \pmod{n}$. Cet inverse est unique modulo $n$.

Plus Grand Commun Diviseur (PGCD)

• Définition : Le PGCD de $a$ et $b$, noté $a \wedge b$, est le plus grand élément de l'ensemble $\mathcal{D}(a,b)$ des diviseurs positifs communs à $a$ et $b$.
  Notation : $a \wedge b = |a| \wedge |b|$ et $a \wedge b \geq 1$.
• Propriétés :
  • $a \wedge b = b \iff b|a$.
  • Homogénéité : $ka \wedge kb = k(a \wedge b)$ pour $k \neq 0$.
  • L'ensemble des diviseurs communs à $a$ et $b$ est l'ensemble des diviseurs de $a \wedge b$. Autrement dit, $\mathcal{D}(a,b) = \mathcal{D}(a \wedge b)$.
• Méthode de calcul (Algorithme d'Euclide) :
  • Permet de trouver le PGCD de deux entiers $a$ et $b$ ($0 < b \leq a$) par divisions euclidiennes successives.
  • Le PGCD est le dernier reste non nul obtenu.
  • Exemple : $PGCD(3596, 3393) = 29$.

Nombres Premiers Entre Eux

• Définition : Deux entiers $a$ et $b$ sont premiers entre eux si $a \wedge b = 1$.
• Conséquence sur les fractions : Une fraction $\frac{a}{b}$ est irréductible si $a$ et $b$ sont premiers entre eux. Toute fraction peut être rendue irréductible en divisant le numérateur et le dénominateur par leur PGCD.

Théorèmes Fondamentaux

Égalité de Bézout

• Théorème : Pour $a, b \in \mathbb{Z}$ non nuls, $d = a \wedge b$. Alors il existe $u, v \in \mathbb{Z}$ tels que $au + bv = d$.
• Cas particulier (Théorème de Bachet-Bézout) : $a$ et $b$ sont premiers entre eux $\iff$ il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$.
• Algorithme d'Euclide Étendu : Permet de trouver les coefficients $u$ et $v$ en "remontant" les étapes de l'algorithme d'Euclide.
  Exemple : Pour $47u + 35v = 1$, on trouve $u=3, v=-4$.
• Note Historique : Énoncé par Bachet pour les entiers, puis démontré par Bézout pour les polynômes.

Théorème de Gauss

• Théorème : Si $a|bc$ et $a \wedge b = 1$, alors $a|c$.
• Hypothèse primordiale : L'hypothèse $a \wedge b = 1$ est indispensable. (Ex: $3|6 \times 7$ mais $3 \nmid 7$).
• Corollaire : Si $a|c$, $b|c$ et $a \wedge b = 1$, alors $ab|c$.

Équations Diophantiennes

• Définition : Équation de la forme $ax + by = c$ avec $(x, y) \in \mathbb{Z}^2$.
• Condition d'existence des solutions : L'équation $(E): ax + by = c$ admet des solutions $\iff$ $a \wedge b | c$.
• Forme des solutions (quand $a \wedge b = 1$) : Si $(x_0, y_0)$ est une solution particulière, les solutions de $(E)$ sont de la forme : $$\left\{ \begin{array}{l} x = x _ {0} + b k \\ y = y _ {0} - a k \end{array} \right., \quad k \in \mathbb {Z}.$$
• Méthode de résolution (Analyse-Synthèse) :
  1. Vérifier l'existence : Calculer $d = a \wedge b$. Si $d \nmid c$, pas de solution. Sinon, simplifier l'équation par $d$.
  2. Trouver une solution particulière $(x_0, y_0)$ : Souvent via l'algorithme d'Euclide étendu.
  3. Analyse : Utiliser le théorème de Gauss pour exprimer $x$ et $y$ en fonction de $x_0, y_0$ et un paramètre $k$.
  4. Synthèse : Vérifier que les expressions obtenues sont bien solutions de l'équation.
• Exemple : Pour $12x + 5y = 3$, une solution particulière est $(x_0,y_0)=(-6,15)$. Les solutions générales sont $(x,y)=(-6+5k, 15-12k)$, pour $k \in \mathbb{Z}$.