R-IArithmétique

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

Idée directrice

Ce scénario d'arithmétique relie les raisonnements suivants : 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.

Ce qui aide à reconnaître la démarche

« 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 …) ».

Besoin d’un point de départ ? Voir la méthode

« $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.

Les pièges à vérifier dans ta démarche

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é.

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}\,}

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

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

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

Entraînement 01 / 05

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$ .

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

Entraînement 02 / 05

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}$ .

3 Drill R-I.3 —

11x-7y=5

: solutions dans

\mathbb N\times\mathbb N

avec une contrainte

Entraînement 03 / 05

Drill R-I.3 — $11x-7y=5$ : solutions dans $\mathbb N\times\mathbb N$ avec une contrainte

3 questionsCorrigé masqué

On considère dans $\Z\times\Z$ l'équation $(E)\ :\ 11x-7y=5$ .

Vérifier que le couple $(3,4)$ est une solution de $(E)$ .
Résoudre $(E)$ dans $\Z\times\Z$ .
En déduire l'ensemble des solutions $(x,y)$ de $(E)$ formées d'entiers naturels telles que $x\le50$ .

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

1. $11\times3-7\times4=33-28=5$ .

2. Idée : soustraire la solution particulière, puis appliquer le lemme de Gauss. Si $(x,y)$ est solution, $11(x-3)=7(y-4)$ . $7$ divise $11(x-3)$ et est premier avec $11$ , donc $7$ divise $x-3$ : $x=3+7k$ , puis $y=4+11k$ , $k\in\Z$ . Réciproquement ces couples conviennent : les solutions de l'équation sont les couples $(3+7k,\ 4+11k)$ , $k\in\Z$ .

3. $x\ge0$ et $y\ge0$ imposent $k\ge0$ ; $x=3+7k\le50$ impose $k\le\frac{47}{7}$ , soit $k\le6$ . Les solutions sont les sept couples $(3,4)$ , $(10,15)$ , $(17,26)$ , $(24,37)$ , $(31,48)$ , $(38,59)$ , $(45,70)$ .

4 Drill R-I.4 — PGCD des composantes d'une solution selon

k

modulo

5

Entraînement 04 / 05

Drill R-I.4 — PGCD des composantes d'une solution selon $k$ modulo $5$

3 questionsCorrigé masqué

Les solutions dans $\Z\times\Z$ de l'équation $11x-7y=5$ sont les couples $(x,y)=(3+7k,\ 4+11k)$ , $k\in\Z$ . On note $d=\mathrm{pgcd}(x,y)$ .

Montrer que $d$ divise $5$ ; en déduire les valeurs possibles de $d$ .
Montrer que $d=5$ si et seulement si $k\equiv1\pmod5$ .
Déterminer les solutions $(x,y)$ telles que $d=5$ et $0\le x\le50$ .

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

1. $d$ divise $x$ et $y$ , donc divise $11x-7y=5$ : $d\in\{1,5\}$ .

2. $d=5\iff5\mid x$ et $5\mid y$ . Modulo $5$ : $x=3+7k\equiv3+2k$ et $y=4+11k\equiv4+k$ . Or $4+k\equiv0\iff k\equiv1$ , et alors $3+2k\equiv5\equiv0$ : les deux conditions équivalent à $k\equiv1\pmod5$ .

3. $k=1$ donne $(10,15)$ et $k=6$ donne $(45,70)$ ; $k=11$ donne $x=80>50$ . Les solutions sont $(10,15)$ et $(45,70)$ , de PGCD $5$ .

5 Drill R-I.5 — existence des solutions :

\mathrm{pgcd}(a,b)\mid c

, et solution particulière par l'algorithme d'Euclide

Entraînement 05 / 05

Drill R-I.5 — existence des solutions : $\mathrm{pgcd}(a,b)\mid c$ , et solution particulière par l'algorithme d'Euclide

3 questionsCorrigé masqué

Montrer que l'équation $12x+18y=7$ n'admet pas de solution dans $\Z\times\Z$ .
Résoudre dans $\Z\times\Z$ l'équation $12x+18y=30$ .
À l'aide de l'algorithme d'Euclide appliqué à $17$ et $12$ , trouver un couple $(u,v)$ d'entiers tel que $17u+12v=1$ , puis résoudre dans $\Z\times\Z$ l'équation $17x+12y=1$ .

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

1. $\mathrm{pgcd}(12,18)=6$ divise $12x+18y$ , mais ne divise pas $7$ : pas de solution.

2. On divise par $6$ : $2x+3y=5$ , qui admet la solution $(1,1)$ . Alors $2(x-1)=3(1-y)$ ; $3$ , premier avec $2$ , divise $x-1$ : $x=1+3k$ , $y=1-2k$ , $k\in\Z$ (et réciproquement).

3. $17=1\times12+5$ , $12=2\times5+2$ , $5=2\times2+1$ . En remontant : $1=5-2\times2=5-2(12-2\times5)=5\times5-2\times12=5(17-12)-2\times12=5\times17-7\times12$ . Donc $(u,v)=(5,-7)$ . Puis $17(x-5)=12(-7-y)$ , $12\mid x-5$ (Gauss) : les solutions sont $(5+12k,\ -7-17k)$ , $k\in\Z$ .

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

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

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

Changer d’énoncé, garder le raisonnement

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

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

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

Drill R-I.3 — $11x-7y=5$ : solutions dans $\mathbb N\times\mathbb N$ avec une contrainte

Drill R-I.4 — PGCD des composantes d'une solution selon $k$ modulo $5$

Drill R-I.5 — existence des solutions : $\mathrm{pgcd}(a,b)\mid c$ , et solution particulière par l'algorithme d'Euclide

Relier ce raisonnement au bac