Résoudre une équation diophantienne ax + by = c (avec l’algorithme d’Euclide)

Entrez les coefficients de l’équation diophantienne linéaire ax + by = c. L’équation ci-dessous est reliée aux champs de saisie : vous pouvez aussi modifier directement ses nombres. Changez « Solutions cherchées » pour ne garder que les solutions entières positives.

Coefficient a de x

Coefficient b de y

Constante c du membre de droite

Solutions cherchées

Entrez uniquement des nombres entiers (pas de nombres décimaux ni de fractions). Les nombres négatifs sont acceptés. S’il n’y a pas de terme en x ou en y, entrez 0 comme coefficient.

Résultat et graphique

Saisissez les coefficients a, b et c dans les champs à gauche et appuyez sur « Calculer ». Les solutions entières et un graphique s’affichent ici.

Table des matières

[ Fermer X ]

Ce que vous pouvez faire sur cette page
À quoi sert ce calcul ?
Mode d'emploi
Formules et graphiques
Symboles et termes
- Symboles
- Termes
Ce qu’il est utile de savoir avant de commencer
Calculer avec Excel
Calculer avec Google Sheets
Calculer avec Python
Écrire la formule en LaTeX et autres langages mathématiques (à copier-coller)
Faire faire le calcul par ChatGPT
Les atouts de DataChef
Fonctions connexes
Liste des calculatrices NumberChef

Ce que vous pouvez faire sur cette page

Saisissez les coefficients entiers \(a,\ b,\ c\) et obtenez les couples d’entiers \(x,\ y\) qui vérifient \(ax + by = c\) (les solutions entières)
Quand \(c\) n’est pas un multiple du plus grand commun diviseur de \(a\) et \(b\), il n’y a aucune solution entière. La page le vérifie et explique aussi pourquoi
Vous suivez ligne par ligne le tableau des divisions de l’algorithme d’Euclide et le tableau qui remonte les restes pour construire une solution particulière
La réponse n’est pas un seul couple : vous obtenez la solution générale \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (où \(t\) est un entier quelconque) et un tableau des solutions pour différentes valeurs de \(t\)
Vous pouvez ne garder que les solutions strictement positives ou que les solutions positives ou nulles. Cela résout directement des problèmes comme « combien de places à 50 € et à 80 € faut-il pour dépenser exactement 1 000 € ? »

Seuls les nombres entiers sont acceptés comme coefficients (pas de nombres décimaux ni de fractions). Chaque coefficient peut compter au maximum 15 chiffres, et \(a\) et \(b\) ne peuvent pas être nuls tous les deux.

À quoi sert ce calcul ?

Trouver les combinaisons qui donnent un montant ou un nombre exact

Acheter uniquement des places à 50 € et à 80 € pour dépenser exactement 1 000 €, peser un objet avec seulement deux sortes de masses marquées, obtenir une longueur exacte avec des morceaux de longueurs fixes : ces problèmes du type « combiner des choses de tailles fixes pour atteindre exactement un objectif » reviennent exactement à chercher les solutions entières de \(ax + by = c\).
On ne peut pas acheter un nombre négatif de places : en pratique, la réponse n’apparaît qu’une fois qu’on ne garde que les solutions entières positives.

Savoir quelles quantités on peut emballer exactement

Si vous n’avez que des boîtes de 6 et des boîtes de 10, pouvoir emballer une commande d’exactement \(c\) articles dépend de l’existence d’une solution de \(6x + 10y = c\) en entiers positifs ou nuls. Le PGCD de 6 et 10 est 2 : une commande d’un nombre impair d’articles ne pourra jamais être emballée exactement, quelle que soit la combinaison de boîtes.
Dans le conditionnement d’aliments ou de pièces, savoir quelles quantités sont réalisables indique quelles commandes accepter et quelles tailles de boîtes stocker.

Mesurer une quantité exacte avec des récipients sans graduations

La célèbre énigme qui consiste à mesurer exactement 4 L avec seulement un bidon de 5 L et un bidon de 3 L correspond aux solutions entières de \(5x + 3y = 4\) (\(x\) et \(y\) comptent, avec un signe, combien de fois chaque bidon est rempli ou vidé). Comme \(\gcd(5,\ 3) = 1\), l’équation vous dit d’avance que ces deux bidons permettent de mesurer n’importe quel nombre entier de litres.
C’est le même raisonnement qu’au laboratoire ou en cuisine quand on se demande : « Puis-je mesurer la quantité nécessaire avec les seuls ustensiles que j’ai ? »

Fabriquer les clés du chiffrement RSA sur Internet

Le chiffrement RSA, qui protège la banque et les achats en ligne, construit la valeur \(d\) de la clé privée à partir de la valeur \(e\) de la clé publique en résolvant l’équation diophantienne linéaire \(e d + \varphi k = 1\) (\(\varphi\) est un entier qui dépend de la clé). L’outil utilisé est le même algorithme d’Euclide étendu que sur cette page.
Cette méthode résout l’équation instantanément, même pour des nombres de plusieurs centaines de chiffres, et c’est l’une des choses qui rendent ce chiffrement utilisable en pratique.

