Propriétés fondamentales des congruences

Définition de la congruence

La congruence est une relation d'équivalence entre deux entiers relatifs. On dit que a est congru à b modulo n, noté a ≡ b [n], si a - b est divisible par n, où n est un entier strictement positif. En d'autres termes, a et b ont le même reste dans la division euclidienne par n. Cette notion est fondamentale pour simplifier les calculs et résoudre des problèmes d'arithmétique.

Addition et soustraction de congruences

Si a ≡ b [n] et c ≡ d [n], alors on peut additionner ou soustraire ces congruences :

• Addition: a + c ≡ b + d [n]
• Soustraction: a - c ≡ b - d [n]

Multiplication de congruences

Si a ≡ b [n] et c ≡ d [n], alors on peut multiplier ces congruences : ac ≡ bd [n]. Exemple: Si 5 ≡ 2 [3] et 4 ≡ 1 [3], alors 5 * 4 ≡ 2 * 1 [3], donc 20 ≡ 2 [3], qui est équivalent à 2 ≡ 2 [3]. Démonstration: Si a ≡ b [n] et c ≡ d [n], alors il existe des entiers k et l tels que a = b + kn et c = d + ln. En multipliant ces équations, on obtient ac = (b + kn)(d + ln) = bd + bln + kdn + kln² = bd + n(bl + kd + kln), donc ac - bd = n(bl + kd + kln), ce qui montre que ac ≡ bd [n].

Élévation à une puissance

Si a ≡ b [n], alors pour tout entier positif k, on a a^k ≡ b^k [n]. Exemple: Si 2 ≡ 5 [3], alors 2³ ≡ 5³ [3], donc 8 ≡ 125 [3], qui est équivalent à 2 ≡ 2 [3]. Cette propriété découle directement de la multiplication des congruences, puisque a^k = a * a * ... * a (k fois).

Simplification des congruences

Si ac ≡ bc [n] et si c et n sont premiers entre eux (c'est-à-dire, PGCD(c, n) = 1), alors on peut simplifier la congruence en divisant par c : a ≡ b [n]. Il est crucial que c et n soient premiers entre eux pour pouvoir simplifier. Contre-exemple: 6 ≡ 15 [3]. Si on divise par 3 (qui n'est pas premier avec 3), on obtient 2 ≡ 5 [3], qui est vrai. Mais si on avait divisé *par* 3 mais qu'il n'y avait *pas* de congruence au départ, cela aurait mené à une conclusion fausse. Donc, il est crucial de respecter cette condition PGCD(c, n) = 1. Cas général : Si ac ≡ bc [n], alors a ≡ b [n/PGCD(c,n)].

Ce qu'il faut retenir

• Définition: a ≡ b [n] signifie que a - b est divisible par n.
• Addition/Soustraction: Si a ≡ b [n] et c ≡ d [n], alors a + c ≡ b + d [n] et a - c ≡ b - d [n].
• Multiplication: Si a ≡ b [n] et c ≡ d [n], alors ac ≡ bd [n].
• Puissance: Si a ≡ b [n], alors a^k ≡ b^k [n] pour tout entier positif k.
• Simplification: Si ac ≡ bc [n] et PGCD(c, n) = 1, alors a ≡ b [n]. Généralisation : Si ac ≡ bc [n] alors a ≡ b [n/PGCD(c, n)].