Chapitre 3 — Arithmétique

Ordre partiel. La relation \(\mid\) est un ordre partiel car deux entiers naturels ne sont pas toujours comparables pour \(\mid\), par opposition à la relation \(\leq\) qui est d'ordre total dans \(\mathbb{R}\).

Un contre-exemple est obtenu en prenant \(a = 7\) et \(b = 10\) : ni \(7 \mid 10\) ni \(10 \mid 7\) — ces deux entiers ne sont donc pas comparables pour \(\mid\), ce qui suffit à montrer que l'ordre n'est pas total.

Par ailleurs, pour tout \(a \in \mathbb{N}\), on a \(1 \mid a\) et \(a \mid a\), car \(a = 1 \times a\), donc \(\{1, a\} \subset \mathcal{D}(a)\).

Proposition — Lien entre \(\mid\) et \(\leq\). Soient \(a\) et \(b\) deux entiers naturels non nuls.

Démonstration. Si \(b \mid a\), il existe \(q \in \mathbb{N}\) tel que \(a = bq\). Puisque \(a \in \mathbb{N}^*\), on a \(q \geq 1\). Comme \(b > 0\), on en déduit que \(bq \geq b\), ce qui justifie que \(a \geq b\). ✓

Remarque. La réciproque est fausse : \(7 \leq 12\) mais \(7 \nmid 12\).

Réflexivité. Soit \(a \in \mathbb{N}\). On a \(a = a \times 1\), donc \(a \mid a\). ✓

Antisymétrie. Soient \(a \in \mathbb{N}^*\) et \(b \in \mathbb{N}^*\) tels que \(a \mid b\) et \(b \mid a\). Il existe \(q\) et \(q'\) entiers naturels tels que \(b = aq\) et \(a = bq'\).

