Bonjour, j'aimerais de l'aide pour ces deux exercices. MERCI D'AVANCE.
EXERCICE 1
En utilisant le théorème chinois,résoudre dans $Z^{2}$ le système:
x≡5 mod 17
x≡3 mod 31
EXERCICE 2
En utilisant l'algorithme de calcul rapide des puissances, calculer $7^{87}$ mod 43
ARITHMETIQUE
Re: ARITHMETIQUE
Bonjour
Exercice 1
17 et 31 sont premiers entre eux. On a besoin de calculer leurs inverses donc on utilise l'algorithme d'Euclide.
31 =17 + 14 ; 17 =14 + 3 ; 14 = 3 x 4 +2 ; 3 = 2 + 1.
1=3 - 2 ; 1= 3 - ( 14 - 4 x 3) = 5 x 3 - 14 ; 1 = 5 ( 17 - 14) - 14 = 5 x 17 - 6 x 14
1 = 5 x 17 - 6 ( 31 - 17) = 11 x 17 - 6 x 31.
Donc modulo 17 : 31 a pour inverse -6 ou 11.
Modulo 31 : 17 a pour inverse 11.
Solutions du système : $x= 5\times 31 \times (-6) + 3\times 17 \times 11=-369$ modulo $17\times 31 = 527$
Exercice 2
$87 = 2^6+2^4+2^2+2^1+2^0$ soit en écriture binaire $k=1010111$
$p=1$ et $a=7$. En utilisant l'écriture binaire de la droite vers la gauche : (toutes les égalités sont modulo 43)
1) $p=1\times 7$ , $a=7^2=49\equiv 6$
2) $p=7\times 6=42$ , $a=6^2=36\equiv (-7)$
3) $p=42 \times (-7)=-294\equiv 7$ , $a=36^2\equiv 6$
4) $p$ inchangé , $a=6^2=36\equiv (-7)$
5) $p=7\times 36\equiv 37\equiv (-6)$ , $a=(-7)^2\equiv 6$
6) $p$ inchangé , $a=6^2\equiv (-7)$
7) $p=(-6)\times (-7)=42 \equiv (-1)$
Donc $7^{87}=-1$ modulo 43.
Reamarque : A partir de l'étape 2 on pouvait gagner du temps car à cette étape on obtient $7^3\equiv (-1)\ [43]$ donc $7^6\equiv 1\ [43]$
87 = 6 x 14 +3 donc $7^{87}\equiv 7^3\equiv (-1)\ [43]$
Exercice 1
17 et 31 sont premiers entre eux. On a besoin de calculer leurs inverses donc on utilise l'algorithme d'Euclide.
31 =17 + 14 ; 17 =14 + 3 ; 14 = 3 x 4 +2 ; 3 = 2 + 1.
1=3 - 2 ; 1= 3 - ( 14 - 4 x 3) = 5 x 3 - 14 ; 1 = 5 ( 17 - 14) - 14 = 5 x 17 - 6 x 14
1 = 5 x 17 - 6 ( 31 - 17) = 11 x 17 - 6 x 31.
Donc modulo 17 : 31 a pour inverse -6 ou 11.
Modulo 31 : 17 a pour inverse 11.
Solutions du système : $x= 5\times 31 \times (-6) + 3\times 17 \times 11=-369$ modulo $17\times 31 = 527$
Exercice 2
$87 = 2^6+2^4+2^2+2^1+2^0$ soit en écriture binaire $k=1010111$
$p=1$ et $a=7$. En utilisant l'écriture binaire de la droite vers la gauche : (toutes les égalités sont modulo 43)
1) $p=1\times 7$ , $a=7^2=49\equiv 6$
2) $p=7\times 6=42$ , $a=6^2=36\equiv (-7)$
3) $p=42 \times (-7)=-294\equiv 7$ , $a=36^2\equiv 6$
4) $p$ inchangé , $a=6^2=36\equiv (-7)$
5) $p=7\times 36\equiv 37\equiv (-6)$ , $a=(-7)^2\equiv 6$
6) $p$ inchangé , $a=6^2\equiv (-7)$
7) $p=(-6)\times (-7)=42 \equiv (-1)$
Donc $7^{87}=-1$ modulo 43.
Reamarque : A partir de l'étape 2 on pouvait gagner du temps car à cette étape on obtient $7^3\equiv (-1)\ [43]$ donc $7^6\equiv 1\ [43]$
87 = 6 x 14 +3 donc $7^{87}\equiv 7^3\equiv (-1)\ [43]$