Terminale › Arithmétique › Déterminer le reste de a^k modulo n

Déterminer le reste de a^k modulo n : méthode (Maths expertes)

Méthode

Déterminer le reste de a^k modulo n

On remplace $a$ par son reste modulo $n$ (ou par un entier congru plus simple, éventuellement négatif comme $-1$).
On calcule les puissances successives jusqu'à trouver un exposant $m$ tel que $a^m \equiv 1 \;[n]$ (ou $\equiv -1$).
On effectue la division euclidienne $k = mq + s$ avec $0 \leqslant s < m$.
On écrit $a^k = (a^m)^q \times a^s \equiv a^s \;[n]$.
On conclut en donnant un reste entre $0$ et $n-1$.

Exemple : $3^4 = 81 \equiv 1 \;[10]$ et $2027 = 4 \times 506 + 3$, donc $3^{2027} \equiv 3^3 = 27 \equiv 7 \;[10]$. Le chiffre des unités de $3^{2027}$ est $7$.

Exemple

Tableau de congruences : n² + n + 1 n'est jamais divisible par 5

On étudie tous les restes possibles de $n$ modulo $5$.

$n \equiv \dots \;[5]$	$0$	$1$	$2$	$3$	$4$
$n^2 \equiv$	$0$	$1$	$4$	$4$	$1$
$n^2 + n + 1 \equiv$	$1$	$3$	$2$	$3$	$1$

Pour $n \equiv 2$ : $4 + 2 + 1 = 7 \equiv 2$. Pour $n \equiv 3$ : $4 + 3 + 1 = 8 \equiv 3$. Pour $n \equiv 4$ : $1 + 4 + 1 = 6 \equiv 1$.

La dernière ligne ne contient jamais $0$ : pour tout entier $n$, $5$ ne divise pas $n^2 + n + 1$.

Exemple

Une divisibilité pour tout n

Montrons que pour tout $n \in \mathbb{N}$, $7 \mid 3^{2n+1} + 2^{n+2}$.

$3^{2n+1} = 3 \times 9^n$ et $9 \equiv 2 \;[7]$, donc $3^{2n+1} \equiv 3 \times 2^n \;[7]$. De plus $2^{n+2} = 4 \times 2^n$. Ainsi $$3^{2n+1} + 2^{n+2} \equiv 3 \times 2^n + 4 \times 2^n = 7 \times 2^n \equiv 0 \;[7].$$

Remarque

Critères de divisibilité

Comme $10 \equiv 1 \;[9]$, on a $10^k \equiv 1 \;[9]$ pour tout $k$ : un entier est congru modulo $9$ à la somme de ses chiffres. Par exemple $2025 \equiv 2+0+2+5 = 9 \equiv 0 \;[9]$, donc $9 \mid 2025$.

Comme $10 \equiv -1 \;[11]$, un entier est congru modulo $11$ à la somme alternée de ses chiffres, en partant des unités.

S’entraîner

Dans le cours

Arithmétique : Déterminer le reste de a^k modulo n