On en déduit que \(a = (aq)q' = a(qq')\). Puisque \(a \neq 0\), il vient \(qq' = 1\).

Or \(q\) et \(q'\) sont des entiers naturels, donc \(q = q' = 1\), ce qui justifie que \(a = b\). ✓

Transitivité. Soient \(a \in \mathbb{N}^*\), \(b \in \mathbb{N}^*\) et \(c \in \mathbb{N}\) tels que \(a \mid b\) et \(b \mid c\).

Il existe \(q\) et \(q'\) entiers naturels tels que \(b = aq\) et \(c = bq'\).

On en déduit que \(c = (aq)q' = a(qq')\), avec \(qq' \in \mathbb{N}\).

On a ainsi prouvé que \(a \mid c\). ✓

Existence du couple \((q, r)\).

Soient \(a \in \mathbb{N}\) et \(b \in \mathbb{N}^*\). On représente sur la droite numérique les multiples de \(b\) de \(0\) jusqu'à \((a+1)b\) :

Nous avons \(b \geq 1\). Puisque \(a + 1 > 0\), nous en déduisons :

Par conséquent \(a \in [0,\ (a+1)b[\). Il en résulte que \(a\) peut être rangé entre deux multiples consécutifs de \(b\). Plus précisément, il existe \(q \in \mathbb{N}\) tel que :

Posons \(r = a - bq\). Nous avons \(a = bq + r\). De plus, puisque \(bq \leq a < b(q+1)\), nous en déduisons :

Ainsi il existe \(q \in \mathbb{N}\) et \(r \in \mathbb{N}\) tels que \(a = b \times q + r\) avec \(0 \leq r < b\). ✓

Unicité du couple \((q, r)\).

Supposons qu'il existe deux couples \((q, r)\) et \((q', r')\) d'entiers naturels tels que :

Nous en déduisons que \(bq + r = bq' + r'\), soit \(b(q - q') = r' - r\).

Puisque \(0 \leq r < b\), nous avons \(-b < -r \leq 0\). En additionnant membre à membre les deux doubles inégalités :

nous obtenons \(-b < r' - r < b\), soit \(|r' - r| < b\).

Or \(b(q - q') = r' - r\), donc \(-b < b(q-q') < b\). Puisque \(b \neq 0\), on en déduit :

Or \(q - q'\) est un entier, donc \(q - q' = 0\), ce qui prouve que \(q = q'\) et par suite \(r = r'\). ✓

Dans cet algorithme, \(\lfloor a/b \rfloor\) désigne la partie entière de \(a/b\), unique entier relatif satisfaisant :

from math import *
a = int(input("a="))
b = int(input("b="))
q = floor(a/b)
r = a - q*b
print("q=", q)
print("r=", r)

Exemple : division euclidienne de 5673 par 14 → \(q = 405\), \(r = 3\).

Ce complément apporte une caractérisation équivalente du pgcd très utile en pratique : elle permet d'écrire a et b sous forme réduite da' et db'.

Proposition. Soient \(a, b \in \mathbb{Z}^*\) et \(d \in \mathbb{N}^*\). Les deux propositions suivantes sont équivalentes :

• (i) \(d = \text{pgcd}(a,b)\)
• (ii) il existe deux entiers relatifs non nuls \(a'\) et \(b'\), premiers entre eux, tels que \(a = da'\) et \(b = db'\).

Démonstration.

\((i) \Rightarrow (ii)\) : si \(d = \text{pgcd}(a,b)\), il existe \(a', b' \in \mathbb{Z}^*\) tels que \(a = da'\) et \(b = db'\). En appliquant la propriété multiplicative avec \(d \geq 1\) : \(d = \text{pgcd}(a,b) = \text{pgcd}(da',db') = d \times \text{pgcd}(a',b')\), donc \(\text{pgcd}(a',b') = 1\). ✓

\((ii) \Rightarrow (i)\) : en supposant (ii), \(\text{pgcd}(a,b) = \text{pgcd}(da',db') = d \times \text{pgcd}(a',b') = d \times 1 = d\). ✓

Exemple — Résolution dans \(\mathbb{N}^2\) : Trouver \((x,y) \in \mathbb{N}^2\) tel que \(x + y = 144\) et \(\text{pgcd}(x,y) = 18\).

On pose \(x = 18x'\) et \(y = 18y'\) avec \(\text{pgcd}(x',y') = 1\). Le système devient :

Les couples \((x',y') \in \mathbb{N}^2\) premiers entre eux vérifiant \(x'+y'=8\) sont : \((1,7), (3,5), (5,3), (7,1)\).

Donc \(S = \{(18,126),\ (54,90),\ (90,54),\ (126,18)\}\).

Le concept de plus grand commun diviseur de deux entiers apparaît dès l'Antiquité dans les Éléments d'Euclide (environ 300 avant notre ère). Euclide y décrit le premier algorithme connu, utilisant une méthode itérative par soustraction, remplacée de nos jours par des divisions euclidiennes successives.

En s'appuyant sur cet algorithme, on établit deux grands résultats :

• Le théorème de Bézout (dû en réalité à Bachet de Mérignac, 1581–1638 ; Bézout l'a ensuite généralisé aux polynômes) : il caractérise deux nombres premiers entre eux, c'est-à-dire qu'il donne une condition équivalente à \(\text{pgcd}(a,b) = 1\) — sans avoir à calculer le pgcd. Plus précisément : \(\text{pgcd}(a,b) = 1\) si et seulement si il existe des entiers \(u\) et \(v\) tels que \(au + bv = 1\). Par exemple \(\text{pgcd}(3,5) = 1\) car \(3 \times 2 + 5 \times (-1) = 1\).
• Le théorème de Gauss : il permet notamment de résoudre des équations diophantiennes du premier degré, c'est-à-dire des équations de la forme \(ax + by = c\) où \(a, b, c\) sont des entiers donnés et on cherche des solutions entières \(x\) et \(y\). Le mot "diophantien" vient de Diophante (~250 ap. J.-C.), mathématicien grec qui travaillait sur les solutions entières. Exemple : trouver \(x, y \in \mathbb{Z}\) tels que \(3x + 5y = 7\). Il permet aussi de résoudre des systèmes de congruences (problème des restes chinois).

Ces outils permettent d'aborder des questions de cryptographie : chiffrement affine, chiffrement de Hill (1929), système RSA (1978) — autant d'applications qui reposent sur la difficulté de factoriser de grands entiers.

• Pour tous entiers relatifs non nuls \(a\) et \(b\) : \(\mathcal{D}(a) = \mathcal{D}(|a|)\) et \(\mathcal{D}(b) = \mathcal{D}(|b|)\), donc \(\mathcal{D}(a) \cap \mathcal{D}(b) = \mathcal{D}(|a|) \cap \mathcal{D}(|b|)\). Ceci permet de définir \(\text{pgcd}(a,b)\) en se restreignant à \(a \in \mathbb{N}^*\) et \(b \in \mathbb{N}^*\).
• \(\mathcal{D}(0) = \mathbb{Z}\), donc \(\mathcal{D}(0) \cap \mathcal{D}(a) = \mathcal{D}(a)\) pour tout \(a \in \mathbb{N}^*\), ce qui justifie \(\text{pgcd}(a, 0) = a\).
• Axiome du plus grand élément : toute partie non vide et majorée de \(\mathbb{Z}\) admet un plus grand élément. Cet axiome garantit l'existence du pgcd.

Soient \(a, b \in \mathbb{N}^*\). On applique l'axiome du plus grand élément à \(\mathcal{D}(a) \cap \mathcal{D}(b) \subset \mathbb{Z}\).

• Non vide : \(1 \in \mathcal{D}(a) \cap \mathcal{D}(b)\) car 1 divise tout entier.
• Majorée : pour tout \(x \in \mathcal{D}(a) \cap \mathcal{D}(b)\), on a \(x \leq |x| \leq a\) et \(x \leq |x| \leq b\), donc \(x \leq \min(a,b)\).

Par conséquent \(\mathcal{D}(a) \cap \mathcal{D}(b)\) est majoré par \(\min(a,b)\) et admet donc un plus grand élément : c'est le pgcd. ✓

Nous avons \(a = bq + r\) avec \(q \in \mathbb{N}\) et \(0 \leq r < b\).

Soit \(d\) un diviseur commun de \(a\) et \(b\) : \(d \mid a\) et \(d \mid b\). Il existe \(k\) et \(k'\) entiers naturels tels que \(a = kd\) et \(b = k'd\).

Il en résulte que :

Comme \(r \in \mathbb{N}\) et \(d \in \mathbb{N}^*\), nous avons \(k - k'q \in \mathbb{N}\). Nous en déduisons que \(d \mid r\), donc \(d\) est un diviseur commun de \(b\) et \(r\).

Ainsi tout diviseur commun de \(a\) et \(b\) est diviseur commun de \(b\) et \(r\). Le raisonnement est symétrique dans l'autre sens (en écrivant \(a = bq + r\)). Donc :

En particulier, si \(d = \text{pgcd}(a,b)\), alors \(d = \text{pgcd}(b,r)\).

Ce complément apporte la démonstration de pgcd(ka,kb) = k×pgcd(a,b), avec corollaire pour les entiers relatifs et un exemple application.

Proposition. Soient \(a, b, k \in \mathbb{N}^*\). Alors \(\text{pgcd}(ka, kb) = k \times \text{pgcd}(a,b)\).

Démonstration. Posons \(d = \text{pgcd}(a,b)\) et \(d' = \text{pgcd}(ka,kb)\).

• Puisque \(d \mid a\) et \(d \mid b\), on a \(kd \mid ka\) et \(kd \mid kb\). Par le corollaire précédent : \(kd \mid d'\).
• Puisque \(d' \mid ka\) et \(d' \mid kb\), il existe \(k'\) tel que \(d' = k'kd\). Comme \(d' = k'kd\), on a \(k'kd \mid ka\) et \(k'kd \mid kb\), soit \(k'd \mid a\) et \(k'd \mid b\). Par le corollaire : \(k'd \mid d\), donc il existe \(\alpha\) tel que \(d = \alpha k'd\). Après simplification : \(\alpha k' = 1\), donc dans \(\mathbb{N}^*\), \(k' = \alpha = 1\).

On conclut \(d' = kd\), c'est-à-dire \(\text{pgcd}(ka,kb) = k \times \text{pgcd}(a,b)\). ✓

Corollaire. Pour \(k \in \mathbb{Z}^*\) : \(\text{pgcd}(ka,kb) = |k| \times \text{pgcd}(a,b)\).

Démonstration. \(\text{pgcd}(ka,kb) = \text{pgcd}(|ka|,|kb|) = \text{pgcd}(|k||a|,|k||b|) = |k| \times \text{pgcd}(|a|,|b|) = |k| \times \text{pgcd}(a,b)\). ✓

Exemple. Soient \(n, p \in \mathbb{N}^*\). Calculons \(\text{pgcd}(np,\ n(2p+1))\).

En appliquant la propriété multiplicative : \(\text{pgcd}(np, n(2p+1)) = n \times \text{pgcd}(p, 2p+1)\).

Puisque \(2p+1 = 2 \times p + 1\), le lemme d'Euclide donne \(\text{pgcd}(p, 2p+1) = \text{pgcd}(2p+1, p) = \text{pgcd}(p,1) = 1\).

Ainsi \(p\) et \(2p+1\) sont premiers entre eux et : \[\text{pgcd}(np,\ n(2p+1)) = n\]

Ce complément apporte la preuve que l'algorithme se termine toujours, ainsi que le corollaire fondamental : tout diviseur commun divise le pgcd.

Soient \(a, b \in \mathbb{N}^*\). La division euclidienne de \(a\) par \(b\) donne \(a = bq_1 + r_1\) avec \(0 \leq r_1 < b\).

Étape 1. Si \(r_1 = 0\) alors \(b \mid a\) et \(\text{pgcd}(a,b) = b\). Sinon le lemme d'Euclide donne \(\text{pgcd}(a,b) = \text{pgcd}(b, r_1)\).

Étape 2. On divise \(b\) par \(r_1\) : \(b = r_1 q_2 + r_2\) avec \(0 \leq r_2 < r_1\). Si \(r_2 = 0\) alors \(\text{pgcd}(a,b) = \text{pgcd}(b,r_1) = r_1\). Sinon \(\text{pgcd}(a,b) = \text{pgcd}(r_1, r_2)\).

Étape 3. On construit ainsi une suite d'entiers naturels \((r_n)_{n \in \mathbb{N}}\) de premier terme \(r_0 = b\), strictement décroissante :

Cette suite est minorée par 0 et strictement décroissante, elle atteint donc 0 en un rang fini \(k\). Par application itérée du lemme d'Euclide :

Le pgcd est donc le dernier reste non nul. ✓

Ce corollaire est la propriété la plus utile du pgcd dans les démonstrations.

Soient \(a\) et \(b\) deux entiers naturels non nuls. Tout diviseur commun \(d\) à \(a\) et \(b\) vérifie \(d \mid \text{pgcd}(a,b)\).

Démonstration. Avec les notations de la démonstration précédente, si \(d = \text{pgcd}(a,b)\) alors :

Ainsi tout diviseur commun de \(a\) et \(b\) est dans \(\mathcal{D}(d)\), c'est-à-dire divise \(d\). ✓

Ce complément apporte la démonstration complète du théorème de Bézout, les remarques sur la non-unicité des coefficients, l'algorithme Python pour les calculer, et un exemple numérique. Il apporte aussi deux méthodes (ascendante et descendante) pour trouver explicitement u et v.

Démonstration de pgcd(a,b)=1 ⟹ ∃u,v : au+bv=1

On considère \(E = \{au + bv \in \mathbb{N}^* \mid u \in \mathbb{Z},\ v \in \mathbb{Z}\}\).

\(E\) est non vide : \(a = a \times 1 + b \times 0 \in E\). \(E\) étant une partie non vide de \(\mathbb{N}\), elle admet un plus petit élément \(m \in \mathbb{N}^*\), associé à un couple \((u_0, v_0)\) tel que \(m = au_0 + bv_0\).

La division euclidienne de \(a\) par \(m\) donne \(a = mq + r\) avec \(0 \leq r < m\). Si \(r > 0\) alors \(r = a - mq = a(1-u_0 q) + b(-v_0 q) \in E\) avec \(r < m\) : contradiction avec la minimalité de \(m\). Donc \(r = 0\), soit \(m \mid a\). De même \(m \mid b\). Donc \(m \mid \text{pgcd}(a,b) = 1\), d'où \(m = 1\). ✓

Remarques

• Le couple \((u,v)\) n'est pas unique. Par exemple pour \(\text{pgcd}(5,3)=1\) : \(5 \times (-1) + 3 \times 2 = 1\) et \(5 \times 2 + 3 \times (-3) = 1\).
• Le théorème assure l'existence d'au moins une solution implicite. En remarquant que \(au = 1 - bv\), c'est-à-dire \(au \equiv 1[b]\), on peut calculer \(u\) explicitement.

Algorithme Python — Coefficients de Bézout

def pgcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

def bezout(a, b):
    if pgcd(a, b) != 1:
        return "non_premiers"
    else:
        u = 1
        c = a
        while a % b != 1:
            u = u * c
            a = u * c
            v = int((1 - a) / b)
        return u, v

Exemple : \(a = 2022\), \(b = 557\) (premiers entre eux) → \(u = 73\), \(v = -265\).

Vérification : \(2022 \times 73 + 557 \times (-265) = 147606 - 147605 = 1\). ✓

Méthode ascendante — pgcd(44064, 2975) = 17

On effectue l'algorithme d'Euclide et on numérote les lignes :

Donc \(\text{pgcd}(44064, 2975) = 17\). On remonte les lignes :

\([1] \Rightarrow 17 = 170 - 51 \times 3\)

\([2] \Rightarrow 51 = 561 - 170 \times 3\), donc \(17 = 10 \times 170 - 3 \times 561\)

\([3] \Rightarrow 170 = 2414 - 561 \times 4\), donc \(17 = 10 \times 2414 - 43 \times 561\)

\([4] \Rightarrow 561 = 2975 - 2414 \times 1\), donc \(17 = 53 \times 2414 - 43 \times 2975\)

\([5] \Rightarrow 2414 = 44064 - 2975 \times 14\), donc \(17 = 53 \times 44064 + (-785) \times 2975\)

Couple solution : \((u,v) = (53, -785)\) — vérification : \(44064 \times 53 + 2975 \times (-785) = 2335392 - 2335375 = 17\). ✓

Méthode descendante (calcul littéral, en posant \(a = 44064\) et \(b = 2975\)) :

\([1] \Rightarrow 2414 = a - 14b\)

\([2] \Rightarrow 561 = b - 2414 = b - (a-14b) = 15b - a\)

\([3] \Rightarrow 170 = 2414 - 561 \times 4 = (a-14b) - 4(15b-a) = 5a - 74b\)

\([4] \Rightarrow 51 = 561 - 170 \times 3 = (15b-a) - 3(5a-74b) = -16a + 237b\)

\([5] \Rightarrow 17 = 170 - 51 \times 3 = (5a-74b) - 3(-16a+237b) = 53a - 785b = a \times \boxed{53} + b \times \boxed{-785}\)

On retrouve le même couple \((u,v) = (53, -785)\). La méthode descendante est plus systématique car elle permet d'élaborer un algorithme général.

Ce complément apporte la démonstration complète via Bézout, ainsi que deux corollaires importants et un exemple d'application.

Démonstration. Puisque \(\text{pgcd}(a,b) = 1\), le théorème de Bézout donne \(au + bv = 1\) pour certains \(u, v \in \mathbb{Z}\). En multipliant par \(c\) :

Puisque \(a \mid acu\) et \(a \mid bc\) (donc \(a \mid bcv\)), par combinaison linéaire \(a \mid c\). ✓

Corollaire 1 — Premiers entre eux et multiplication. Si \(a\) est premier avec \(b\) et avec \(c\), alors \(a\) est premier avec \(b \times c\).

Démonstration. Bézout donne \(au + bv = 1\) et \(au' + cv' = 1\). En multipliant : \((au+bv)(au'+cv') = 1\), soit \(a(auu' + cuv' + bvu') + bc(vv') = 1\). En posant \(u'' = auu'+cuv'+bvu'\) et \(v'' = vv'\) : \(au'' + (bc)v'' = 1\), donc \(\text{pgcd}(a, bc) = 1\). ✓

Corollaire 2 — Somme et produit. Soient \(a\) et \(b\) premiers entre eux. Alors \(a+b\) est premier avec \(a\), avec \(b\), et avec \(ab\).

Démonstration. Puisque \(a \wedge b = 1\), il existe \((u,v) \in \mathbb{Z}^2\) tel que \(au + bv = 1\).

\((a+b) \wedge a = 1\) : \(au+bv=1 \Leftrightarrow (a+b)v + a(u-v) = 1\). ✓

\((a+b) \wedge b = 1\) : \(au+bv=1 \Leftrightarrow (a+b)u + b(v-u) = 1\). ✓

\((a+b) \wedge ab = 1\) : par le Corollaire 1 ci-dessus. ✓

Ce complément apporte la résolution exhaustive en 5 cas de l'équation diophantienne ax + by = c, avec démonstrations, algorithme Python et exemple numérique complet.

Proposition. Soient \(S\) l'ensemble des solutions dans \(\mathbb{Z}^2\) de \(ax + by = c\), avec \(a, b, c \in \mathbb{Z}^*\) et \(d = \text{pgcd}(a,b)\). Alors \(S \neq \emptyset \iff d \mid c\).

Lorsque des solutions existent, elles sont initialisées par une solution particulière \((x_0, y_0)\), obtenue soit directement soit via les algorithmes de Bézout.

1er cas : a et b premiers entre eux et c = 0.

L'équation devient \(ax = b(-y)\). Puisque \(b \mid ax\) et \(a \wedge b = 1\), Gauss donne \(b \mid x\), soit \(x = bk\) avec \(k \in \mathbb{Z}\), puis \(y = -ak\). Ensemble des solutions : \(S_{(E)} = \{(bk, -ak) \ / \ k \in \mathbb{Z}\}\).

2e cas : a et b premiers entre eux et c = 1.

Bézout assure l'existence d'une solution particulière \((x_0, y_0)\). Si \((x,y)\) est une solution quelconque, on soustrait les deux équations : \(a(x-x_0) = b(y_0-y)\). Puisque \(b \mid a(x-x_0)\) et \(a \wedge b = 1\), Gauss donne \(b \mid x-x_0\), soit \(x = x_0 + bk\). On obtient \(y = y_0 - ak\). Ensemble des solutions : \(S_{(E)} = \{(x_0 + bk,\ y_0 - ak) \ / \ k \in \mathbb{Z}\}\).

3e cas : a et b premiers entre eux et c ≠ 1.

Puisque \(\text{pgcd}(a,b) = 1\), Bézout donne \((x_0,y_0)\) solution de \(ax_0 + by_0 = 1\). En multipliant par \(c\) : \(a(cx_0) + b(cy_0) = c\), donc \((X_0, Y_0) = (cx_0, cy_0)\) est une solution particulière. Le raisonnement du 2e cas donne : \(S_{(E)} = \{(cx_0 + bk,\ cy_0 - ak) \ / \ k \in \mathbb{Z}\}\).

4e cas : a et b non premiers entre eux et c = pgcd(a,b).

On pose \(c = d\), \(a = ca'\) et \(b = cb'\) avec \(\text{pgcd}(a',b') = 1\). L'équation se réduit à \(a'x + b'y = 1\) : on est ramené au 2e cas. Ensemble des solutions : \(S_{(E)} = \{(x_0 + b'k,\ y_0 - a'k) \ / \ k \in \mathbb{Z}\}\).

5e cas : a et b non premiers entre eux et c divisible par d = pgcd(a,b).

Il existe \(\alpha \in \mathbb{Z}^*\) tel que \(c = \alpha d\). Soit \((x_0,y_0)\) solution particulière de \(ax_0 + by_0 = d\) (cas 4). En multipliant par \(\alpha\) : \(a(\alpha x_0) + b(\alpha y_0) = c\). Ensemble des solutions (avec \(b' = b/d\) et \(a' = a/d\)) : \(S_{(E)} = \{(\alpha x_0 + b'k,\ \alpha y_0 - a'k) \ / \ k \in \mathbb{Z}\}\).

Algorithme Python — equadiop(a, b, c)

def equadiop(a, b, c):
    for u in range(-10, 10):
        for v in range(-10, 10):
            e = a*u + b*v
            if e == c:
                return u, v
    return "vide"

Note : cet algorithme cherche une solution particulière par force brute sur un intervalle. Pour de grands entiers, on utilise l'algorithme de Bézout.

Exemple numérique — 114x + 30y = 54

On calcule \(\text{pgcd}(114, 30) = 6\) et \(6 \mid 54\) → des solutions existent.

Le script Python donne \((x_0, y_0) = (1, -2)\) comme solution particulière.

En soustrayant les équations pour \((x,y)\) et \((x_0,y_0)\) :

En divisant par \(d=6\) : \(19(x-1) = 5(y_0-y)\). Puisque \(5 \mid 19(x-1)\) et \(\text{pgcd}(5,19)=1\), Gauss donne \(5 \mid x-1\), soit \(x = 1 + 5k\). Puis \(y = -2 - 19k\).

Vérification : \(114(1+5k) + 30(-2-19k) = 114 + 570k - 60 - 570k = 54\). ✓