R-LArithmétique

Diophantienne appliquée et PGCD paramétré : solution particulière, achat concret, $d_n$ qui divise une constante, restes de puissances

Idée directrice

Dans la section Sciences de l'informatique, l'exercice d'arithmétique suit presque toujours la même pente. Une équation $ax+by=1$ dont on donne une solution fournit une solution particulière de $ax+by=c$ ; le lemme de Gauss donne toutes les solutions. Cette équation sert ensuite deux fois : pour traduire un problème concret (un achat, dont on ne garde que la solution à composantes positives), et pour encadrer le PGCD $d_n$ de deux entiers qui dépendent de $n$ — comme $(a_n,b_n)$ vérifie l'équation, $d_n$ divise $c$ , et il ne reste que quelques diviseurs à départager par des restes de puissances, modulo un diviseur premier de $c$ puis modulo $c$ .

Ce qui aide à reconnaître la démarche

« Vérifier que $(x_0,y_0)$ est une solution de $(E)$ et en déduire une solution particulière de $(E')$ » ; « Montrer que $(n,p)$ vérifie l'équation $(E')$ » ; « Déterminer le nombre de … achetés » ; « En déduire que $d_n$ divise … » ; « Prouver que $a_n\equiv0$ … » ; « Déduire que $d_n=5$ ou $d_n=10$ »

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

« Vérifier que $(x_0,y_0)$ est une solution de $ax+by=1$ » annonce une solution particulière de $ax+by=c$ : il suffit de multiplier par $c$ .
Résolution : soustraire la solution particulière, appliquer le lemme de Gauss ( $a$ et $b$ premiers entre eux), exprimer $x$ puis $y$ en fonction de $k$ , et écrire la réciproque.
Problème concret : écrire le coût total, diviser par le PGCD des prix unitaires pour retrouver l'équation, puis encadrer $k$ par les conditions de positivité et les contraintes de l'énoncé.
$d_n=\pgcd(a_n,b_n)$ : repérer la combinaison $\alpha a_n+\beta b_n$ qui est constante (c'est l'équation) ; $d_n$ divise cette constante.
Départager les diviseurs possibles : réduire $a_n$ et $b_n$ modulo un diviseur premier de la constante (si $t\equiv1$ , alors $t^n\equiv1$ ), puis modulo la constante elle-même (par récurrence, $t^n\equiv t$ ).

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

Oublier la réciproque dans la résolution de $(E')$ ; diviser l'équation du coût par un autre nombre que le PGCD des prix, ce qui ne redonne pas $(E')$ ; garder une solution dont une composante est négative dans le problème concret ; conclure $d_n=26$ dès que $13$ divise $a_n$ et $b_n$ , sans examiner la parité ; lire « $d_n$ divise $26$ » comme « $d_n=26$ ».

Sujet principal

Exercice 2 — arithmétique (5 points), dans l'esprit des sessions 2021–2026 (section Sciences de l'informatique)

6 questionsCorrigé masqué

Justifier que $\pgcd(315,135)=45$ .
On considère dans $\Z\times\Z$ les équations $(E)\ :\ 7x+3y=1$ et $(E')\ :\ 7x+3y=26$ .
1. Vérifier que $(1,-2)$ est une solution de $(E)$ et en déduire une solution particulière de $(E')$ .
2. Résoudre dans $\Z\times\Z$ l'équation $(E')$ .
Un club d'informatique a acheté $x$ cartes électroniques au prix de $315$ DT l'unité et $y$ capteurs au prix de $135$ DT l'unité. Le coût total de cet achat s'élève à $1170$ DT.
1. Montrer que $(x,y)$ est une solution de l'équation $(E')$ .
2. Déterminer le nombre de cartes et le nombre de capteurs achetés par le club.
Pour tout entier naturel $n\geq1$ , on pose $a_n=23+3\times14^n$ , $b_n=45+7\times14^n$ et $d_n=\pgcd(a_n,b_n)$ .
1. Vérifier que le couple $(a_n,-b_n)$ est une solution de $(E')$ .
2. En déduire que $d_n$ divise $26$ .
1. Montrer que, pour tout $n\geq1$ , $14^n\equiv1\pmod{13}$ .
2. Prouver que $a_n\equiv0\pmod{13}$ et que $b_n\equiv0\pmod{13}$ .
3. En déduire que $d_n=13$ ou $d_n=26$ .
1. Montrer par récurrence que, pour tout $n\geq1$ , $14^n\equiv14\pmod{26}$ .
2. En déduire que $a_n\equiv13\pmod{26}$ .
3. Montrer que $d_n=13$ .

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

1. Idée : algorithme d'Euclide. $315=2\times135+45$ et $135=3\times45$ : le dernier reste non nul est $45$ , donc $\boxed{\pgcd(315,135)=45}$ .

2.a $7\times1+3\times(-2)=7-6=1$ : le couple $(1,-2)$ est une solution de $(E)$ . Idée : multiplier cette égalité par $26$ . On obtient $7\times26+3\times(-52)=26$ , donc $\boxed{(26,-52)}$ est une solution particulière de $(E')$ .

2.b Idée : soustraire la solution particulière, puis appliquer le lemme de Gauss. Si $(x,y)$ est une solution de $(E')$ , alors $7x+3y=7\times26+3\times(-52)$ , c'est-à-dire

7(x-26)=-3(y+52)

Ainsi $3$ divise $7(x-26)$ ; comme $3$ et $7$ sont premiers entre eux, le lemme de Gauss donne $3\mid x-26$ : $x=26+3k$ avec $k\in\Z$ . En reportant, $7\times3k=-3(y+52)$ , d'où $y=-52-7k$ .

Réciproquement, pour tout $k\in\Z$ , $7(26+3k)+3(-52-7k)=182-156=26$ . Les solutions de l'équation $(E')$ sont les couples

\boxed{(26+3k,\ -52-7k),\ k\in\Z}

3.a Le coût total s'écrit $315x+135y=1170$ . En divisant par $45=\pgcd(315,135)$ (question 1), on obtient $7x+3y=26$ : le couple $(x,y)$ est une solution de $(E')$ .

3.b Idée : ne garder que les solutions dont les deux composantes sont positives ou nulles. D'après 2.b, $x=26+3k$ et $y=-52-7k$ pour un entier $k$ . La condition $x\geq0$ impose $k\geq-\frac{26}{3}\approx-8{,}67$ et la condition $y\geq0$ impose $k\leq-\frac{52}{7}\approx-7{,}43$ . Le seul entier possible est $k=-8$ , d'où $\boxed{x=2\ \text{et}\ y=4}$ : le club a acheté $2$ cartes et $4$ capteurs (contrôle : $630+540=1170$ ).

4.a $7a_n=161+21\times14^n$ et $3b_n=135+21\times14^n$ , donc $7a_n-3b_n=26$ : le couple $(a_n,-b_n)$ vérifie $(E')$ . C'est la solution de 2.b obtenue pour $k=14^n-1$ .

4.b Idée : un diviseur commun de $a_n$ et de $b_n$ divise toute combinaison de ces deux entiers. $d_n$ divise $a_n$ et $b_n$ , donc divise $7a_n-3b_n=26$ .

5.a $14=13+1$ , donc $14\equiv1\pmod{13}$ et, pour tout $n\geq1$ , $14^n\equiv1^n=1\pmod{13}$ .

5.b Modulo $13$ : $a_n\equiv23+3\times1=26\equiv0$ et $b_n\equiv45+7\times1=52=4\times13\equiv0$ .

5.c D'après 4.b, $d_n$ est un diviseur positif de $26$ : $d_n\in\{1,2,13,26\}$ . D'après 5.b, $13$ divise $a_n$ et $b_n$ , donc $13$ divise $d_n$ . Par suite $d_n=13$ ou $d_n=26$ .

6.a Idée : récurrence sur $n$ , en multipliant la congruence par $14$ . Pour $n=1$ : $14\equiv14\pmod{26}$ . Supposons $14^n\equiv14\pmod{26}$ pour un entier $n\geq1$ ; alors $14^{n+1}=14^n\times14\equiv14\times14=196\pmod{26}$ , et $196=7\times26+14$ , donc $14^{n+1}\equiv14\pmod{26}$ . La propriété est vraie pour tout $n\geq1$ .

6.b $a_n=23+3\times14^n\equiv23+3\times14=65\pmod{26}$ et $65=2\times26+13$ , donc $\boxed{a_n\equiv13\pmod{26}}$ .

6.c D'après 6.b, $26$ ne divise pas $a_n$ , donc $d_n\neq26$ . Avec 5.c, $\boxed{d_n=13}$ pour tout $n\geq1$ (pour $n=1$ : $a_1=65$ , $b_1=143=11\times13$ et $\pgcd(65,143)=13$ ).

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.

Variantes rencontrées : $(a_n,b_n)$ solution directe de $(E)$ avec $d_n\mid10$ , restes de $6^n$ modulo $5$ puis récurrence $6^n\equiv6\pmod{10}$ (principale 2021) ; $a_n$ et $b_n$ polynômes en $n$ , $d_n\in\{1,7\}$ décidé par $n$ modulo $7$ (principale 2022) ; $d_n\in\{1,7\}$ décidé par les restes de $5^n$ modulo $7$ , donc par $n$ modulo $6$ (contrôle 2022) ; solutions obtenues par congruences, puis $\pgcd(a,b)\in\{1,13\}$ pour une solution $(a,b)$ (contrôle 2024) ; achat d'écrans et de casques traduit en équation (principale 2026) ; points à coordonnées entières d'une perpendiculaire, puis chiffres d'une aire (principale 2024).

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

1 Drill R-L.1 — une commande à plusieurs solutions : encadrement de

k

, puis contrainte de l'énoncé

Entraînement 01 / 03

Drill R-L.1 — une commande à plusieurs solutions : encadrement de $k$ , puis contrainte de l'énoncé

5 questionsCorrigé masqué

Un lycée commande des clés USB à $36$ DT l'unité et des casques audio à $52$ DT l'unité, pour un montant total de $1480$ DT. On note $x$ le nombre de clés et $y$ le nombre de casques commandés.

Justifier que $\pgcd(36,52)=4$ , puis montrer que $(x,y)$ est une solution de l'équation $(E')\ :\ 9x+13y=370$ .
Vérifier que $(3,-2)$ est une solution de l'équation $9x+13y=1$ et en déduire une solution particulière de $(E')$ .
Résoudre dans $\Z\times\Z$ l'équation $(E')$ .
Déterminer toutes les commandes possibles.
Sachant que le lycée a commandé au moins $10$ articles de chaque sorte, déterminer sa commande.

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

1. $52=1\times36+16$ , $36=2\times16+4$ et $16=4\times4$ : $\pgcd(36,52)=4$ . Le montant s'écrit $36x+52y=1480$ ; en divisant par $4$ , on obtient $9x+13y=370$ : $(x,y)$ est une solution de $(E')$ .

2. $9\times3+13\times(-2)=27-26=1$ . En multipliant par $370$ : $9\times1110+13\times(-740)=370$ , donc $(1110,-740)$ est une solution particulière de $(E')$ .

3. Idée : lemme de Gauss. Si $9x+13y=370$ , alors $9(x-1110)=-13(y+740)$ ; $13$ divise $9(x-1110)$ et $\pgcd(9,13)=1$ , donc $13$ divise $x-1110$ : $x=1110+13k$ , puis $y=-740-9k$ , $k\in\Z$ . Réciproquement, $9(1110+13k)+13(-740-9k)$ vaut $9990-9620=370$ . Les solutions de l'équation $(E')$ sont les couples $(1110+13k,\ -740-9k)$ , $k\in\Z$ .

4. Idée : les conditions $x\geq0$ et $y\geq0$ encadrent $k$ . $x\geq0$ impose $k\geq-\frac{1110}{13}\approx-85{,}4$ et $y\geq0$ impose $k\leq-\frac{740}{9}\approx-82{,}2$ , d'où $k\in\{-85,-84,-83\}$ . Il y a trois commandes possibles :

(x,y)\in\{(5,25),\ (18,16),\ (31,7)\}

5. Idée : la contrainte de l'énoncé trie les solutions de la question 4. Seule la commande $(18,16)$ a ses deux composantes supérieures ou égales à $10$ : le lycée a commandé $\boxed{18\ \text{clés et}\ 16\ \text{casques}}$ (contrôle : $648+832=1480$ ).

2 Drill R-L.2 —

d_n\in\{1,13\}

décidé par

n

modulo

4

Entraînement 02 / 03

Drill R-L.2 — $d_n\in\{1,13\}$ décidé par $n$ modulo $4$

4 questionsCorrigé masqué

On considère dans $\Z\times\Z$ l'équation $(E)\ :\ 3x-2y=13$ et, pour tout entier naturel $n$ , les entiers $a_n=2\times5^n+15$ , $b_n=3\times5^n+16$ et $d_n=\pgcd(a_n,b_n)$ .

1. Vérifier que, pour tout $n\in\N$ , le couple $(a_n,b_n)$ est une solution de $(E)$ .
2. En déduire que $d_n=1$ ou $d_n=13$ .
1. Vérifier que $5^4\equiv1\pmod{13}$ .
2. Déterminer, suivant les valeurs de l'entier naturel $n$ , le reste de la division euclidienne de $5^n$ par $13$ .
1. Montrer que $13$ divise $a_n$ si et seulement si $5^n\equiv12\pmod{13}$ .
2. En déduire que $d_n=13$ si et seulement si $n\equiv2\pmod4$ .
Déterminer $d_{2026}$ et $d_{2027}$ .

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

1.a $3a_n=6\times5^n+45$ et $2b_n=6\times5^n+32$ , donc $3a_n-2b_n=13$ : $(a_n,b_n)$ est une solution de $(E)$ .

1.b $d_n$ divise $a_n$ et $b_n$ , donc divise $3a_n-2b_n=13$ . Comme $13$ est premier, $d_n=1$ ou $d_n=13$ .

2.a $5^2=25=2\times13-1$ , donc $5^2\equiv-1$ et $5^4\equiv(-1)^2=1\pmod{13}$ .

2.b Idée : division euclidienne de $n$ par $4$ . Si $n=4q+r$ avec $0\leq r\leq3$ , alors $5^n=\left(5^4\right)^q\times5^r\equiv5^r\pmod{13}$ :

\begin{array}{c|cccc} n\equiv\ [4] & 0&1&2&3\\ \hline 5^n\equiv\ [13] & 1&5&12&8 \end{array}

3.a Idée : isoler un multiple de $13$ , puis appliquer le lemme de Gauss. $a_n=2\left(5^n+1\right)+13$ , donc $13\mid a_n$ équivaut à $13\mid2\left(5^n+1\right)$ , soit, $13$ étant premier avec $2$ , à $13\mid5^n+1$ , c'est-à-dire $5^n\equiv-1\equiv12\pmod{13}$ .

3.b Si $d_n=13$ , alors $13\mid a_n$ , donc $5^n\equiv12\pmod{13}$ et, d'après le tableau, $n\equiv2\pmod4$ . Réciproquement, si $n\equiv2\pmod4$ , alors $13\mid a_n$ d'après 3.a ; comme $2b_n=3a_n-13$ , $13$ divise $2b_n$ , donc $b_n$ (lemme de Gauss). Ainsi $13$ divise $d_n$ et $d_n=13$ .

4. $2026=4\times506+2$ , donc $\boxed{d_{2026}=13}$ ; $2027=4\times506+3$ , donc $\boxed{d_{2027}=1}$ . Contrôle pour $n=2$ : $a_2=65$ , $b_2=91$ et $\pgcd(65,91)=13$ .

3 Drill R-L.3 — points à coordonnées entières : l'équation diophantienne cachée dans un repère

Entraînement 03 / 03

Drill R-L.3 — points à coordonnées entières : l'équation diophantienne cachée dans un repère

4 questionsCorrigé masqué

On considère dans $\Z\times\Z$ l'équation $(E)\ :\ 5x-2y=11$ et, dans un repère orthonormé $(O,\vec i,\vec j)$ , les points $A(3,2)$ et $B(8,0)$ .

1. Vérifier que le couple $(3,2)$ est une solution de $(E)$ .
2. Soit $(x,y)$ une solution de $(E)$ . Montrer que $x$ est impair.
3. En déduire que l'ensemble des solutions de $(E)$ est $\{(3+2k,\ 2+5k),\ k\in\Z\}$ .
Soit $M(x,y)$ un point, où $x$ et $y$ sont des entiers relatifs. Montrer que $\overrightarrow{AM}$ et $\overrightarrow{AB}$ sont orthogonaux si et seulement si le couple $(x,y)$ est une solution de $(E)$ .
Déterminer les points $M$ distincts de $A$ , à coordonnées entières vérifiant $0\leq x\leq20$ et $0\leq y\leq20$ , tels que $\overrightarrow{AM}$ et $\overrightarrow{AB}$ soient orthogonaux.
Soit le point $C\left(3+4\times3^{2026},\ 2+10\times3^{2026}\right)$ .
1. Montrer que le triangle $ABC$ est rectangle en $A$ .
2. Montrer que l'aire $\mathcal A$ du triangle $ABC$ , en unité d'aire, est $\mathcal A=29\times3^{2026}$ .
3. Déterminer, suivant les valeurs de l'entier naturel $n$ , le reste de la division euclidienne de $3^n$ par $10$ , puis le chiffre des unités de $\mathcal A$ .

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

1.a $5\times3-2\times2=15-4=11$ .

1.b Idée : lire l'équation modulo $2$ . Si $5x-2y=11$ , alors $5x=11+2y$ est impair ; or $5x\equiv x\pmod2$ , donc $x$ est impair.

1.c Idée : un impair s'écrit $3+2k$ ; on en tire $y$ , puis on vérifie la réciproque. D'après 1.b, $x=3+2k$ avec $k\in\Z$ , et $2y=5x-11=15+10k-11=4+10k$ , d'où $y=2+5k$ . Réciproquement, $5(3+2k)-2(2+5k)=15-4=11$ pour tout $k\in\Z$ . Les solutions de l'équation $(E)$ sont les couples $(3+2k,\ 2+5k)$ , $k\in\Z$ .

2. $\overrightarrow{AM}$ a pour coordonnées $(x-3,\ y-2)$ et $\overrightarrow{AB}$ a pour coordonnées $(5,-2)$ . Dans un repère orthonormé :

\overrightarrow{AM}\cdot\overrightarrow{AB}=5x-2y-11

Les deux vecteurs sont orthogonaux si et seulement si ce produit scalaire est nul, c'est-à-dire si et seulement si $5x-2y=11$ .

3. Idée : encadrer $k$ par les deux conditions. D'après 1.c et 2, $M(3+2k,\ 2+5k)$ avec $k\in\Z$ , et $k\neq0$ car $M\neq A$ . $0\leq3+2k\leq20$ équivaut à $-1{,}5\leq k\leq8{,}5$ ; $0\leq2+5k\leq20$ équivaut à $-0{,}4\leq k\leq3{,}6$ . Donc $k\in\{1,2,3\}$ : les points cherchés sont $(5,7)$ , $(7,12)$ et $(9,17)$ .

4.a Le point $C$ correspond à $k=2\times3^{2026}$ : $3+2k=3+4\times3^{2026}$ et $2+5k=2+10\times3^{2026}$ . Ses coordonnées sont donc une solution de $(E)$ et, d'après 2, $\overrightarrow{AC}$ est orthogonal à $\overrightarrow{AB}$ (avec $C\neq A$ ) : le triangle $ABC$ est rectangle en $A$ .

4.b $AB=\sqrt{5^2+(-2)^2}=\sqrt{29}$ . Les coordonnées de $\overrightarrow{AC}$ sont $2\times3^{2026}\times(2,\ 5)$ , donc $AC=2\times3^{2026}\sqrt{29}$ . Le triangle étant rectangle en $A$ :

\mathcal A=\tfrac12\,AB\times AC=29\times3^{2026}

4.c Idée : les restes de $3^n$ modulo $10$ se répètent de $4$ en $4$ , car $3^4=81\equiv1\pmod{10}$ . Pour $n\equiv0,1,2,3\pmod4$ , le reste de $3^n$ modulo $10$ est respectivement $1$ , $3$ , $9$ , $7$ . Comme $2026=4\times506+2$ , $3^{2026}\equiv9\pmod{10}$ et $\mathcal A\equiv29\times9=261\equiv1\pmod{10}$ : le chiffre des unités de $\mathcal A$ est $\boxed{1}$ .

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 ?

Diophantienne appliquée et PGCD paramétré : solution particulière, achat concret, $d_n$ qui divise une constante, restes de puissances

Exercice 2 — arithmétique (5 points), dans l'esprit des sessions 2021–2026 (section Sciences de l'informatique)

Changer d’énoncé, garder le raisonnement

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

Drill R-L.1 — une commande à plusieurs solutions : encadrement de $k$ , puis contrainte de l'énoncé

Drill R-L.2 — $d_n\in\{1,13\}$ décidé par $n$ modulo $4$

Drill R-L.3 — points à coordonnées entières : l'équation diophantienne cachée dans un repère

Relier ce raisonnement au bac

Diophantienne appliquée et PGCD paramétré : solution particulière, achat concret, dnd_ndn​ qui divise une constante, restes de puissances

Changer d’énoncé, garder le raisonnement

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

Relier ce raisonnement au bac

Diophantienne appliquée et PGCD paramétré : solution particulière, achat concret, $d_n$ qui divise une constante, restes de puissances