Découverte de la division euclidienne et congruence
2) Calculer le reste de \(2^{100}\) dans la division par 7 en utilisant les congruences.
- 1) Le reste doit être strictement positif ou nul : \(0 \le r < 5\).
\(-23 = 5(-5) + 2\). Le quotient est \(q = -5\) et le reste est \(r = 2\). (Attention : \(-23 = 5(-4) - 3\) n'est pas correct car le reste ne peut être négatif). - 2) Calculons les premières puissances modulo 7 :
\(2^1 \equiv 2 [7]\), \(2^2 \equiv 4 [7]\), \(2^3 = 8 \equiv 1 [7]\).
Comme \(100 = 3 \times 33 + 1\) :
\(2^{100} = (2^3)^{33} \times 2^1 \equiv 1^{33} \times 2 \equiv 2 [7]\). Le reste cherché est donc 2.