Rechercher le reste de la division de an par b Méthode

Sommaire

1Déterminer les restes successifs des premières puissances de a par b 2Exprimer n en fonction p 3Remplacer dans l'expression de a^n 4En déduire la table de congruence

Afin de rechercher le reste de la division de a^n par b, on détermine les restes successifs pour les différentes puissances de a et on utilise les congruences.

Déterminer les restes de la division euclidienne de 5^n par 7 suivant les valeurs de n.

Etape 1

Déterminer les restes successifs des premières puissances de a par b

On calcule les restes successifs des premières puissances de a par b. On s'arrête pour le premier entier naturel p\gt1 tel que :

\ce{a^{p} #1}\left[ b \right]

Le cycle est donc de p.

On a les restes successifs de la division par 7 des puissances de 5 suivantes :

  • 5^0\ce{#}1\left[ 7 \right]
  • 5^1\ce{#}5\left[ 7 \right]
  • 5^2\ce{#}4\left[ 7 \right]
  • 5^3\ce{#}6\left[ 7 \right]
  • 5^4\ce{#}2\left[ 7 \right]
  • 5^5\ce{#}3\left[ 7 \right]
  • 5^6\ce{#}1\left[ 7 \right]

Le cycle est donc de 6.

Etape 2

Exprimer n en fonction p

On exprime n en fonction de p :

n = p\times k +r avec 0 \leq r \lt p

On divise n par 6, on obtient :

n = 6\times k +r avec 0 \leq r \lt 6

Etape 3

Remplacer dans l'expression de a^n

On remplace dans l'expression de a^n :

a^n = a^{p\times k +r} = \left(a^p\right)^k \times a^r

Comme a^p \ce{#} 1\left[ b\right], on en déduit que \left(a^p\right)^k \ce{#} 1^k\left[ b\right] \ce{#} 1\left[ b\right]

Donc \left(a^p\right)^k \times a^r \ce{#} a^r\left[ b\right]

On remplace dans l'expression de a^n :

5^n = 5^{6\times k +r} = \left(5^6\right)^k \times 5^r

Comme 5^6 \ce{#} 1\left[ 7\right], on en déduit que \left(5^6\right)^k \ce{#} 1^k\left[ 7\right] \ce{#} 1\left[ 7\right].

Donc \left(5^6\right)^k \times 5^r \ce{#} 5^r\left[7\right].

Etape 4

En déduire la table de congruence

Comme a^n \ce{#}a^r \left[ b \right] on détermine les restes de la division euclidienne de a^r par b pour 0 \leq r \lt p. On reprend les valeurs calculées à l'étape 1.

On récapitule les résultats sous forme d'un tableau.

En reprenant les résultats de l'étape 1, on obtient alors la table de congruence modulo 7 suivante :

n\ce{#}\left[ 6 \right] 0 1 2 3 4 5
5^n\ce{#}\left[ 7\right] 1 5 4 6 2 3