Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Calculer un reste à l'aide de congruences

Situation

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 345200012\ 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 aba^{b} par nn on va utiliser la caractérisation du reste à l'aide de congruence :

rr et le reste de la division euclidienne de mm par nn ⇔\Leftrightarrow {r≡m[n]0⩽r<∣n∣\left\{ \begin{matrix} r\equiv m \left[n\right] \\ 0 \leqslant r <|n| \end{matrix}\right.

et on va chercher à remplacer aa et bb par deux autres entiers plus petits uu et vv tels que ab≡uv[n]a^{b}\equiv u^{v} \left[n\right]

  1. On utilise la propriété :

    a≡u[n]⇒ab≡ub[n]a\equiv u \left[n\right] \Rightarrow a^{b}\equiv u^{b} \left[n\right]

    pour remplacer aa par un entier uu plus petit, par exemple le reste de la division euclidienne de aa par nn

  2. On calcule ensuite les puissances successives de uu (u2,u3,...u^{2}, u^{3}, . . . ) et on cherche un entier k tel que uk≡1[n]u^{k}\equiv 1 \left[n\right] (un tel entier existe si uu et nn 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 bb par kk :

    b=kq+vb=kq+v

    donc :

    ub=ukq+v=ukq×uv=[uk]q×uvu^{b}=u^{kq+v}=u^{kq}\times u^{v}=\left[u^{k}\right]^{q}\times u^{v}

    ub≡[uk]q×uv≡1q×uv≡uv[n]u^{b}\equiv \left[u^{k}\right]^{q}\times u^{v}\equiv 1^{q}\times u^{v}\equiv u^{v} \left[n\right]

  3. On peut conclure :

    ab≡ub≡uv[n]a^{b}\equiv u^{b}\equiv u^{v} \left[n\right]

    Donc aba^{b} et uvu^{v} ont le même reste dans la division par nn. Ce reste est alors facile à calculer car uu et vv sont "petits".

Exemple 1

On recherche le reste de la division euclidienne de 12 345200012\ 345^{2000} par 7.

  1. On effectue tout d'abord la division euclidienne de 12\ 345 par 7. Le quotient est 1763 et le reste est 4.

    Donc 12345≡4[7]12 345\equiv 4 \left[7\right] et 12 3452000≡42000[7]12\ 345^{2 000}\equiv 4^{2 000} \left[7\right]

  2. 42=16≡2[7]4^{2}=16\equiv 2 \left[7\right]

    43=64≡1[7]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 :

    42000=4666×3+2=[43]666×42≡1666×42=16[7]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]

  3. Le reste de la division euclidienne de 12 345200012\ 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 2

On recherche le reste de la division euclidienne de 12 344200012\ 344^{2000} par 6.

  1. On effectue tout d'abord la division euclidienne de 12\ 344 par 6. Le quotient est 2057 et le reste est 2.

    Donc 12344≡2[6]12 344\equiv 2 \left[6\right] et 12 3452000≡22000[6]12\ 345^{2 000}\equiv 2^{2 000} \left[6\right]

  2. 22≡4[6]2^{2}\equiv 4 \left[6\right]

    23=8≡2[6]2^{3}=8\equiv 2 \left[6\right]

    24=16≡4[6]2^{4}=16\equiv 4 \left[6\right]

    etc.

    Ici on ne peut pas trouver d'entier kk tel que 2k≡1[6]2^{k}\equiv 1 \left[6\right] mais on remarque que 2k≡2[6]2^{k}\equiv 2 \left[6\right] si k est impair et 2k≡4[6]2^{k}\equiv 4 \left[6\right] si k est pair (ce résultat peut se démontrer facilement par récurrence; faites-le!)

    Donc :

    22000≡4[6]2^{2 000}\equiv 4 \left[6\right]

    Le reste de la division euclidienne de 12 344200012\ 344^{2000} par 6 est donc 4.

Dans ce chapitre :

Cours

Exercices

Méthodes