Planifier une production qui utilise toute la matière

Supposons que le produit A consomme \(a\) kg de matière par unité et le produit B \(b\) kg, et que vous vouliez utiliser exactement les \(c\) kg dont vous disposez. Ce plan revient à chercher les solutions de \(ax + by = c\) en entiers positifs ou nuls. On ne peut pas fabriquer un demi-produit : la réponse doit être un nombre entier.
Le domaine qui traite les problèmes de planification dont les réponses doivent être entières s’appelle la programmation en nombres entiers. On l’utilise pour planifier une production, établir des plannings d’équipes, organiser des livraisons, etc.

Formules et graphiques

Quand existe-t-il des solutions entières ?

Graphique

Notation mathématique (l’écriture habituelle)

\(c\) \(=\) \(\gcd(a,\ b)\) \(\times\) \(m\)

En mots (les symboles remplacés par des mots)

③ \(c\) : constante du membre de droite \(=\) ① \(g\) : PGCD de \(a\) et \(b\) \(\times\) ② \(m\) : un entier

La formule en mots

① On multiplie le \(g\) : PGCD de \(a\) et \(b\)

② par \(m\) : un entier

③ Si ce produit peut être exactement égal à la \(c\) : constante du membre de droite (c’est-à-dire si \(c\) est un multiple de \(g\)), il existe des solutions entières. Sinon, il n’y en a aucune

Exemple simple

\(2x + 4y = 6\) a des solutions entières, mais \(2x + 4y = 5\) n’en a aucune (dans les deux cas, \(\gcd(2,\ 4) = 2\))

constante du membre de droite (6) \(=\) PGCD (2) \(\times\) entier (3)

\(\gcd(2,\ 4) = 2\)

\(6 = 2 \times 3 \quad \Rightarrow \quad 2 \times 1 + 4 \times 1 = 6\)

\(5 = 2 \times 2 + 1 \quad \Rightarrow \quad 2x + 4y \neq 5\)

L’idée clé

Pourquoi \(c\) doit-il être un multiple de \(g\) ? \(a\) et \(b\) sont tous deux des multiples de \(g\) : on peut écrire \(a = g a'\) et \(b = g b'\). Le membre de gauche devient alors \(ax + by = g(a'x + b'y)\) Tant que \(x\) et \(y\) sont des entiers, le membre de gauche est toujours un multiple de \(g\), et rien d’autre. Si \(c\), à droite, n’est pas un multiple de \(g\), aucun choix d’entiers ne peut rendre les deux membres égaux. À l’inverse, si \(c\) est un multiple de \(g\), une solution existe toujours (c’est ce que garantit l’identité de Bézout, la formule suivante). Sur le graphique, la différence est de savoir si la droite \(ax + by = c\) passe par des points à coordonnées entières (points dont l’abscisse et l’ordonnée sont toutes deux entières) ou si elle passe entre eux.

L’identité de Bézout (un couple d’entiers donné par l’algorithme d’Euclide)

Notation mathématique (l’écriture habituelle)

\(a x_1\) \(+\) \(b y_1\) \(=\) \(\gcd(a,\ b)\)

En mots (les symboles remplacés par des mots)

① \(a x_1\) : \(a\) fois l’entier \(x_1\) donné par l’algorithme d’Euclide \(+\) ② \(b y_1\) : \(b\) fois l’entier \(y_1\) donné par l’algorithme d’Euclide \(=\) ③ \(g\) : PGCD de \(a\) et \(b\)

La formule en mots

① En additionnant le terme \(a x_1\) : \(a\) fois l’entier \(x_1\) donné par l’algorithme d’Euclide

② et le terme \(b y_1\) : \(b\) fois l’entier \(y_1\) donné par l’algorithme d’Euclide

③ on peut obtenir exactement le \(g\) : PGCD de \(a\) et \(b\) . De tels entiers \(x_1,\ y_1\) existent toujours, et on les trouve en remontant l’algorithme d’Euclide

Exemple simple

En appliquant l’algorithme d’Euclide à \(7\) et \(5\), puis en remontant les restes (\(\gcd(7,\ 5) = 1\))

\(7\) fois l’entier \(-2\) \(+\) \(5\) fois l’entier \(3\) \(=\) PGCD (1)

\(7 = 5 \times 1 + 2, \quad 5 = 2 \times 2 + 1\)

\(1 = 5 - 2 \times 2 = 5 - (7 - 5) \times 2 = 3 \times 5 - 2 \times 7\)

\(7 \times (-2) + 5 \times 3 = -14 + 15 = 1\)

L’idée clé

