Calculer un reste à l’aide de congruences
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteSituation
On cherche à déterminer le reste de la division euclidienne d'un très grand entier par un autre entier.
Par exemple, on recherche le reste de la division euclidienne de $ 12\ 345^{2000} $ par 7.
Une calculatrice ne permet pas de répondre (les nombres sont trop grands) mais il est possible de résoudre le problème en utilisant les congruences.
Méthode
Pour trouver le reste de la division euclidienne de $ a^{b} $ par $ n $ on va utiliser la caractérisation du reste à l'aide de congruence :
$ r $ est le reste de la division euclidienne de $ m $ par $ n $ $ \Leftrightarrow $ $ \left\{ \begin{matrix} r\equiv m \ \left[n\right] \\ 0 \leqslant r <|n| \end{matrix}\right. $
et on va chercher à remplacer $ a $ et $ b $ par deux autres entiers plus petits $ u $ et $ v $ tels que $ a^{b}\equiv u^{v} \ \left[n\right] $
On utilise la propriété :
$ a\equiv u \ \left[n\right] \Rightarrow a^{b}\equiv u^{b} \ \left[n\right] $
pour remplacer $ a $ par un entier $ u $ plus petit, par exemple le reste de la division euclidienne de $ a $ par $ n $
On calcule ensuite les puissances successives de $ u $ ($ u^{2}, u^{3}, . . . $) et on cherche un entier $ k $ tel que $ u^{k}\equiv 1 \ \left[n\right] $ (un tel entier existe si $ u $ et $ n $ sont premiers entre eux — l'exemple 2 traite un cas où il n'est pas possible de trouver un tel entier)
On effectue alors la division euclidienne de $ b $ par $ k $ :
$ b=kq+v $
donc :
$ u^{b}=u^{kq+v}=u^{kq}\times u^{v}=\left[u^{k}\right]^{q}\times u^{v} $
$ u^{b}\equiv \left[u^{k}\right]^{q}\times u^{v}\equiv 1^{q}\times u^{v}\equiv u^{v} \ \left[n\right] $
On peut conclure :
$ a^{b}\equiv u^{b}\equiv u^{v} \ \left[n\right] $
Donc $ a^{b} $ et $ u^{v} $ ont le même reste dans la division par $ n $. Ce reste est alors facile à calculer car $ u $ et $ v $ sont "petits".
Exemple
On recherche le reste de la division euclidienne de $ 12\ 345^{2000} $ par 7.
On effectue tout d'abord la division euclidienne de $12\,345$ par $7$. Le quotient est $1\,763$ et le reste est $4$.
Donc $ 12\,345\equiv 4 \ \left[7\right] $ et $ 12\,345^{2\,000}\equiv 4^{2\,000} \ \left[7\right] $
$ 4^{2}=16\equiv 2 \ \left[7\right] $
$ 4^{3}=64\equiv 1 \ \left[7\right] $
On effectue la division euclidienne de $2\,000$ par $3$ : $2\,000=666 \times 3+2$
Donc :
$ 4^{2\,000}=4^{666\times 3+2}=\left[4^{3}\right]^{666}\times 4^{2}\equiv 1^{666}\times 4^{2}=16 \ \left[7\right] $
- Le reste de la division euclidienne de $ 12\ 345^{2000} $ par 7 est donc le même que le reste de la division euclidienne de 16 par 7 c'est à dire 2.
Exemple
On recherche le reste de la division euclidienne de $ 12\ 344^{2000} $ par 6.
On effectue tout d'abord la division euclidienne de $12\,344$ par $6$. Le quotient est $2\,057$ et le reste est $2$.
Donc $ 12\,344\equiv 2 \ \left[6\right] $ et $ 12\,344^{2\,000}\equiv 2^{2\,000} \ \left[6\right] $
$ 2^{2}\equiv 4 \ \left[6\right] $
$ 2^{3}=8\equiv 2 \ \left[6\right] $
$ 2^{4}=16\equiv 4 \ \left[6\right] $
etc.
Ici on ne peut pas trouver d'entier $ k $ tel que $ 2^{k}\equiv 1 \ \left[6\right] $ mais on remarque que $ 2^{k}\equiv 2 \ \left[6\right] $ si $ k $ est impair et $ 2^{k}\equiv 4 \ \left[6\right] $ si $ k $ est pair (ce résultat se démontre aisément par récurrence)
Donc :
$ 2^{2\,000}\equiv 4 \ \left[6\right] $
Le reste de la division euclidienne de $ 12\ 344^{2000} $ par 6 est donc 4.