R-BArithmétique

Congruences et restes des puissances $a^n$

Idée directrice

Les puissances de $a$ modulo $m$ sont périodiques : il existe un plus petit $T$ tel que $a^T\equiv1\,[m]$ . Une fois $T$ trouvé, le reste de $a^n$ ne dépend que de $n \bmod T$ . Tout l'exercice consiste à débusquer cette période, puis à discuter selon la classe de $n$ .

Signature de reconnaissance — l'énoncé se trahit ainsi

« Déterminer suivant les valeurs de $n$ le reste de $a^n$ modulo $m$ » ; tableau de congruences.

Sujet principal

Exercice 3 — reste d'une puissance et divisibilité d'une suite

3 questionsCorrigé masqué

Déterminer le reste de la division de $2^n$ par $7$ selon les valeurs de $n\in\N$ .
En déduire l'ensemble des entiers $n$ tels que $7\mid 2^n-1$ .
On pose $u_n=2^n+3^n$ . Déterminer le reste de $u_n$ modulo $7$ , puis déterminer les entiers $n$ pour lesquels $7$ divise $u_n$ .

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : les puissances modulo $7$ sont périodiques ; on cherche la première puissance congrue à $1$ . $2^1\equiv2$ , $2^2\equiv4$ , $2^3=8\equiv1\pmod 7$ . Donc $2^{3k}=(2^3)^k\equiv1$ , puis $2^{3k+1}\equiv2$ et $2^{3k+2}\equiv4$ . En écrivant $n=3k+r$ avec $r\in\{0,1,2\}$ le reste de $n$ modulo $3$ :

2^n\equiv\begin{cases}1&\text{si }n\equiv0\ [3]\\ 2&\text{si }n\equiv1\ [3]\\ 4&\text{si }n\equiv2\ [3]\end{cases}\quad\pmod 7

2. $7$ divise $2^n-1$ si et seulement si $2^n\equiv1\pmod 7$ , c'est-à-dire, d'après le tableau, si et seulement si $n\equiv0\pmod 3$ : les entiers cherchés sont les multiples de $3$ .

3. Idée : deux périodes ( $3$ pour $2^n$ , $6$ pour $3^n$ ) $\Rightarrow$ raisonner modulo leur ppcm $6$ . $3^1\equiv3$ , $3^2\equiv2$ , $3^3\equiv6$ , $3^4\equiv4$ , $3^5\equiv5$ , $3^6\equiv1\pmod 7$ . Selon le reste $r$ de $n$ modulo $6$ :

$r$	0	1	2	3	4	5
$2^n\bmod 7$	1	2	4	1	2	4
$3^n\bmod 7$	1	3	2	6	4	5
$u_n\bmod 7$	2	5	6	0	6	2

Le reste de $u_n$ modulo $7$ est donc $2,5,6,0,6,2$ selon que $n\equiv0,1,2,3,4,5\pmod 6$ , et $u_n$ n'est divisible par $7$ que dans un cas :

7\mid u_n\iff n\equiv3\pmod 6

Méthode / Automatismes

Chercher la période $T$ : plus petit $T\geq1$ avec $a^T\equiv1\,[m]$ (existe si $\pgcd(a,m)=1$ ).
Reste de $a^n$ : écrire $n=Tq+r$ , alors $a^n\equiv a^r\,[m]$ .
Somme de deux périodicités : travailler modulo le ppcm des deux périodes, avec un tableau.
Carré parfait : un carré est $\equiv0$ ou $1\,[4]$ , $\equiv0$ ou $1\,[3]$ ; outil classique pour montrer qu'un nombre n'est pas un carré.

Pièges classiques

Chercher $a^n \bmod m$ sans trouver d'abord la période $T$ . Appliquer Euler/Fermat hors hypothèses ( $a$ non premier avec $m$ ). Confondre $n\bmod T$ avec le reste de $a^n$ .

Où ce scénario est tombé

Bac 2020 — session principale· Exercice 3 (arithmétique)attestéLa périodicité des restes réduit le problème à un nombre fini de cas ; la combinaison linéaire fait circuler la divisibilité.

Bac 2023 — session principale (couverture partielle)· Exercice 3 (arithmétique)probableCongruences / équation dans Z — scénario exact à confirmer sur le scan.

Bac 2024 — session principale (partiel)· Exercice 4 (arithmétique)probableCongruences ou diophantienne — à confirmer sur le scan.

Congruences et restes des puissances ana^nan

Où ce scénario est tombé

Congruences et restes des puissances $a^n$