Chaque reste de l’algorithme d’Euclide peut s’écrire comme une somme de multiples entiers des deux nombres de départ. En effet, \(2 = 7 - 5\), et si l’on remplace le \(2\) de l’étape suivante, \(1 = 5 - 2 \times 2\), par cette expression, \(1\) devient une somme de multiples entiers de \(7\) et de \(5\). L’algorithme d’Euclide étendu fait cela étape par étape pour n’importe quels nombres. Le couple \(x_1,\ y_1\) obtenu donne le PGCD \(g\), et non \(c\) : ce n’est donc pas encore une solution de votre équation. En multipliant les deux membres par \(\dfrac{c}{g}\), on obtient une solution de l’équation cherchée. \(x_0 = \dfrac{c}{g} x_1, \quad y_0 = \dfrac{c}{g} y_1\) Par exemple, pour \(7x + 5y = 3\), on multiplie l’égalité ci-dessus par 3 pour obtenir \(7 \times (-6) + 5 \times 9 = 3\) : \((x_0\,;\,y_0) = (-6\,;\,9)\) est une solution. Cette calculatrice décale la solution trouvée vers des nombres plus petits et plus lisibles avant de l’afficher (quel que soit le couple de départ, la solution générale ci-dessous donne le même ensemble de solutions).

Toutes les solutions entières (solution générale)

Graphique

Notation mathématique (l’écriture habituelle)

\(x\) \(=\) \(x_0\) \(+\) \(\dfrac{b}{g}\) \(t\)

\(y\) \(=\) \(y_0\) \(-\) \(\dfrac{a}{g}\) \(t\)

En mots (les symboles remplacés par des mots)

\(x\) : solution entière \(=\) ① \(x_0\) : solution particulière \(+\) ② \(\dfrac{b}{g}\) : pas de \(x\) ③ \(t\) : entier quelconque

\(y\) : solution entière \(=\) ④ \(y_0\) : solution particulière \(-\) ⑤ \(\dfrac{a}{g}\) : pas de \(y\) \(t\) : entier quelconque

La formule en mots

① On part de la \(x_0\) : solution particulière

② et on ajoute le \(\dfrac{b}{g}\) : pas de \(x\)

③ multiplié par \(t\) : entier quelconque . On obtient la solution entière \(x\)

④ En même temps, on part de la \(y_0\) : solution particulière

⑤ et on soustrait le \(\dfrac{a}{g}\) : pas de \(y\) multiplié par le même \(t\). On obtient la solution entière \(y\). Chaque entier choisi pour \(t\) donne une autre solution, et ensemble elles forment toutes les solutions entières

Exemple simple

Pour \(3x + 4y = 10\), une solution est \((x_0\,;\,y_0) = (2\,;\,1)\), et \(\gcd(3,\ 4) = 1\), donc

\(x\) : solution entière \(=\) solution particulière (2) \(+\) pas (4) entier \(t\)

\(y\) : solution entière \(=\) solution particulière (1) \(-\) pas (3) entier \(t\)

\(3 \times 2 + 4 \times 1 = 10\)

\(x = 2 + 4t, \quad y = 1 - 3t\)

\(t = 1 \ \Rightarrow \ (x\,;\,y) = (6\,;\,-2), \quad 3 \times 6 + 4 \times (-2) = 10\)

\(t = -1 \ \Rightarrow \ (x\,;\,y) = (-2\,;\,4), \quad 3 \times (-2) + 4 \times 4 = 10\)

L’idée clé

Pourquoi \(x\) n’avance-t-il que par pas de \(\dfrac{b}{g}\), et \(y\) que par pas de \(\dfrac{a}{g}\) ? Si \((x\,;\,y)\) et \((x_0\,;\,y_0)\) sont deux solutions, en soustrayant une égalité de l’autre, on obtient \(a(x - x_0) = -b(y - y_0)\) En divisant les deux membres par \(g\) : \(\dfrac{a}{g}(x - x_0) = -\dfrac{b}{g}(y - y_0)\). Ici, \(\dfrac{a}{g}\) et \(\dfrac{b}{g}\) sont premiers entre eux (leur seul diviseur commun est 1). Le membre de gauche doit donc être un multiple de \(\dfrac{b}{g}\). Comme \(\dfrac{a}{g}\) n’a aucun facteur commun avec lui, c’est \(x - x_0\) lui-même qui doit être un multiple de \(\dfrac{b}{g}\) (c’est le théorème de Gauss) : \(x - x_0 = \dfrac{b}{g}t\), et la formule pour \(y\) s’en déduit. Sur le graphique, les points à coordonnées entières de la droite \(ax + by = c\) sont régulièrement espacés : \(\dfrac{b}{g}\) en horizontal et \(\dfrac{a}{g}\) en vertical.

Ne garder que les solutions entières positives

Graphique

Notation mathématique (l’écriture habituelle)

\(x_0\) \(+\) \(\dfrac{b}{g}\) \(t\) \(\geqslant 1\)

\(y_0\) \(-\) \(\dfrac{a}{g}\) \(t\) \(\geqslant 1\)

En mots (les symboles remplacés par des mots)

① \(x_0\) : solution particulière \(+\) ② \(\dfrac{b}{g}\) : pas de \(x\) ③ \(t\) : entier quelconque \(\geqslant 1\)

④ \(y_0\) : solution particulière \(-\) ⑤ \(\dfrac{a}{g}\) : pas de \(y\) \(t\) : entier quelconque \(\geqslant 1\)

