Rechercher le reste de la division de aⁿ par b Exercice

On a :

5^0=0\times9+1

Or, si r est le reste de la division euclidienne de a par b, on a : a\equiv r \left[ b \right]

Donc : 5^0\equiv 1 \left[ 9 \right]

De même on a :

• 5^1\equiv 5 \left[ 9 \right] car 5^1=0\times9+5
• 5^2\equiv 7 \left[ 9 \right] car 25=2\times9+7
• 5^3\equiv 8 \left[ 9 \right] car 125=13\times9+8

De plus, on sait que si a\equiv a^{'} \left[ n \right] et b\equiv b^{'} \left[ n \right], alors ab\equiv a^{'}b^{'} \left[ n \right]

Donc, on a :

• 5^4\equiv 8\times5 \left[ 9 \right] \equiv 40\left[ 9 \right]\equiv 4 \left[ 9 \right] car 5^4=5^3\times5^1 et 40=4\times9+4
• 5^5\equiv 4\times5 \left[ 9 \right] \equiv 20\left[ 9 \right]\equiv 2 \left[ 9 \right] car 5^5=5^4\times5^1 et 20=2\times9+2
• 5^6\equiv 2\times5 \left[ 9 \right] \equiv 10\left[ 9 \right]\equiv 1 \left[ 9 \right] car 5^6=5^5\times5^1 et 10=1\times9+1

On remarque donc que le cycle de congruence est de longueur 6.

Soit alors n un entier naturel. n peut s'écrire sous la forme :

n = 6k + r avec 0 \leq r \lt 6 et k un entier naturel.

On a alors :

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

Or, on sait que si a\equiv b \left[ n \right] alors pour tout entier k, a^k\equiv b^k \left[ n \right]

On a donc \left( 5^6 \right)^k\equiv 1 \left[ 9 \right] et donc :

5^n \equiv 5^r \left[ 9 \right]

On obtient donc la table de congruence modulo 9 suivante où la première colonne se lit "si n est congru à 0 modulo 6, alors le reste de la division euclidienne de 5^n par 9 est 1" :

On a :

3^0=0\times7+1

Or, si r est le reste de la division euclidienne de a par b, on a : a\equiv r \left[ b \right]

Donc : 3^0\equiv 1 \left[ 7 \right]

De même on a :

• 3^1\equiv 3 \left[ 7 \right] car 3^1=0\times7+3
• 3^2\equiv 2 \left[ 7 \right] car 9=1\times7+2
• 3^3\equiv 6 \left[ 7 \right] car 27=3\times7+6

De plus, on sait que si a\equiv a^{'} \left[ n \right] et b\equiv b^{'} \left[ n \right], alors ab\equiv a^{'}b^{'} \left[ n \right]

Donc, on a :

• 3^4\equiv 2\times2 \left[ 7 \right] \equiv 4\left[ 7 \right] car 3^4=3^2\times3^2
• 3^5\equiv 4\times3 \left[ 7 \right] \equiv 12\left[ 7 \right]\equiv 5 \left[ 7 \right] car 3^5=3^4\times3^1 et 12=1\times7+5
• 3^6\equiv 5\times3 \left[ 7 \right] \equiv 15\left[ 7 \right]\equiv 1 \left[ 7 \right] car 3^6=3^5\times3^1 et 15=2\times7+1

On remarque donc que le cycle de congruence est de longueur 6.

Soit alors n un entier naturel. n peut s'écrire sous la forme :

n = 6k + r avec 0 \leq r \lt 6 et k un entier naturel.

On a alors :

3^n=3^{6k}\times3^{r}=\left( 3^6 \right)^k\times3^r

Or, on sait que si a\equiv b \left[ n \right] alors pour tout entier k, a^k\equiv b^k \left[ n \right]

On a donc \left( 3^6 \right)^k\equiv 1 \left[ 7 \right] et donc :

3^n \equiv 3^r \left[ 7 \right]

On obtient donc la table de congruence modulo 7 suivante où la première colonne se lit "si n est congru à 0 modulo 6, alors le reste de la division euclidienne de 3^n par 7 est 1" :

On a :

5^0=0\times7+1

Or, si r est le reste de la division euclidienne de a par b, on a : a\equiv r \left[ b \right]

Donc : 5^0\equiv 1 \left[ 7 \right]

De même on a :

• 5^1\equiv 5 \left[ 7 \right] car 5^1=0\times7+5
• 5^2\equiv 4 \left[ 7 \right] car 25=3\times7+4
• 5^3\equiv 6 \left[ 7 \right] car 125=17\times7+6

