Algèbre et géométrie · 2e Bac SM

Numération, congruences et Z/nZ

L'heure, le jour de la semaine, le code d'un ordinateur en binaire : tout cela se calcule avec des restes, et les en donnent le mode d'emploi.

Le vocabulaire à connaître

système de numération de base b: Écrire un entier avec des chiffres de 0 à b − 1 : N = aₖbᵏ + … + a₁b + a₀.
congruence: a ≡ c [n] signifie que n divise a − c, c'est-à-dire que a et c ont le même reste dans la division par n.
Z/nZ: L'ensemble des classes de restes modulo n, muni de l'addition et de la multiplication des classes.

Pour écrire N en base b, je divise par b et je lis les restes de bas en haut. Pour additionner ou multiplier en base b, je retiens à partir de b.
Les congruences sont compatibles avec l'addition et la multiplication : si a ≡ c [n], alors aᵏ ≡ cᵏ [n]. Pour une puissance, on cherche k avec aᵏ ≡ 1 [n].
Dans , la classe de a est inversible si et seulement si a est premier avec n. Si n est premier, Z/nZ est un corps ; sinon il y a des diviseurs de zéro.

1.Je réduis chaque nombre modulo n pour travailler avec des petits restes.

2.Pour une puissance, je cherche la plus petite puissance congrue à 1 et je divise l'exposant par elle.

3.J'écris l'exposant sous la forme k × q + r et je ne garde que aʳ.

4.Je calcule aʳ et je donne son reste modulo n.

Si aᵏ ≡ 1 [n] et N = k q + r, alors aᴺ ≡ aʳ [n].

C.Q.F.D.

1.Je cherche le reste de 3²⁰²⁴ dans la division par 7.

2.3⁶ = 729 = 7 × 104 + 1, donc 3⁶ ≡ 1 [7].

3.2024 = 6 × 337 + 2, donc 3²⁰²⁴ = (3⁶)³³⁷ × 3² ≡ 3² [7].

4.3² = 9 = 7 + 2 : le reste est 2.