La formule en mots

① La \(x_0\) : solution particulière

② plus le \(\dfrac{b}{g}\) : pas de \(x\)

③ fois \(t\) : entier quelconque (c’est-à-dire la solution entière \(x\)) doit valoir au moins 1, et

④ la \(y_0\) : solution particulière

⑤ moins le \(\dfrac{a}{g}\) : pas de \(y\) fois le même \(t\) (c’est-à-dire la solution entière \(y\)) doit aussi valoir au moins 1. Trouvez les valeurs de \(t\) qui vérifient les deux conditions, et vous avez toutes les solutions entières strictement positives

Exemple simple

Pour obtenir exactement 47 articles avec seulement des lots de 3 et des lots de 5 (\(3x + 5y = 47\), \((x_0\,;\,y_0) = (4\,;\,7)\)) :

solution particulière (4) \(+\) pas (5) entier \(t\) \(\geqslant 1\)

solution particulière (7) \(-\) pas (3) entier \(t\) \(\geqslant 1\)

\(3 \times 4 + 5 \times 7 = 47\)

\(4 + 5t \geqslant 1 \ \Leftrightarrow \ t \geqslant -\dfrac{3}{5} \ \Leftrightarrow \ t \geqslant 0\)

\(7 - 3t \geqslant 1 \ \Leftrightarrow \ t \leqslant 2\)

\(0 \leqslant t \leqslant 2 \ \Rightarrow \ (x\,;\,y) = (4\,;\,7),\ (9\,;\,4),\ (14\,;\,1)\)

L’idée clé

Dans les problèmes où l’on compte des places, des objets ou des personnes, la réponse doit être un entier strictement positif (ou un entier positif ou nul). On traduit la solution générale en inéquations pour trouver les valeurs possibles de \(t\), et on ne garde que les solutions qui conviennent. Comme \(t\) est un entier, même quand une borne est une fraction comme \(t \geqslant -\dfrac{3}{5}\), on peut la resserrer jusqu’à l’entier le plus proche à l’intérieur (ici \(t \geqslant 0\)). C’est l’étape clé. Si \(a\) et \(b\) sont de même signe (par exemple tous deux positifs), une inéquation donne une borne inférieure et l’autre une borne supérieure : il y a donc toujours un nombre fini de solutions. S’ils sont de signes contraires (par exemple \(3x - 5y = 1\)), les deux bornes vont dans le même sens, et il y a une infinité de solutions entières strictement positives. Si l’un des coefficients est nul (par exemple \(0x + 5y = 10\)), l’autre inconnue n’a qu’une seule valeur possible, et l’inconnue au coefficient nul peut prendre n’importe quelle valeur. Si cette unique valeur vérifie la condition, il y a une infinité de solutions ; sinon, il n’y en a aucune. Il peut aussi arriver qu’aucun \(t\) ne vérifie la condition. La réponse est alors : « aucune combinaison ne convient ».

L’équation diophantienne linéaire \(ax + by = c\) n’a des solutions entières que si \(c\) est un multiple de \(g\), le plus grand commun diviseur de \(a\) et \(b\). Dans ce cas, on remonte l’algorithme d’Euclide pour construire une solution particulière \((x_0\,;\,y_0)\). Toutes les autres solutions sont alors \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (où \(t\) est un entier quelconque).

Symboles et termes

Symboles

