R-JArithmétique

L'exercice de Fermat complet : reste de $x^{52}$ , $x^{261}\equiv x$ , équation $x^{29}\equiv 2$ modulo 53, système de congruences

Idée directrice

Quand l'exercice d'arithmétique fait apparaître un nombre premier $p$ et de grandes puissances, le fil est le petit théorème de Fermat : $x^{p-1}\equiv1$ réduit tout exposant modulo $p-1$ ; on en tire une congruence « universelle » ( $x^{261}\equiv x$ ), qui permet de résoudre une équation du type $x^{29}\equiv2$ en élevant à une puissance bien choisie ; le tout se termine par un système de congruences à deux modules premiers entre eux.

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

« Soit $x$ un entier non nul premier avec $p$ … déterminer le reste modulo $p$ de $x^{p-1}$ » ; « montrer que $x^{\dots}\equiv x$ (mod $p$ ) » ; « montrer que $2^9$ est une solution de $(E)$ » ; « en déduire que $x\equiv\dots$ (mod $p$ ) » ; « résoudre dans $\Z$ le système ».

Sujet principal

Exercice 3 — arithmétique (4 points), dans l’esprit de la session 2017

3 questionsCorrigé masqué

On rappelle que $53$ est un nombre premier.

Soit $x$ un entier non nul premier avec $53$ .
1. Déterminer le reste modulo $53$ de $x^{52}$ .
2. Montrer que $x^{261}\equiv x\pmod{53}$ , puis justifier que cette congruence reste vraie pour tout entier $x$ .
On considère dans $\Z$ l'équation $(E_1)\ :\ x^{29}\equiv2\pmod{53}$ .
1. Montrer que $2^9$ est une solution de $(E_1)$ .
2. Soit $x$ une solution de $(E_1)$ . Montrer que $x$ est premier avec $53$ .
3. Montrer que $x^{261}\equiv2^9\pmod{53}$ et en déduire que $x\equiv2^9\pmod{53}$ .
4. Montrer que $2^9\equiv35\pmod{53}$ et résoudre $(E_1)$ dans $\Z$ .
Résoudre dans $\Z$ le système $(S)\ :\ \begin{cases}x^{29}\equiv2\pmod{53}\\ x\equiv34\pmod{71}\end{cases}$ (on donne $3\times71-4\times53=1$ ).

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

1.a Idée : petit théorème de Fermat avec $p=53$ . $53$ est premier et ne divise pas $x$ , donc $x^{52}\equiv1\pmod{53}$ : le reste est $1$ .

1.b Idée : réduire l'exposant modulo $52$ . $261=5\times52+1$ , donc $x^{261}=(x^{52})^5\cdot x\equiv1^5\cdot x=x\pmod{53}$ . Si $53$ divise $x$ , les deux membres sont congrus à $0$ : la congruence $x^{261}\equiv x$ vaut pour tout entier $x$ .

2.a $(2^9)^{29}=2^{261}\equiv2\pmod{53}$ d'après 1.b appliqué à $x=2$ : $2^9$ est solution de $(E_1)$ .

2.b Idée : raisonner par l'absurde. Si $53$ divisait $x$ , alors $x^{29}\equiv0\pmod{53}$ , et non $2$ . Donc $53$ ne divise pas $x$ ; $53$ étant premier, $x$ est premier avec $53$ .

2.c Idée : élever $(E_1)$ à la puissance $9$ pour retrouver l'exposant $261$ . De $x^{29}\equiv2$ on tire $x^{261}=(x^{29})^9\equiv2^9\pmod{53}$ . Or, $x$ étant premier avec $53$ , $x^{261}\equiv x$ (1.b). Par suite $x\equiv2^9\pmod{53}$ . Réciproquement $2^9$ convient (2.a), et toute solution lui est congrue :

2.d $2^9=512=9\times53+35$ , donc $2^9\equiv35\pmod{53}$ , et

(E_1)\iff x\equiv35\pmod{53},\qquad \mathcal S_1=\{35+53k\ ;\ k\in\Z\}

3. Idée : deux congruences à modules premiers entre eux $\Rightarrow$ équation diophantienne. $x=35+53u=34+71v$ donne $53u-71v=-1$ . L'égalité donnée, changée de signe, s'écrit $53\times4-71\times3=-1$ : une solution particulière est $(u,v)=(4,3)$ . Alors $53(u-4)=71(v-3)$ ; $71$ premier avec $53$ divise $u-4$ (Gauss), d'où $u=4+71k$ et $x=35+53(4+71k)=247+3763k$ . Vérification : $247=4\times53+35$ et $247=3\times71+34$ .

