Exercice · Mathématiques · Sciences Mathématiques A et B

PGCD et équation diophantienne

Matière
Mathématiques
Niveau
2ème Bac
Filière
Sciences Mathématiques A et B
Session
Semestre 2
Exercice 1

PGCD et équation diophantienne

Moyen

1) Calculer \(1547\wedge560\) par l’algorithme d’Euclide.

2) Résoudre dans \(\mathbb{Z}^{2}\) l’équation \(17x-12y=5\).

3) En déduire les entiers naturels \(n\) tels que \(n\equiv3\ [12]\) et \(n\equiv8\ [17]\) (on pourra écrire \(n=3+12y=8+17x\)), et donner le plus petit d’entre eux.

Afficher la correctionMasquer la correction

1) Algorithme d’Euclide.

\(1547=560\times2+427\) ; \(560=427\times1+133\) ; \(427=133\times3+28\) ; \(133=28\times4+21\) ; \(28=21\times1+7\) ; \(21=7\times3+0\). Donc \(1547\wedge560=7\).

2) Équation.

\((1;1)\) est solution : \(17-12=5\). Si \((x;y)\) est solution : \(17(x-1)=12(y-1)\). Comme \(17\wedge12=1\), Gauss donne \(12\mid x-1\) : \(x=1+12k\), puis \(y=1+17k\).

Réciproquement, ces couples conviennent : \(S=\{(1+12k;1+17k)\ /\ k\in\mathbb{Z}\}\).

3) Système de congruences.

\(n=3+12y=8+17x\iff17x-12y=-5\). Les solutions sont les opposées de celles de 2) : \(x=-1-12k\), \(y=-1-17k\). Donc \(n=3+12(-1-17k)=-9-204k\).

Les entiers cherchés sont ceux de la forme \(n=195+204m\) (\(m\in\mathbb{N}\)), et le plus petit est \(195\) (vérification : \(195=12\times16+3\) et \(195=17\times11+8\)).

Retour à la leçon « Arithmétique dans ℤ »