\(a,\ b\)	a, b	Les coefficients qui multiplient \(x\) et \(y\). Par tradition, on désigne les nombres fixés par les premières lettres de l’alphabet, \(a,\ b,\ c\). Sur cette page, ce sont des entiers.
\(c\)	c	La constante du membre de droite de l’équation, d’après l’initiale de « constante ». C’est le total à atteindre, et selon qu’il est ou non un multiple du PGCD, l’équation a des solutions ou non.
\(x,\ y\)	x, y	Les inconnues à trouver. Désigner les inconnues par les dernières lettres de l’alphabet est une habitude qu’aurait popularisée Descartes. Sur cette page, seules les valeurs entières comptent comme réponses.
\(\gcd(a,\ b)\)	PGCD de a et b	Le plus grand commun diviseur de \(a\) et \(b\). C’est la notation internationale, d’après l’anglais « greatest common divisor » ; en France, on écrit plutôt \(\mathrm{PGCD}(a\,;\,b)\) ou \(a \wedge b\).
\(g\)	g	Une notation courte pour le plus grand commun diviseur \(\gcd(a,\ b)\), d’après l’initiale de l’anglais « greatest ». Elle raccourcit les formules, comme \(\dfrac{b}{g}\) et \(\dfrac{a}{g}\) dans la solution générale.
\(x_0,\ y_0\)	x zéro, y zéro	La solution particulière, c’est-à-dire la première solution entière trouvée. Le petit 0 indique le point de départ, « la solution numéro 0 ». Toutes les solutions entières s’écrivent à partir d’elle.
\(x_1,\ y_1\)	x indice 1, y indice 1	Le couple d’entiers obtenu en remontant l’algorithme d’Euclide. Il vérifie \(a x_1 + b y_1 = g\). En le multipliant par \(\dfrac{c}{g}\), on obtient la solution particulière \((x_0\,;\,y_0)\).
\(t\)	t	Une variable qui peut prendre n’importe quelle valeur entière (un paramètre). Elle permet de décrire toutes les solutions entières avec une seule formule. Chaque entier choisi pour \(t\) donne une autre solution entière.
\(m\)	m	L’entier qui indique combien de fois \(g\) est contenu dans \(c\). On utilise souvent \(m\), \(n\) ou \(k\) pour des entiers ; \(m\) viendrait de « multiple ». Il existe des solutions entières quand on peut écrire \(c = g \times m\), et seulement dans ce cas.
\(q\)	q	Le quotient d’une division, d’après l’initiale de « quotient ». Dans le tableau de l’algorithme d’Euclide, c’est le \(2\) de \(13 = 5 \times 2 + 3\).
\(r\)	r	Le reste d’une division, d’après l’initiale de l’anglais « remainder » (on le note aussi \(r\) en France, comme « reste »). Dans le tableau de l’algorithme d’Euclide, c’est le \(3\) de \(13 = 5 \times 2 + 3\). L’algorithme s’arrête quand ce reste devient 0.
\(\geqslant\)	supérieur ou égal à	Le signe d’inégalité qui signifie « le membre de gauche est supérieur ou égal au membre de droite ». \(x \geqslant 1\) signifie que \(x\) vaut 1 ou plus. Son pendant \(\leqslant\) signifie « inférieur ou égal à ».

Termes

équation diophantienne linéaire	Une équation du premier degré à deux inconnues, mais une seule équation, comme \(ax + by = c\). Dans les réels, tous les points de la droite sont des solutions : la solution n’est pas unique. Même en ne gardant que les solutions entières, il y en a en général une infinité. C’est le cas le plus simple d’équation diophantienne.
équation diophantienne	Le nom des équations dont on cherche les solutions en nombres entiers. Il vient de Diophante, mathématicien de la Grèce antique. L’équation diophantienne linéaire de cette page en est le cas le plus simple.
solution entière	Une solution de l’équation où \(x\) et \(y\) sont tous deux des entiers. Dans les problèmes sur des quantités qu’on ne peut pas couper, comme des nombres de places, d’objets ou de personnes, seules les solutions entières ont un sens.
solution particulière	Le premier couple trouvé parmi l’infinité de solutions entières. N’importe quel couple convient. À partir de lui, la solution générale décrit toutes les solutions.
solution générale	Toutes les solutions entières écrites avec une seule formule à l’aide d’un entier \(t\). Chaque entier choisi pour \(t\) donne une autre solution.
PGCD (plus grand commun diviseur)	Le plus grand entier positif qui divise chacun de deux entiers ou plus. Dans une équation diophantienne linéaire, cette valeur décide à la fois s’il existe des solutions et de l’écart entre elles.
algorithme d’Euclide	Une méthode pour trouver le plus grand commun diviseur : on divise le plus grand nombre par le plus petit et on remplace le couple par le diviseur et le reste, encore et encore. Le diviseur de l’étape où le reste devient 0 est le PGCD. Elle figure dans les « Éléments » d’Euclide, vers le IIIe siècle av. J.-C., et on la présente souvent comme le plus ancien algorithme du monde.
algorithme d’Euclide étendu	Une méthode pour écrire le plus grand commun diviseur sous la forme \(a x_1 + b y_1\) en substituant les égalités de division de l’algorithme d’Euclide, de bas en haut. Elle sert à construire une solution particulière d’une équation diophantienne linéaire.
identité de Bézout	Le théorème selon lequel il existe toujours des entiers \(x_1,\ y_1\) tels que \(a x_1 + b y_1 = \gcd(a,\ b)\). Il porte le nom du mathématicien français Étienne Bézout. C’est grâce à lui qu’une équation diophantienne linéaire peut être résolue.
premiers entre eux	Deux entiers sont premiers entre eux quand leur plus grand commun diviseur vaut 1. Par exemple, 3 et 4 sont premiers entre eux. \(\dfrac{a}{g}\) et \(\dfrac{b}{g}\) sont toujours premiers entre eux, et c’est pour cela que les solutions sont régulièrement espacées.
multiple	Un nombre obtenu en multipliant un entier par un autre entier. Les multiples de \(10\) sont \(\dots,\ -20,\ -10,\ 0,\ 10,\ 20,\ \dots\) Zéro et les nombres négatifs sont aussi des multiples.
reste	Ce qui reste quand une division entière ne tombe pas juste. \(13 \div 5\) donne un quotient de \(2\) et un reste de \(3\). L’algorithme d’Euclide ne travaille qu’avec ces restes.
quotient	Dans la division euclidienne, le nombre entier de fois que le diviseur est contenu dans le dividende. Dans \(13 = 5 \times 2 + 3\), le quotient est \(2\).
point à coordonnées entières	Un point du plan dont l’abscisse et l’ordonnée sont toutes deux des entiers, comme les croisements des lignes d’une feuille quadrillée. Les solutions entières d’une équation diophantienne linéaire sont exactement les points à coordonnées entières de la droite \(ax + by = c\).
paramètre	Une variable que l’on peut faire varier librement, utilisée pour écrire tout un ensemble de solutions avec une seule formule. Sur cette page, le paramètre est \(t\).
coefficient	Le nombre placé devant une lettre. Dans \(3x\), le coefficient est \(3\). Quand aucun nombre n’est écrit, comme dans \(x\), le coefficient vaut 1.
inéquation	Une inégalité qui contient une inconnue, comme \(5t \geqslant 1\), et que l’on résout pour trouver les valeurs possibles. Elle sert ici à ne garder que les solutions entières positives.

