Nombres et calculs · 1re Bac SM

Congruences et ensemble Z/nZ

Calculer modulo n, c'est ne garder que le reste : de quoi trouver le dernier chiffre de 7²⁰²³ sans calculatrice.

Le vocabulaire à connaître

congruence: a ≡ b [n] signifie que n divise a − b : a et b ont le même reste dans la division par n.
Z/nZ: L'ensemble des n classes de congruence modulo n, représentées par 0, 1, …, n − 1, que l'on peut additionner et multiplier.

Si a ≡ b [n] et c ≡ d [n], alors a + c ≡ b + d [n] et ac ≡ bd [n], donc aᵏ ≡ bᵏ [n].
n divise a si et seulement si a ≡ 0 [n] : la divisibilité se lit sur les restes.
Les puissances d'un entier modulo n se répètent : il suffit de trouver la période.

1.Je calcule les premières puissances modulo n jusqu'à retomber sur 1 (ou sur un reste déjà vu).

2.Je repère la période.

3.Je réduis l'exposant par la division euclidienne par la période.

4.Je conclus avec le reste obtenu.

Avec les , un grand calcul se ramène à la période des restes.

C.Q.F.D.

1.Reste de 3¹⁰⁰ dans la division par 7.

2.3⁶ = 729 = 7 × 104 + 1, donc 3⁶ ≡ 1 [7] : la période est 6.

3.100 = 6 × 16 + 4, donc 3¹⁰⁰ ≡ 3⁴ [7].

4.3⁴ = 81 = 7 × 11 + 4 : le reste vaut 4.