R-IArithmétique

L'exercice d'arithmétique complet : divisibilité, Bézout, équation diophantienne, congruence

Idée directrice

L'exercice d'arithmétique du bac (exercice 3, 3 à 4 points, 18 sessions sur 22) suit presque toujours le même fil : une divisibilité transformée en congruence, deux entiers prouvés premiers entre eux, une équation diophantienne résolue par une solution particulière et le théorème de Gauss, puis une congruence inversée grâce à cette solution. Chaque question prépare la suivante : la réponse à la question 1 est l'outil de la question 3.

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

« Montrer que si $d$ divise … alors … $\equiv$ … » ; « en déduire que … sont premiers entre eux » ; « vérifier que le couple … est une solution de $(E)$ » ; « résoudre dans $\Z\times\Z$ » ; « déterminer les entiers $n$ tels que … $\equiv 1$ (mod …) ».

Sujet principal

Exercice 3 — arithmétique (4 points), dans l’esprit des sessions 2023 et 2024

4 questionsCorrigé masqué

Soit $a$ un entier naturel supérieur ou égal à $2$ . On considère dans $\Z\times\Z$ l'équation $(E_a)\ :\ (a^2+a-1)\,x-(a+2)\,y=1$ .

1. Soit $d$ un entier supérieur ou égal à $2$ . Montrer que si $d$ divise $a+2$ , alors $a^2+a-1\equiv 1 \pmod d$ .
2. En déduire que les entiers $a^2+a-1$ et $a+2$ sont premiers entre eux.
1. Vérifier que le couple $(1,\ a-1)$ est une solution de $(E_a)$ .
2. Résoudre dans $\Z\times\Z$ l'équation $(E_a)$ .
Déterminer les entiers $n\in\Z$ tels que $(a+2)\,n\equiv 1 \pmod{a^2+a-1}$ .
Dans cette question, $a=3$ .
1. Écrire l'équation $(E_3)$ et donner ses solutions.
2. Résoudre dans $\Z$ le système $(S)\ :\ \begin{cases} x\equiv 2 \pmod 5 \\ x\equiv 3 \pmod{11}\end{cases}$

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

1.a Idée : une divisibilité se lit comme une congruence, puis on remplace. Si $d$ divise $a+2$ , alors $a\equiv -2 \pmod d$ . Par suite $a^2+a-1\equiv (-2)^2+(-2)-1 = 4-2-1 = 1 \pmod d$ .

1.b Idée : un diviseur commun diviserait aussi $1$ . Soit $d\geq 2$ un diviseur commun de $a^2+a-1$ et de $a+2$ . D'après 1.a, $a^2+a-1\equiv 1 \pmod d$ ; or $d$ divise $a^2+a-1$ , donc $a^2+a-1\equiv 0 \pmod d$ . Il en résulte $1\equiv 0 \pmod d$ , c'est-à-dire $d$ divise $1$ : impossible pour $d\geq 2$ . Le seul diviseur commun positif est $1$ :

\pgcd\big(a^2+a-1,\ a+2\big)=1

2.a Idée : on remplace et on développe. $(a^2+a-1)\times 1-(a+2)(a-1) = a^2+a-1-(a^2+a-2) = 1$ . Le couple $(1,\ a-1)$ est bien solution de $(E_a)$ .

2.b Idée : soustraire la solution particulière, puis Gauss. Soit $(x,y)$ une solution. En retranchant membre à membre $(a^2+a-1)\cdot 1-(a+2)(a-1)=1$ , on obtient $(a^2+a-1)(x-1)=(a+2)(y-a+1)$ . Ainsi $a+2$ divise $(a^2+a-1)(x-1)$ ; comme $a+2$ est premier avec $a^2+a-1$ (question 1.b), le théorème de Gauss donne : $a+2$ divise $x-1$ . Il existe donc $k\in\Z$ tel que $x=1+(a+2)k$ , et en reportant, $y=a-1+(a^2+a-1)k$ . Réciproquement, tout couple de cette forme vérifie $(E_a)$ (développer). D'où

\mathcal S=\Big\{\big(1+(a+2)k,\ \ a-1+(a^2+a-1)k\big)\ ;\ k\in\Z\Big\}

3. Idée : la solution particulière de $(E_a)$ fournit l'inverse de $a+2$ modulo $a^2+a-1$ . De $(a^2+a-1)-(a+2)(a-1)=1$ on tire $(a+2)(a-1)\equiv -1$ , soit $(a+2)(1-a)\equiv 1 \pmod{a^2+a-1}$ . Si $(a+2)n\equiv 1$ , alors en multipliant par $(1-a)$ : $n\equiv (1-a)\big[(a+2)(1-a)\big]\equiv 1-a \pmod{a^2+a-1}$ . Réciproquement $n\equiv 1-a$ convient. Les entiers cherchés sont

n\equiv 1-a \pmod{a^2+a-1},\quad\text{soit } n=1-a+(a^2+a-1)k,\ k\in\Z

4.a Pour $a=3$ : $a^2+a-1=11$ et $a+2=5$ , donc $(E_3)\ :\ 11x-5y=1$ , de solution particulière $(1,2)$ et de solutions $(1+5k,\ 2+11k)$ , $k\in\Z$ .

