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 montrer que $7$ ne divise jamais $u_n$ .

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

1. On calcule les premières puissances modulo $7$ : $2^1\equiv2$ , $2^2\equiv4$ , $2^3\equiv1$ modulo $7$ . La période est $T=3$ . Selon la congruence 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[7].

2. $2^n-1$ est divisible par $7$ si et seulement si $2^n\equiv1$ modulo $7$ , d'où $n\equiv0$ modulo $3$ . Conclusion : $7\mid 2^n-1$ exactement lorsque $n$ est multiple de $3$ .

3. De même $3^1\equiv3$ , $3^2\equiv2$ , $3^3\equiv6$ , $3^4\equiv4$ , $3^5\equiv5$ , $3^6\equiv1$ modulo $7$ (période $6$ ). On calcule $u_n=2^n+3^n$ modulo $7$ sur une période commune $\mathrm{ppcm}(3,6)=6$ : pour $n\bmod6\in\{0,1,2,3,4,5\}$ , on obtient $u_n\equiv2,5,6,0,6,2$ modulo $7$ . Ainsi $u_n$ est divisible par $7$ uniquement pour $n\equiv3$ modulo $6$ — et non « jamais ». Conclusion : $7\mid u_n\iff n\equiv3$ modulo $6$ . *(Le tableau de congruences est la preuve ; l'énoncé « $7$ ne divise jamais $u_n$ » est contredit par le calcul.)*

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$