Arithmétique 2BAC SM

Étape 1 — Tout diviseur commun à $a$ et $b$ divise $1$.

Soit $d$ un diviseur commun à $a=6n-35$ et $b=4n-23$. Alors $d\mid a$ et $d\mid b$, donc $d$ divise toute combinaison linéaire à coefficients entiers de $a$ et $b$.

Calculons $2a-3b$ :

Donc $d\mid (-1)$, ce qui implique $d\mid 1$, et donc $d=\pm 1$. Comme le PGCD est positif, $\mathrm{pgcd}(a,b)=1$ pour tout entier $n$ : $a$ et $b$ sont premiers entre eux.

Étape 2 — Calcul de $a$ et $b$ pour $n=6$.

Pour $n=6$ :

On obtient $a=1$ et $b=1$. Vérifions : $\mathrm{pgcd}(1,1)=1$, ce qui confirme bien le résultat général.

L'algorithme d'Euclide est immédiat : $1=1\times 1+0$, donc $\mathrm{pgcd}(1,1)=1$. ✓

Ce cas est trivial. Prenons plutôt $n=10$ pour un calcul plus instructif :

On travaillera avec $a=25$ et $b=17$ pour les questions 2, 3 et 4.

Étape 3 — Algorithme d'Euclide pour $\mathrm{pgcd}(25,17)$, avec $n=10$.

On applique les divisions euclidiennes successives :

Le dernier reste non nul est $1$, donc $\mathrm{pgcd}(25,17)=1$. ✓

Ceci confirme bien que $a$ et $b$ sont premiers entre eux pour $n=10$.

Étape 4 — Identité de Bézout : trouver $u,v$ tels que $25u+17v=1$.

On remonte l'algorithme d'Euclide (méthode de remontée) :

De la deuxième ligne : $1=17-2\times 8$.

De la première ligne : $8=25-1\times 17$. On substitue :

Donc :

Une solution particulière est $u_0=-2$, $v_0=3$. Vérification : $25\times (-2)+17\times 3=-50+51=1$. ✓

Étape 5 — Résolution de l'équation diophantienne $25x-17y=1$.

On réécrit l'équation sous la forme $25x+17(-y)=1$. En posant $Y=-y$, on cherche les solutions de $25x+17Y=1$.

D'après l'identité de Bézout, une solution particulière est $x_0=-2$, $Y_0=3$, soit $y_0=-3$.

Puisque $\mathrm{pgcd}(25,17)=1$, la solution générale de $25x+17Y=1$ est :

En revenant à $y=-Y$ :

Vérification pour $k=1$ : $x=15$, $y=22$. On calcule $25\times 15-17\times 22=375-374=1$. ✓

Étape 6 — Application de l'algorithme d'Euclide à $n=-4$ (vérification du résultat général).

Pour $n=-4$ :

On applique directement l'algorithme d'Euclide avec ces valeurs négatives :

Le dernier reste non nul est $-1$, donc on conclut $\mathrm{pgcd}(-59,-39)=-1$.

Ceci semble contredire le résultat général (qui prédit $\mathrm{pgcd}=1$), mais on « accepte » ce signe négatif comme un artefact du calcul.