4.b Idée : traduire le système en équation diophantienne. $x\equiv 2 \pmod 5$ et $x\equiv 3 \pmod{11}$ s'écrivent $x=2+5u=3+11v$ avec $(u,v)\in\Z^2$ , soit $5u-11v=1$ . Comme $5\times 9-11\times 4=1$ , on a $5(u-9)=11(v-4)$ ; $11$ premier avec $5$ divise $u-9$ (Gauss), donc $u=9+11k$ et $x=2+5(9+11k)=47+55k$ . Vérification : $47=9\times 5+2$ et $47=4\times 11+3$ .

\boxed{\,x\equiv 47 \pmod{55}\,}

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

Entraînement 01 / 02

Drill R-I.1 — équation diophantienne avec solution donnée

3 questionsCorrigé masqué

On considère dans $\Z^2$ l'équation $(E)\ :\ 5u-53v=24$ .

Vérifier que $(26,\ 2)$ est une solution de $(E)$ .
Résoudre dans $\Z^2$ l'équation $(E)$ .
Soit $x\in\Z$ . Déterminer, suivant les valeurs de $x$ , les restes possibles modulo $5$ de $x^2-x$ .

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

1. $5\times 26-53\times 2=130-106=24$ : le couple $(26,2)$ est solution.

2. Idée : soustraire la solution particulière puis Gauss. Si $(u,v)$ est solution, $5(u-26)=53(v-2)$ . Comme $53$ est premier (donc premier avec $5$ ), $53$ divise $u-26$ : $u=26+53k$ , puis $v=2+5k$ avec $k\in\Z$ . Réciproquement $5(26+53k)-53(2+5k)=24$ . Les solutions sont les couples $(26+53k,\ 2+5k)$ , $k\in\Z$ .

3. Idée : un tableau des restes suffit. Modulo $5$ , $x$ vaut $0,1,2,3$ ou $4$ et $x^2-x$ vaut respectivement $0,\ 0,\ 2,\ 6\equiv 1,\ 12\equiv 2$ . Les restes possibles de $x^2-x$ modulo $5$ sont donc $0$ , $1$ et $2$ ; en particulier $x^2-x\equiv 1 \pmod 5$ si et seulement si $x\equiv 3 \pmod 5$ .

Entraînement 02 / 02

Drill R-I.2 — d’un système de congruences à une équation diophantienne

2 questionsCorrigé masqué

On considère dans $\Z$ le système de congruences $(S)\ :\ \begin{cases} x\equiv 3 \pmod 5\\ x\equiv 27 \pmod{53}\end{cases}$ ( $x$ entier, congruences modulo $5$ et modulo $53$ ). On rappelle que les solutions de l'équation diophantienne $5u-53v=24$ sont les couples $(26+53k,\ 2+5k)$ , $k\in\Z$ .

Montrer que $x$ est solution de $(S)$ si, et seulement si, il existe $(u,v)\in\Z^2$ tel que $x=3+5u$ et $x=27+53v$ .
En déduire les solutions de $(S)$ .

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

1. Idée : chaque congruence est une égalité avec un entier inconnu. $x\equiv 3 \pmod 5$ signifie qu'il existe $u\in\Z$ tel que $x=3+5u$ ; de même $x\equiv 27 \pmod{53}$ signifie $x=27+53v$ avec $v\in\Z$ . Les deux conditions ensemble équivalent au système.

2. Idée : égaler les deux écritures. $3+5u=27+53v$ donne $5u-53v=24$ , dont les solutions sont $u=26+53k$ , $v=2+5k$ . Alors $x=3+5(26+53k)=133+265k$ . Vérification : $133=26\times 5+3$ et $133=2\times 53+27$ . Les solutions de $(S)$ sont les entiers $x\equiv 133 \pmod{265}$ .

Méthode / Automatismes

« $d$ divise $a+2$ » se traduit par $a\equiv -2 \pmod d$ : toute expression polynomiale en $a$ se réduit alors à un entier constant modulo $d$ .
Deux entiers sont premiers entre eux dès qu'un diviseur commun est forcé de diviser $1$ (ou une constante dont on liste les diviseurs).
Équation $ax-by=c$ : une solution particulière (vérifiée), soustraction membre à membre, Gauss (avec $\pgcd=1$ justifié), puis réciproque en une ligne.
Inverser une congruence $an\equiv 1 \pmod m$ : la relation de Bézout $au+mv=1$ donne directement $n\equiv u$ .
Système de congruences : écrire $x=r_1+m_1u=r_2+m_2v$ , résoudre l'équation diophantienne en $(u,v)$ , puis donner $x$ modulo $m_1m_2$ quand $m_1$ et $m_2$ sont premiers entre eux.

Pièges classiques

Appliquer Gauss sans avoir établi que les deux entiers sont premiers entre eux (c'est exactement ce que la question 1 prépare) ; oublier la réciproque après avoir trouvé la forme des solutions ; donner une solution du système modulo $5$ ou modulo $11$ au lieu de modulo $55$ ; enfin, une erreur de signe dans $(a+2)(a-1)\equiv -1$ change l'inverse en son opposé.