Rechercher le reste de la division de aⁿ par b

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

Déterminer les restes de la division euclidienne de \(\displaystyle{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 \(\displaystyle{p\gt1}\) tel que :

\(\displaystyle{\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 :

\(\displaystyle{5^0\ce{#}1\left[ 7 \right]}\)
\(\displaystyle{5^1\ce{#}5\left[ 7 \right]}\)
\(\displaystyle{5^2\ce{#}4\left[ 7 \right]}\)
\(\displaystyle{5^3\ce{#}6\left[ 7 \right]}\)
\(\displaystyle{5^4\ce{#}2\left[ 7 \right]}\)
\(\displaystyle{5^5\ce{#}3\left[ 7 \right]}\)
\(\displaystyle{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 :

\(\displaystyle{n = p\times k +r}\) avec \(\displaystyle{0 \leq r \lt p}\)

On divise n par 6, on obtient :

\(\displaystyle{n = 6\times k +r}\) avec \(\displaystyle{0 \leq r \lt 6}\)

Etape 3

Remplacer dans l'expression de \(\displaystyle{a^n}\)

On remplace dans l'expression de \(\displaystyle{a^n}\) :

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

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

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

On remplace dans l'expression de \(\displaystyle{a^n}\) :

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

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

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

Etape 4

En déduire la table de congruence

Comme \(\displaystyle{a^n \ce{#}a^r \left[ b \right]}\) on détermine les restes de la division euclidienne de \(\displaystyle{a^r}\) par b pour \(\displaystyle{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 :