De plus, on sait que si a\equiv a^{'} \left[ n \right] et b\equiv b^{'} \left[ n \right], alors ab\equiv a^{'}b^{'} \left[ n \right]

Donc, on a :

• 5^4\equiv 4\times4 \left[ 7 \right] \equiv 2\left[ 7 \right] car 5^4=5^2\times5^2
• 5^5\equiv 2\times5 \left[ 7 \right] \equiv 10\left[ 7 \right]\equiv 3 \left[ 7 \right] car 5^5=5^4\times5^1 et 10=1\times7+3
• 5^6\equiv 3\times5 \left[ 7 \right] \equiv 15\left[ 7 \right]\equiv 1 \left[ 7 \right] car 5^6=5^5\times5^1 et 15=2\times7+1

On remarque donc que le cycle de congruence est de longueur 6.

Soit alors n un entier naturel. n peut s'écrire sous la forme :

n = 6k + r avec 0 \leq r \lt 6 et k un entier naturel.

On a alors :

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

Or, on sait que si a\equiv b \left[ n \right] alors pour tout entier k, a^k\equiv b^k \left[ n \right]

On a donc \left( 5^6 \right)^k\equiv 1 \left[ 7 \right] et donc :

5^n \equiv 5^r \left[ 7 \right]

On obtient donc la table de congruence modulo 7 suivante où la première colonne se lit "si n est congru à 0 modulo 6, alors le reste de la division euclidienne de 5^n par 7 est 1" :

On a :

8^0=0\times11+1

Or, si r est le reste de la division euclidienne de a par b, on a : a\equiv r \left[ b \right]

Donc : 8^0\equiv 1 \left[ 11 \right]

De même on a :

• 8^1\equiv 8 \left[ 11 \right]
• 8^2\equiv 9 \left[ 11 \right] car 64=5\times11+9

De plus, on sait que si a\equiv a^{'} \left[ n \right] et b\equiv b^{'} \left[ n \right], alors ab\equiv a^{'}b^{'} \left[ n \right]

Donc, on a :

• 8^3\equiv 9\times8 \left[ 11 \right] \equiv72\left[ 11 \right]\equiv6\left[ 11 \right] car 8^3=8^2\times8^1 et 72=6\times11+6
• 8^4\equiv 6\times8 \left[ 11 \right] \equiv 48\left[ 11 \right] \equiv 4\left[ 11 \right] car 8^4=8^3\times8^1 et 48=4\times11+4
• 8^5\equiv 4\times8 \left[ 11 \right] \equiv 32\left[ 11 \right]\equiv 10 \left[ 11 \right] car 8^5=8^4\times8^1 et 32=2\times11+10
• 8^6\equiv 6\times6 \left[ 11 \right] \equiv 36\left[ 11 \right]\equiv 3 \left[ 11 \right] car 8^6=8^3\times8^3 et 36=3\times11+3

• 8^7\equiv 3\times8 \left[ 11 \right] \equiv 24\left[ 11 \right]\equiv 2 \left[ 11 \right] car 8^7=8^6\times8^1 et 24=2\times11+2

• 8^8\equiv 2\times8 \left[ 11 \right] \equiv 16\left[ 11 \right]\equiv 5 \left[ 11 \right] car 8^8=8^7\times8^1 et 16=1\times11+5

• 8^9\equiv 5\times8 \left[ 11 \right] \equiv 40\left[ 11 \right]\equiv 7 \left[ 11 \right] car 8^9=8^8\times8^1 et 40=3\times11+7

• 8^{10}\equiv 7\times8 \left[ 11 \right] \equiv 56\left[ 11 \right]\equiv 1 \left[ 11 \right] car 8^‘{10}=8^9\times8^1 et 56=5\times11+1

On remarque donc que le cycle de congruence est de longueur 10.

Soit alors n un entier naturel. n peut s'écrire sous la forme :

n = 10k + r avec 0 \leq r \lt 10 et k un entier naturel.

On a alors :

8^n=8^{10k}\times8^{r}=\left( 8^{10} \right)^k\times8^r

Or, on sait que si a\equiv b \left[ n \right] alors pour tout entier k, a^k\equiv b^k \left[ n \right]

On a donc \left( 8^{10} \right)^k\equiv 1 \left[ 11 \right] et donc :

8^n \equiv 8^r \left[ 11 \right]

