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 congruenceAfin 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.
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.
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
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].
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 |