Exercices td arithmetique modulaire et exponentielle rapide
Télécharger PDFExponentielle Modulaire Rapide
Exercice 1
1. Démontrer que l'on peut calculer \( x^{43} \) en employant trois produits et des élévations au carré.
2. Calculer \( 1247^{43} \mod 27 \).
Exercice 2
Calculer le nombre de multiplications et d'élévations au carré que vous devez faire en utilisant la méthode d'exponentiation rapide pour élever un nombre à la puissance \( 10262 \).
Exercice 3
En utilisant la méthode d'exponentiation modulaire rapide, calculer :
1. \( 5^{121} \mod 8 \) ;
2. \( 2^{31545} \mod 173 \) ;
3. \( 5^{14476478} \mod 3241 \).
Exercice 4
Quels sont les nombres inversibles dans \( \mathbb{Z}/30\mathbb{Z} \) ?
Exercice 5
On admet que les décompositions en facteurs premiers de \( 1139062500 \) et \( 4665600 \) sont \( 2^2 \times 3^6 \times 5^8 \) et \( 2^8 \times 3^6 \times 5^2 \) respectivement. Calculer le PGCD de ces deux nombres.
Exercice 6
On rappelle que les 12 premiers nombres premiers sont les suivants : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Quelle est la forme de la décomposition en facteurs premiers d'un entier \( 1 \leq a \leq 25 \) premier avec 35 ?
Exercice 7
En utilisant la méthode d'exponentiation modulaire rapide, calculer :
1. \( 8^4 \mod 9 \) ;
2. \( 15^{6312} \mod 38 \).
Exercice 8
Calculer le nombre de multiplications et d'élévations au carré que vous devez faire en utilisant la méthode d'exponentiation rapide pour élever un nombre à la puissance \( 7645 \).
Foire aux Questions (FAQ)
Qu'est-ce que l'exponentiation modulaire rapide ?
L'exponentiation modulaire rapide est une méthode permettant de calculer \( a^b \mod m \) de manière efficace en réduisant le nombre d'opérations nécessaires.
Comment fonctionne la décomposition en facteurs premiers ?
La décomposition en facteurs premiers consiste à exprimer un nombre comme un produit de nombres premiers, ce qui permet de simplifier les calculs de PGCD ou d'autres propriétés arithmétiques.
Qu'est-ce qu'un nombre inversible dans \( \mathbb{Z}/n\mathbb{Z} \) ?
Un nombre est inversible dans \( \mathbb{Z}/n\mathbb{Z} \) s'il existe un entier \( k \) tel que \( a \times k \equiv 1 \mod n \), ce qui est possible si et seulement si \( a \) et \( n \) sont premiers entre eux.