Ce qu’il est utile de savoir avant de commencer

Voici ce qu’il est utile de savoir pour utiliser le calcul de cette page en le comprenant, et pas seulement en appuyant sur le bouton.
Si vous bloquez, revoir ces notions est le chemin le plus court.

Division euclidienne et reste (CM1-6e, 9-12 ans)	Savoir que \(13 \div 5\) donne « quotient \(2\), reste \(3\) » et savoir l’écrire en une seule égalité, \(13 = 5 \times 2 + 3\) Savoir que le reste est toujours plus petit que le diviseur (au moins \(0\) et strictement inférieur au diviseur)
Diviseurs, multiples et PGCD (CM1-3e, 9-15 ans)	Savoir passer de « \(6\) est un multiple de \(3\) » à « \(3\) est un diviseur de \(6\) » Savoir trouver que le PGCD de \(12\) et \(18\) est \(6\) (la décomposition en facteurs premiers convient aussi) Savoir que deux nombres dont le PGCD vaut \(1\) sont dits « premiers entre eux »
Calcul littéral et équations du premier degré (5e-4e, 12-14 ans)	Savoir que dans une expression comme \(ax + by\), \(a\) et \(b\) sont des coefficients et \(x\) et \(y\) des inconnues Savoir résoudre une équation comme \(3 \times 2 + 5y = 1\) en \(y\) Savoir factoriser par un nombre commun, comme dans \(4x + 6y = 2(2x + 3y)\)
Équations de droites (3e-2de, 14-16 ans)	Savoir que \(ax + by = c\) représente une droite dans un repère Savoir qu’avec deux inconnues et une seule équation, il n’y a pas une réponse unique : tous les points de la droite sont des solutions
Inéquations (3e-2de, 14-16 ans)	Savoir transformer \(5t \geqslant 1\) en \(t \geqslant \dfrac{1}{5}\) Savoir qu’en divisant les deux membres par un nombre négatif, on change le sens de l’inégalité Savoir que si \(t \leqslant \dfrac{5}{3}\) et que \(t\) est un entier, on peut resserrer jusqu’à \(t \leqslant 1\)
Calculer avec des fractions (6e-4e, 11-14 ans)	Savoir simplifier une fraction comme \(\dfrac{80}{10} = 8\) Savoir comparer des fractions négatives comme \(-\dfrac{3}{8}\) sur une droite graduée

Calculer avec Excel

Copiez tout le tableau ci-dessous et collez-le dans la cellule A1 d’Excel. Il fonctionne tel quel.

Tableau pour vérifier s’il existe des solutions entières

Coefficient a de x	50
Coefficient b de y	80
Constante c du membre de droite	1000
PGCD g	=PGCD(B1;B2)
Reste de c ÷ g	=MOD(B3;B4)
Solutions entières ?	=SI(B5=0;"Il y a des solutions";"Pas de solution")

Tableau pour vérifier l’identité de Bézout

Coefficient a de x	50
Coefficient b de y	80
x1 donné par l’algorithme d’Euclide	-3
y1 donné par l’algorithme d’Euclide	2
a×x1 + b×y1	=B1B3+B2B4
PGCD g	=PGCD(B1;B2)

Tableau pour obtenir des solutions à partir de la solution générale

Coefficient a de x	50
Coefficient b de y	80
Constante c du membre de droite	1000
PGCD g	=PGCD(B1;B2)
Solution particulière x0	4
Solution particulière y0	10
Entier t	1
x = x0 + (b/g)×t	=B5+(B2/B4)*B7
y = y0 − (a/g)×t	=B6-(B1/B4)*B7
Vérification a×x + b×y	=B1B8+B2B9

Tableau pour ne garder que les solutions entières positives

Coefficient a de x	50
Coefficient b de y	80
PGCD g	=PGCD(B1;B2)
Solution particulière x0	4
Solution particulière y0	10
Borne inférieure de t (avec x ⩾ 1)	=-ENT((B4-1)/(B2/B3))
Borne supérieure de t (avec y ⩾ 1)	=ENT((B5-1)/(B1/B3))
Nombre de solutions entières strictement positives	=MAX(0;B7-B6+1)