\boxed{\,x\equiv247\pmod{3763}\,}\qquad(3763=53\times71)

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 02

Drill R-J.1 — restes de $5^n$ modulo 8 et congruence d’une suite

3 questionsCorrigé masqué

Pour tout entier naturel $n$ , on pose $a_n=5^n+3$ .

Déterminer, suivant les valeurs de $n$ , le reste modulo $8$ de $5^n$ .
En déduire que pour tout entier naturel $n$ pair, $a_n\equiv4\pmod 8$ , et déterminer le reste de $a_n$ modulo $8$ lorsque $n$ est impair.
Existe-t-il un entier $n$ tel que $8$ divise $a_n$ ? Justifier.

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

1. $5^0\equiv1$ , $5^1\equiv5$ , $5^2=25\equiv1\pmod 8$ : période $2$ . Donc $5^n\equiv1$ si $n$ est pair et $5^n\equiv5$ si $n$ est impair.

2. Pour $n$ pair, $a_n\equiv1+3=4\pmod 8$ ; pour $n$ impair, $a_n\equiv5+3=8\equiv0\pmod 8$ .

3. Oui : pour tout $n$ impair, $8$ divise $a_n$ (par exemple $a_1=8$ , $a_3=128$ ) ; jamais pour $n$ pair, où le reste vaut $4$ .

Entraînement 02 / 02

Drill R-J.2 — Fermat pour un produit de modules : divisibilité par 30

3 questionsCorrigé masqué

Soit $n$ un entier naturel.

En utilisant le petit théorème de Fermat, montrer que $n^5\equiv n\pmod 5$ et que $n^5\equiv n\pmod 3$ .
Montrer que $n^5-n$ est pair.
En déduire que $30$ divise $n^5-n$ pour tout entier naturel $n$ .

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

1. Corollaire de Fermat avec $p=5$ : $n^5\equiv n\pmod 5$ . Avec $p=3$ : $n^3\equiv n$ , donc $n^5=n^3\cdot n^2\equiv n\cdot n^2=n^3\equiv n\pmod 3$ .

2. $n^5$ et $n$ ont la même parité, donc $n^5-n$ est pair : $n^5\equiv n\pmod 2$ .

3. $2$ , $3$ et $5$ divisent $n^5-n$ et sont premiers entre eux deux à deux ; par le lemme de Gauss (appliqué deux fois), leur produit $30$ divise $n^5-n$ .

Méthode / Automatismes

Nombre premier $p$ + grandes puissances : Fermat, $x^{p-1}\equiv1$ pour $x$ premier avec $p$ ; réduire l'exposant modulo $p-1$ ( $261=5\times52+1$ ).
Équation $x^m\equiv c\pmod p$ : chercher un exposant $k$ tel que $mk\equiv1\pmod{p-1}$ ( $29\times9=261$ ) et élever à la puissance $k$ ; vérifier d'abord que toute solution est première avec $p$ .
Toujours réduire la solution ( $2^9=512\equiv35$ ) et écrire l'ensemble des solutions dans $\Z$ , pas seulement un représentant.
Système de congruences : $x=r_1+m_1u=r_2+m_2v$ , Bézout (souvent donné), Gauss, réponse modulo $m_1m_2$ .

Pièges classiques

Appliquer Fermat à un $x$ multiple de $53$ ( $x^{52}\equiv0$ , pas $1$ ) ; écrire $x^{261}\equiv x$ sans avoir réduit $261$ modulo $52$ (et non modulo $53$ ) ; oublier de vérifier que $2^9$ est bien solution avant de conclure l'équivalence ; se tromper de signe dans la relation de Bézout et obtenir $x\equiv-177$ au lieu de $247$ — la vérification finale sur les deux modules protège.

L'exercice de Fermat complet : reste de x52x^{52}x52, x261≡xx^{261}\equiv xx261≡x, équation x29≡2x^{29}\equiv 2x29≡2 modulo 53, système de congruences

Exercices d'entraînement — une nuance à la fois

L'exercice de Fermat complet : reste de $x^{52}$ , $x^{261}\equiv x$ , équation $x^{29}\equiv 2$ modulo 53, système de congruences