On obtient donc la table de congruence modulo 11 suivante où la première colonne se lit "si n est congru à 0 modulo 10, alors le reste de la division euclidienne de 8^n par 11 est 1" :

On a :

7^0=0\times5+1

Or, si r est le reste de la division euclidienne de a par b, on a : a\equiv r \left[ b \right]

Donc : 7^0\equiv 1 \left[ 5 \right]

De même on a :

• 7^1\equiv 2 \left[ 5 \right] car 7^1=1\times5+2
• 7^2\equiv 4 \left[ 5 \right] car 49=9\times5+4

De plus, on sait que si a\equiv a^{'} \left[ n \right] et b\equiv b^{'} \left[ n \right], alors ab\equiv a^{'}b^{'} \left[ n \right]

Donc, on a :

• 7^3\equiv 4\times2 \left[ 5 \right] \equiv 3\left[ 5 \right] car 7^3=7^2\times7^1

• 7^4\equiv 3\times2 \left[ 5 \right] \equiv 6\left[ 5 \right]\equiv 1 \left[ 5 \right] car 7^4=7^3\times7^1 et 6=1\times5+1

On remarque donc que le cycle de congruence est de longueur 4.

Soit alors n un entier naturel. n peut s'écrire sous la forme :

n = 4k + r avec 0 \leq r \lt 4 et k un entier naturel.

On a alors :

7^n=7^{4k}\times7^{r}=\left( 7^4 \right)^k\times7^r

Or, on sait que si a\equiv b \left[ n \right] alors pour tout entier k, a^k\equiv b^k \left[ n \right]

On a donc \left( 7^4 \right)^k\equiv 1 \left[ 5 \right] et donc :

7^n \equiv 7^r \left[ 5 \right]

On obtient donc la table de congruence modulo 5 suivante où la première colonne se lit "si n est congru à 0 modulo 4, alors le reste de la division euclidienne de 7^n par 5 est 1" :

On a :

2^0=0\times5+1

Or, si r est le reste de la division euclidienne de a par b, on a : a\equiv r \left[ b \right]

Donc : 2^0\equiv 1 \left[ 5 \right]

De même on a :

• 2^1\equiv 2 \left[ 5 \right] car 2^1=0\times5+2
• 2^2\equiv 4 \left[ 5 \right] car 4=0\times5+4
• 2^3\equiv 3 \left[ 5 \right] car 8=1\times5+3
• 2^4\equiv 1 \left[ 5 \right] car 16=3\times5+1

On remarque donc que le cycle de congruence est de longueur 4.

Soit alors n un entier naturel. n peut s'écrire sous la forme :

n = 4k + r avec 0 \leq r \lt 4 et k un entier naturel.

On a alors :

2^n=2^{4k}\times2^{r}=\left( 2^4 \right)^k\times2^r

Or, on sait que si a\equiv b \left[ n \right] alors pour tout entier k, a^k\equiv b^k \left[ n \right]

On a donc \left( 2^4 \right)^k\equiv 1 \left[ 5 \right] et donc :

2^n \equiv 2^r \left[ 5 \right]

On obtient donc la table de congruence modulo 5 suivante où la première colonne se lit "si n est congru à 0 modulo 4, alors le reste de la division euclidienne de 2^n par 5 est 1" :

On a :

4^0=0\times5+1

Or, si r est le reste de la division euclidienne de a par b, on a : a\equiv r \left[ b \right]

Donc : 4^0\equiv 1 \left[ 5 \right]

De même on a :

• 4^1\equiv 4 \left[ 5 \right] car 4^1=0\times5+4
• 4^2\equiv 1 \left[ 5 \right] car 16=3\times5+1

On remarque donc que le cycle de congruence est de longueur 2.

Soit alors n un entier naturel. n peut s'écrire sous la forme :

n = 2k + r avec 0 \leq r \lt 1 et k un entier naturel.

On a alors :

4^n=4^{2k}\times4^{r}=\left( 4^2 \right)^k\times4^r

Or, on sait que si a\equiv b \left[ n \right] alors pour tout entier k, a^k\equiv b^k \left[ n \right]

On a donc \left( 4^2 \right)^k\equiv 1 \left[ 5 \right] et donc :

4^n \equiv 4^r \left[ 5 \right]

On obtient donc la table de congruence modulo 5 suivante où la première colonne se lit "si n est congru à 0 modulo 2, alors le reste de la division euclidienne de 4^n par 5 est 1" :