Une fois le tableau collé, les lignes du haut (coefficients et solution particulière) sont vos données et les lignes du bas se calculent automatiquement. PGCD donne le plus grand commun diviseur, MOD le reste d’une division, et ENT supprime la partie décimale (arrondit vers le bas).
Le premier tableau reprend l’exemple 50x + 80y = 1000. Le PGCD vaut 10 et 1000 ÷ 10 donne un reste de 0 : il affiche donc « Il y a des solutions ». Remplacez 1000 par 1001 et il affiche « Pas de solution ».
Le deuxième tableau vérifie que x1 = −3 et y1 = 2, obtenus en remontant l’algorithme d’Euclide, vérifient bien l’identité de Bézout : 50×(−3) + 80×2 = 10, ce qui est bien le PGCD.
Le troisième tableau tire une solution de la solution générale. Avec t = 1, on obtient x = 12 et y = 5, et la ligne de vérification redonne 1000. Essayez d’autres entiers pour t.
Le quatrième tableau ne garde que les solutions entières strictement positives. La borne inférieure de t est 0 et la borne supérieure 1 : il y a donc 2 solutions entières strictement positives (t = 0 et t = 1). Ces deux formules valent pour a et b tous deux positifs. Avec un coefficient négatif, le sens de l’inéquation change : attention.

Calculer avec Google Sheets

Copiez tout le tableau ci-dessous et collez-le dans la cellule A1 de Google Sheets. Il fonctionne tel quel.

Tableau pour vérifier s’il existe des solutions entières

Coefficient a de x	50
Coefficient b de y	80
Constante c du membre de droite	1000
PGCD g	=PGCD(B1;B2)
Reste de c ÷ g	=MOD(B3;B4)
Solutions entières ?	=SI(B5=0;"Il y a des solutions";"Pas de solution")

Tableau pour vérifier l’identité de Bézout

Coefficient a de x	50
Coefficient b de y	80
x1 donné par l’algorithme d’Euclide	-3
y1 donné par l’algorithme d’Euclide	2
a×x1 + b×y1	=B1B3+B2B4
PGCD g	=PGCD(B1;B2)

Tableau pour obtenir des solutions à partir de la solution générale

Coefficient a de x	50
Coefficient b de y	80
Constante c du membre de droite	1000
PGCD g	=PGCD(B1;B2)
Solution particulière x0	4
Solution particulière y0	10
Entier t	1
x = x0 + (b/g)×t	=B5+(B2/B4)*B7
y = y0 − (a/g)×t	=B6-(B1/B4)*B7
Vérification a×x + b×y	=B1B8+B2B9

Tableau pour ne garder que les solutions entières positives

Coefficient a de x	50
Coefficient b de y	80
PGCD g	=PGCD(B1;B2)
Solution particulière x0	4
Solution particulière y0	10
Borne inférieure de t (avec x ⩾ 1)	=-ENT((B4-1)/(B2/B3))
Borne supérieure de t (avec y ⩾ 1)	=ENT((B5-1)/(B1/B3))
Nombre de solutions entières strictement positives	=MAX(0;B7-B6+1)

Les formules d’Excel fonctionnent telles quelles dans Google Sheets en français (PGCD, MOD, ENT, MAX et SI ont les mêmes noms et le même rôle). Copiez tout le tableau, collez-le dans la cellule A1 et remplacez les coefficients par vos propres nombres.

Calculer avec Python

from math import gcd

# coefficients de ax + by = c (entiers)
a, b, c = 50, 80, 1000

