Calcule le reste de la division de 13^987654 par 1001.
- User
Calcule le reste de la division de 13^987654 par 1001.
- Assistant
Nous cherchons le reste de la division de 13^987654 par 1001, c’est-à-dire :
[ 13^{987654} \mod 1001 ]
Étape 1 : Factoriser 1001
Commençons par factoriser 1001 :
[ 1001 = 7 \times 11 \times 13 ]
Ces trois facteurs sont premiers entre eux, donc nous pouvons utiliser le théorème des restes chinois (TRC) pour reconstruire le résultat modulo 1001 à partir des résultats modulo 7, 11 et 13.
Étape 2 : Calculs modulo 7, 11 et 13
a) Modulo 7
13 ≡ 6 mod 7
On cherche : [ 6^{987654} \mod 7 ]
φ(7) = 6, donc par le théorème d’Euler : [ 6^6 ≡ 1 \mod 7 ]
Donc : [ 6^{987654} ≡ 6^{987654 \mod 6} \mod 7 ]
987654 ÷ 6 = 164609 reste 0, donc : [ 6^{987654} ≡ 1 \mod 7 ]
✅ Résultat modulo 7 :
[ 13^{987654} ≡ 1 \mod 7 ]
b) Modulo 11
13 ≡ 2 mod 11
On cherche : [ 2^{987654} \mod 11 ]
φ(11) = 10, donc : [ 2^{10} ≡ 1 \mod 11 ]
Donc : [ 2^{987654} ≡ 2^{987654 \mod 10} \mod 11 ]
987654 ÷ 10 = 98765 reste 4, donc : [ 2^4 = 16 \Rightarrow 16 \mod 11 = 5 ]
✅ Résultat modulo 11 :
[ 13^{987654} ≡ 5 \mod 11 ]
c) Modulo 13
13 ≡ 0 mod 13
Donc : [ 13^{987654} ≡ 0 \mod 13 ]
✅ Résultat modulo 13 :
[ 13^{987654} ≡ 0 \mod 13 ]
Étape 3 : Théorème des restes chinois
Nous avons :
[ \begin{cases} x \equiv 1 \mod 7 \ x \equiv 5 \mod 11 \ x \equiv 0 \mod 13 \end{cases} ]
Nous allons résoudre ce système pour trouver x modulo 1001.
Étape 3.1 : Posons x ≡ 0 mod 13
Donc x = 13k pour un certain entier k.
Remplaçons dans les deux autres congruences :
-
x ≡ 1 mod 7 ⇒ 13k ≡ 1 mod 7
13 mod 7 = 6 ⇒ 6k ≡ 1 mod 7
L’inverse de 6 mod 7 est 6 (car 6×6 = 36 ≡ 1 mod 7)
⇒ k ≡ 6 mod 7 -
x ≡ 5 mod 11 ⇒ 13k ≡ 5 mod 11
13 mod 11 = 2 ⇒ 2k ≡ 5 mod 11
L’inverse de 2 mod 11 est 6 (car 2×6 = 12 ≡ 1 mod 11)
⇒ k ≡ 6×5 = 30 ≡ 8 mod 11
Donc k ≡ 6 mod 7
et k ≡ 8 mod 11
Étape 3.2 : Résolvons ce système pour k
[ \begin{cases} k \equiv 6 \mod 7 \ k \equiv 8 \mod 11 \end{cases} ]
Utilisons le théorème des restes chinois pour k modulo 77 = 7×11.
Posons k = 7a + 6
⇒ Remplaçons dans la 2e équation :7a + 6 ≡ 8 mod 11
⇒ 7a ≡ 2 mod 117a ≡ 2 mod 11
L’inverse de 7 mod 11 est 8 (car 7×8 = 56 ≡ 1 mod 11)
⇒ a ≡ 8×2 = 16 ≡ 5 mod 11Donc a = 11b + 5
⇒ k = 7a + 6 = 7(11b + 5) + 6 = 77b + 35 + 6 = 77b + 41Donc : [ x = 13k = 13(77b + 41) = 1001b + 533 ]
Donc : [ x ≡ 533 \mod 1001 ]
✅ Résultat final :
[ \boxed{13^{987654} \mod 1001 = 533} ]
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.