def extended_gcd(x, y):
    # algorithme d'Euclide étendu : renvoie le PGCD et s, t tels que x*s + y*t = PGCD
    if y == 0:
        return x, 1, 0
    g, s, t = extended_gcd(y, x % y)
    return g, t, s - (x // y) * t

g = gcd(a, b)
if c % g != 0:
    print(f"{c} n'est pas un multiple de {g}, il n'y a donc pas de solution entière")
else:
    _, s, t = extended_gcd(a, b)
    x0, y0 = s * (c // g), t * (c // g)   # solution particulière (une solution entière)
    step_x, step_y = b // g, a // g       # pas de x et pas de y
    # on décale jusqu'à ce que x soit la plus petite valeur positive ou nulle, pour une solution plus lisible
    n = x0 // step_x
    x0, y0 = x0 - n * step_x, y0 + n * step_y
    print(f"Solution particulière : (x ; y) = ({x0} ; {y0})")
    print(f"Solution générale : x = {x0} + {step_x}t, y = {y0} - {step_y}t (t entier quelconque)")
    for k in range(-2, 3):
        print(f"  t = {k:2} : (x ; y) = ({x0 + step_x * k} ; {y0 - step_y * k})")
    # on ne garde que les solutions entières strictement positives (x >= 1 et y >= 1)
    t_low = -((1 - x0) // -step_x)
    t_high = (y0 - 1) // step_y
    print("Solutions entières strictement positives :", [(x0 + step_x * k, y0 - step_y * k)
                                        for k in range(t_low, t_high + 1)])

Il suffit de math.gcd de la bibliothèque standard et d’un algorithme d’Euclide étendu écrit de façon récursive. L’exemple est 50x + 80y = 1000. À l’exécution, le programme affiche la solution particulière (4 ; 10), la solution générale x = 4 + 8t, y = 10 − 5t, et les solutions entières strictement positives [(4, 10), (12, 5)] (Python écrit les couples avec une virgule). Changez les coefficients pour essayer (la dernière partie, pour les solutions strictement positives, suppose a et b tous deux positifs).

Écrire la formule en LaTeX et autres langages mathématiques (à copier-coller)

Quand existe-t-il des solutions entières ?

c = gcd(a, b) × m

c = \gcd(a, b) \times m

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>c</mi>
    <mo>=</mo>
    <mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>&#xD7;</mo>
    <mi>m</mi>
  </mrow>
</math>

c = gcd(a, b) * m

Mod[c, GCD[a, b]] == 0

irem(c, igcd(a, b)) = 0;

mod(c, gcd(a, b)) == 0

c = gcd(a,b) × m

L’identité de Bézout (un couple d’entiers donné par l’algorithme d’Euclide)

a·x₁ + b·y₁ = gcd(a, b)

a x_1 + b y_1 = \gcd(a, b)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><msub><mi>x</mi><mn>1</mn></msub>
    <mo>+</mo>
    <mi>b</mi><msub><mi>y</mi><mn>1</mn></msub>
    <mo>=</mo>
    <mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
  </mrow>
</math>

a*x_1 + b*y_1 = gcd(a, b)

ExtendedGCD[a, b]

igcdex(a, b, x1, y1);

[g, x1, y1] = gcd(a, b);

a x_1 + b y_1 = gcd(a,b)

Toutes les solutions entières (solution générale)

x = x₀ + (b/g)t, y = y₀ − (a/g)t

x = x_0 + \frac{b}{g} t, \quad y = y_0 - \frac{a}{g} t

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>x</mi><mo>=</mo><msub><mi>x</mi><mn>0</mn></msub>
    <mo>+</mo>
    <mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>,</mo><mspace width="1em"/>
    <mi>y</mi><mo>=</mo><msub><mi>y</mi><mn>0</mn></msub>
    <mo>&#x2212;</mo>
    <mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
  </mrow>
</math>

x = x_0 + (b/g)t, y = y_0 - (a/g)t

Solve[a x + b y == c, {x, y}, Integers]

isolve(a*x + b*y = c);

S = solve(a*x + b*y == c, [x y], 'Integer', true);

x = x_0 + (b/g)t, y = y_0 - (a/g)t

Ne garder que les solutions entières positives

x₀ + (b/g)t ⩾ 1 et y₀ − (a/g)t ⩾ 1

x_0 + \frac{b}{g} t \geqslant 1, \quad y_0 - \frac{a}{g} t \geqslant 1

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <msub><mi>x</mi><mn>0</mn></msub>
    <mo>+</mo>
    <mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>&#x2A7E;</mo><mn>1</mn>
    <mo>,</mo><mspace width="1em"/>
    <msub><mi>y</mi><mn>0</mn></msub>
    <mo>&#x2212;</mo>
    <mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>&#x2A7E;</mo><mn>1</mn>
  </mrow>
</math>

x_0 + (b/g)t >= 1 and y_0 - (a/g)t >= 1

Solve[a x + b y == c && x >= 1 && y >= 1, {x, y}, Integers]

isolve({a*x + b*y = c, x >= 1, y >= 1});

S = solve([a*x + b*y == c, x >= 1, y >= 1], [x y], 'Integer', true);

x_0 + (b/g)t ⩾ 1, y_0 − (a/g)t ⩾ 1

Faire faire le calcul par ChatGPT

Tu es un assistant de calcul en arithmétique (propriétés des nombres entiers). Effectue le calcul suivant en exécutant réellement du code Python, et fonde ta réponse uniquement sur les nombres obtenus à l’exécution (ne réponds pas de tête ni par estimation).

Trouve les solutions entières de l’équation diophantienne linéaire 50x + 80y = 1000.
Donne chacun des éléments suivants :
1. Le PGCD de 50 et 80, et si 1000 en est un multiple
2. Les étapes de division de l’algorithme d’Euclide (jusqu’à un reste nul), et les x1, y1 tels que 50×x1 + 80×y1 = PGCD obtenus en remontant ces étapes
3. Une solution particulière (x0 ; y0) et la solution générale x = x0 + (b/g)t, y = y0 − (a/g)t
4. Toutes les solutions entières où x et y valent tous deux 1 ou plus

En Python, utilise math.gcd et l’algorithme d’Euclide étendu pour calculer exactement, et indique les formules utilisées et les nombres obtenus à l’exécution.

Mode d'emploi

1

Saisissez vos nombres

Tapez les nombres à calculer dans les champs de saisie
2

Calculez

Appuyez sur le bouton « Calculer »
3

Lisez le résultat

Le résultat s’affiche aussitôt. La même page explique aussi le raisonnement et la formule