Voir la source de Équation diophantienne ax + by = c

{{Titre mis en forme|1=Équation diophantienne ''ax + by = c''}}

L''''équation ''ax + by = c''''', où les coefficients ''a'', ''b ''et ''c ''sont trois [[entier relatif|entiers relatifs]] (''a'' et ''b'' non tous deux nuls) et où les [[inconnue (mathématiques)|inconnues]] ''x ''et ''y ''sont des entiers relatifs, est une des [[équation diophantienne|équations diophantiennes]] les plus simples à résoudre. Sa résolution s'appuie sur l'[[algorithme d'Euclide étendu|algorithme d'Euclide]], le [[théorème de Bachet-Bézout]] (qui correspond au cas, appelé aussi '''identité de Bézout''', où ''c ''est égal au [[Plus grand commun diviseur|PGCD]] de ''a ''et ''b'') et le [[Lemme d'Euclide|théorème de Gauss]].

Dans l'ensemble des entiers relatifs, une telle équation possède, ou bien aucune solution, ou bien une infinité de solutions. Lorsque les coefficients et les inconnues sont des [[entier naturel|entiers naturels]], l'équation possède un nombre fini de solutions. Le théorème de Paoli en donne le nombre à 1 près.

== Recherche de solutions dans l'ensemble des entiers relatifs ==
=== Équation ''ax + by ''= 1 où ''a ''et ''b ''sont premiers entre eux ===
Le [[théorème de Bachet-Bézout]] affirme que cette équation admet toujours au moins une solution.

La première étape de la résolution consiste à trouver une solution particulière, c'est-à-dire un [[Couple (mathématiques)|couple]] d'entiers relatifs (''x''<sub>0</sub>, ''y''<sub>0</sub>) vérifiant : ''ax''<sub>0</sub> + ''by''<sub>0</sub> = 1.
* L'[[algorithme d'Euclide étendu]] permet d'en exhiber une. (On peut remarquer que cet algorithme s'interprète comme le calcul du [[Fraction continue#Développement en fraction continue d'un rationnel|développement en fraction continue du rationnel]] ''a''/''b'' ; l'avant dernière réduite ''h''{{ind|''n''–1}}/''k''{{ind|''n''–1}} fournit une solution du problème<ref>{{Ouvrage|auteur=[[Eugène Cahen]]|titre=Éléments de la théorie des nombres|éditeur=Gauthier-Villars|lieu=Paris|année=1900|url=https://archive.org/stream/lmentsdelath00caheuoft#page/60/mode/2up|page=60-61}}.</ref>, puisque {{nobr|1=''k''{{ind|''n''–1}}''a ''– ''h''{{ind|''n''–1}}''b ''= (–1){{exp|''n''+1}}.)}}
*On peut travailler [[Congruence sur les entiers|modulo ''b'']], en cherchant d'abord un entier ''x''{{ind|0}} tel que ''ax''{{ind|0}} ≡ 1 (mod ''b''). L'entier ''y''{{ind|0}} se calcule ensuite comme étant égal à (1 – ''ax''{{ind|0}})/''b''.
**Pour trouver un ''x''{{ind|0}} [[Inverse modulaire|inverse  de ''a'' mod ''b'']], on peut se servir du [[théorème d'Euler (arithmétique)|théorème de Fermat généralisé par Euler]], d'après lequel ''a''{{exp|φ(''b'')}} est congru à 1 modulo ''b'', où φ est l'[[indicatrice d'Euler]] : l'entier ''x''{{ind|0}} = ''a''{{exp|φ(''b'')–1}} convient<ref>{{Harvsp|Cahen|1900|p=68-69}}.</ref>. De même, l'entier ''x''{{ind|0}} = ''a''{{exp|λ(''b'')–1}} convient, où λ est la [[Indicatrice de Carmichael|fonction de Carmichael]].
**Mais on peut aussi, si ''b ''n'est pas trop grand, chercher une solution par simple balayage, en cherchant quel entier ''x''{{ind|0}} compris entre 1 et |''b''| – 1 vérifie la [[congruence linéaire]] ''ax''{{ind|0}} ≡ 1 (mod ''b'').

{{Théorème|Ensemble des solutions|Une solution particulière (''x''<sub>0</sub>, ''y''<sub>0</sub>) étant connue, l'ensemble des solutions est formé des couples (''x''<sub>0</sub> + ''bk'', ''y''<sub>0</sub> – ''ak'') où ''k ''est un entier relatif quelconque.}}

En effet, il est facile de vérifier qu'un tel couple est solution du problème :
: <math>\forall k \in\Z ,\, a(x_0+bk)+b(y_0-ak)=ax_0+by_0=1.</math>
Il s'agit maintenant de prouver que seuls ces couples sont solutions. Supposons donc que le couple (''x'', ''y'') est solution de l'équation. On a donc 
: <math>(1):\qquad ax+by=1=ax_0+by_0.</math>
En regroupant autrement les termes, on obtient
: <math>(2):\qquad a(x-x_0)=-b(y-y_0).</math>
L'entier ''b ''divise donc le produit ''a''(''x – x''<sub>0</sub>). Comme ''a ''et ''b ''sont premiers entre eux, le [[Lemme d'Euclide|lemme de Gauss]] permet de dire que ''b ''divise ''x – x''<sub>0</sub>. Il existe donc un entier relatif ''k ''tel que ''x – x''<sub>0</sub> = ''kb''. Soit encore
: <math>(3):\qquad x=x_0+kb.</math>
En remplaçant ''x – x''<sub>0</sub> par ''kb ''dans (2), on obtient :
: <math>(4) \qquad akb=-b(y-y_0).</math>
Puis en simplifiant par –''b''
: <math>(5) \qquad y-y_0=-ak.</math>
Soit encore 
: <math>(6) \qquad y=y_0-ak.</math>
Donc, si (''x'', ''y'') est solution de (1) alors, il existe un entier relatif ''k ''tel que (''x'', ''y'') = (''x''<sub>0</sub> + ''bk'', ''y''<sub>0</sub> – ''ak'').

=== Équation ''ax + by = c ''où ''a ''et ''b ''sont premiers entre eux ===
Une solution particulière peut être trouvée en multipliant par ''c ''une solution particulière de l'équation ''ax + by ''= 1. En effet, si (''x''<sub>0</sub>, ''y''<sub>0</sub>) vérifie ''ax''<sub>0</sub> + ''by''<sub>0</sub> = 1 alors ''ax''<sub>0</sub>''c + by''<sub>0</sub>''c = c ''; le couple  (''x''<sub>0</sub>''c'', ''y''<sub>0</sub>''c'')  est alors solution de l'équation ''ax + by = c''.

Un raisonnement analogue au précédent permet de trouver l'ensemble des solutions :
{{Théorème|Ensemble des solutions|Une solution particulière (''x''<sub>1</sub>, ''y''<sub>1</sub>) étant connue, l'ensemble des solutions est formé des couples (''x''<sub>1</sub> + ''bk'', ''y''<sub>1</sub> – ''ak'') où ''k ''est un entier relatif quelconque.}}

=== Cas général ===
On appelle ''d ''le pgcd de ''a ''et de ''b''.

{{Théorème|Si ''c ''n'est pas un multiple de ''d''|  L'équation n'a pas de solution.}}
En effet, ''d ''divisant ''a ''et ''b'', ''d ''divise aussi toute expression de la forme ''ax + by ''où ''x ''et ''y ''sont des entiers relatifs, donc ''d ''doit diviser ''c''.

On suppose maintenant que ''d ''divise ''c ''; il existe alors trois entiers relatifs ''a''<sub>1</sub>, ''b''<sub>1</sub> et ''c''<sub>1</sub> tels que 
: ''a = da''<sub>1</sub>
: ''b = db''<sub>1</sub>
: ''c = dc''<sub>1</sub>
avec ''a''<sub>1</sub> et ''b''<sub>1</sub> premiers entre eux.

L'équation ''ax + by = c ''est alors équivalente à l'équation ''a''<sub>1</sub>''x + b''<sub>1</sub>''y = c''<sub>1</sub> dans laquelle ''a''<sub>1</sub> et ''b''<sub>1</sub> sont premiers entre eux, et ce cas a déjà été résolu. On obtient alors la résolution dans le cas général :
: Une solution particulière (''x''<sub>1</sub>, ''y''<sub>1</sub>) étant connue, l'ensemble des solutions est formé des couples (''x''<sub>1</sub> + ''b''<sub>1</sub>''k'', ''y''<sub>1</sub> – ''a''<sub>1</sub>''k'') où ''k ''est un entier relatif quelconque.

D'où  la propriété : 
{{Théorème|Si ''c ''est  un multiple de ''d''| L'équation  admet toujours des solutions. Une solution particulière (''x''<sub>1</sub>, ''y''<sub>1</sub>) étant connue, l'ensemble des solutions est formé des couples (''x''<sub>1</sub> + ''bk''/''d'', ''y''<sub>1</sub> – ''ak''/''d'') où ''k ''est un entier relatif quelconque.}}

=== Système minimal ===
On suppose dans cette section que ''c ''est un multiple de ''d''. Parmi toutes les solutions d'une équation ''ax + by = c ''donnée, on peut chercher celle(s) pour laquelle ''x''{{2}} + ''y''{{2}} soit la plus petite possible.

Il s'agit de rendre minimale la valeur (''x''<sub>1</sub> + ''b''{{ind|1}}''k''){{2}} + (''y''<sub>1</sub> – ''a''{{ind|1}}''k''){{2}}. Si l'on considère la fonction de la variable réelle ''t ''définie par ''f''(''t'') = (''x''<sub>1</sub> + ''b''{{ind|1}}''t''){{2}} + (''y''<sub>1</sub> – ''a''{{ind|1}}''t''){{2}}, l'étude de cette fonction du second degré montre que celle-ci possède un minimum en<ref name="Système minimum">{{Ouvrage|auteur=Édouard Lucas|url=http://visualiseur.bnf.fr/CadresFenetre?O=NUMM-29021|titre=Théorie des nombres|date=1891}}, {{page|478 §263}}.
</ref> 
{{retrait|<math>t=\frac{a_1y_1-b_1x_1}{a_1^2+b_1^2}.</math>}}
Si ''t ''est entier, le couple solution est alors (''x''<sub>1</sub> + ''b''{{ind|1}}''t'', ''y''<sub>1</sub> – ''a''{{ind|1}}''t'') ; sinon, l'entier qui rend ''f'' minimale est le (ou les) entier(s) ''k ''le(s) plus proche(s) de ''t''.

Le(s) couple(s) d'entiers solution de ''ax + by = c ''dont la valeur ''x''{{2}} + ''y''{{2}} est minimale est (ou sont) le (ou les) couple(s) (''x''<sub>1</sub> + ''b''{{ind|1}}''k'', ''y''<sub>1</sub> – ''a''{{ind|1}}''k'') où ''k ''est le (ou les) entier(s) le(s) plus proche(s) de {{nobr|1=''t ''= (''a''{{ind|1}}''y''{{ind|1}} – ''b''{{ind|1}}''x''{{ind|1}})/(''a''{{ind|1}}{{2}} + ''b''{{ind|1}}{{2}}).}}

Dans le cas où ''a ''et ''b ''sont premiers entre eux, le cas où ''t ''est entier mérite d'être explicité. On démontre que ''t ''est entier si et seulement si l'entier ''c ''est un multiple de ''a''{{2}} + ''b''{{2}}. La solution du système minimal est alors<ref name="Système minimum"/> <math> \left(\frac{ac}{a^2+b^2},\frac{bc}{a^2+b^2}\right)</math>.

Dans le cas où ''a ''et ''b ''sont premiers entre eux, il existe deux solutions au système minimal si et seulement si ''a ''et ''b ''sont impairs et l'entier ''c ''est un multiple impair de (''a''{{2}} + ''b''{{2}})/2.

== Applications ==
=== Congruence ===
La résolution de l'équation ''ax + by ''= 1, où ''a ''et ''b ''sont premiers entre eux, permet de trouver un inverse à ''a ''modulo ''b'', c'est-à-dire un entier ''x ''tel que ''ax ''≡ 1 (mod ''b''). L'ensemble des solutions permet de dire qu'il existe une unique classe ''x ''telle que ''ax ''= 1 dans ℤ/''b''ℤ. En effet, parmi les couples solutions, tous les entiers ''x ''sont congrus modulo ''b''.

=== Équation de droite ===
L'ensemble des points M(''x'', ''y'') vérifiant l'équation ''ax + by = c'' forme une droite. Les couples d'entiers relatifs vérifiant cette équation correspondent aux points M de la droite dont les coordonnées sont entières. La résolution de l'équation dans l'ensemble des entiers relatifs permet de donner les coordonnées de ces points. Selon la valeur de ''c'', la droite D peut ne jamais passer par des points de coordonnées entières ou bien posséder une infinité de points de coordonnées entière régulièrement répartis.
{| width="100%" align="center" border="0" cellpadding="4" cellspacing="4" 
|- valign="top"
| width="50%" |
[[Image:Diophante Bezout.svg|thumb|center|300 px| Résolution graphique de l'équation 9''x ''+ 12''y ''= 483.]]

| width="50%" |
[[Image:Diophante Bezout(2).svg|thumb|center|300 px| La droite d'équation 4''x ''+ 6''y ''= 81 ne passe par aucun point de coordonnées entières.]]

|}

La solution du système minimal se lit alors très facilement. Le ou les couples solutions correspondent aux points dont les coordonnées vérifient ''x''{{2}} + ''y''{{2}} est minimal. Ce sont donc les points de la droite les plus proches de l'origine. Le point O se projette sur la droite en H. La solution du système minimal est donc le (ou les) points de la droite  de coordonnées entières situé(s) le plus près de H.
{| width="100%" align="center" border="0" cellpadding="4" cellspacing="4" 
|- valign="top"
| width="33%" |
[[Image:Diophante Bezout minimum(1).svg|thumb|center|250 px| Les coordonnées de H fournissent la solution au système minimum de l'équation 2''x ''+ 3''y ''= 26.]]
| width="33%" |
[[Image:Diophante Bezout minimum(2).svg|thumb|center|250 px| Les coordonnées de M1 et M2 fournissent les solutions  au système minimum de l'équation {{nobr|1=3''x ''+ 5''y ''= 51.}}]]
| width="33%" |
[[Image:Diophante Bezout minimum(3).svg|thumb|center|250 px| Les coordonnées de M fournissent la solution au système minimum de l'équation 2''x ''+ 3''y ''= 31.]]
|}

=== Réduction d'une fraction en éléments simples ===
Décomposer une fraction irréductible ''A''/''B ''en éléments simples, c'est la décomposer en somme d'un entier relatif et de fractions de la forme ''r{{ind|j,i}} ''/ ''p{{ind|i}} {{exp|j}} ''dans laquelle ''p{{ind|i}} ''est un nombre premier apparaissant dans la décomposition de ''B ''en facteurs premiers, ''j ''est un exposant entier non nul ne dépassant pas l'exposant de ''p{{ind|i}} ''dans la décomposition de ''B ''et ''r{{ind|j,i}} ''est un entier compris entre 0 et ''p{{ind|i}} ''– 1.

[[Édouard Lucas|Lucas]]{{sfn|Lucas|1891}} prouve l'existence d'une telle décomposition. Il procède en plusieurs étapes.

Si <math> B = p^n</math>, où ''p ''est un nombre premier, une simple écriture de ''A ''dans la [[Base (arithmétique)|base]] ''p ''permet d'aboutir. En effet 
: <math>A = r_0+ r_1p+r_2p^2+\cdots + r_{n-1}p^{n-1}+ Ep^n</math>
où les <math>r_i</math> sont des entiers compris entre 0 et ''p ''– 1 et ''E ''est un entier relatif.
D'où en divisant par ''B''
:<math>\frac AB = \frac {r_0}{p^n}+\frac{r_1}{p^{n-1}}+ \cdots + \frac{r_{n-1}}{p} + E.</math>
La seconde étape consiste à travailler sur un nombre ''B = ab ''où ''a ''et ''b ''sont premiers entre eux et c'est là qu'intervient l'équation diophantienne. Les deux nombres sont premiers entre eux, il existe donc des entiers relatifs ''x ''et ''y ''tels que 
: ''ax + by = A''
donc 
: <math>\frac AB = \frac A{ab}= \frac{x}{b} +\frac{y}{a}.</math> 
La décomposition de la fraction sera donc établie dès que seront obtenues les décompositions des fractions ''x''/''b ''et ''y''/''a''.

Lucas procède alors de proche en proche. Si <math>B=p_1^{n_1}\times p_2^{n_2} \times \cdots \times p_k^{n_k}</math> alors on peut poser <math>a = p_1^{n_1}</math> et <math>b = \frac Ba</math>
: <math>\frac AB = \frac A{ab}= \frac{x}{b} +\frac{y}{a} =  \frac{x}{b} +  \frac{y}{p_1^{n_1}}.</math>
La seconde fraction se décompose aisément et la première est à décomposer  en utilisant le même processus. Il suffit de ''k ''– 1 étapes pour arriver au bout de la décomposition complète.

Lucas démontre que malgré la multiplicité des méthodes pour arriver à la décomposition, celle-ci est unique.

Exemple : Décomposition de la fraction <math>\frac{259}{90}</math>

On décompose 90 en 9×10. On cherche deux entiers ''x ''et ''y ''tels que 9''x ''+ 10''y ''= 259. On peut prendre ''x ''= 1 et ''y ''= 25.
: <math>(1) \qquad \frac{259}{90} =\frac{1}{10}+ \frac{25}{9}.</math>
On décompose 10 en 2×5. On cherche deux entiers ''x ''et ''y ''tels que 2''x ''+ 5''y ''= 1. On peut prendre ''x ''= 3 et ''y ''= –1.
: <math>(2) \qquad \dfrac{1}{10} = \dfrac{3}{5} - \dfrac{1}{2} = -1 + \dfrac{3}{5} + \dfrac{1}{2}.</math> 
On écrit 25 en base 3 
: <math>\qquad 25 = 1+3\times 8 = 1 + 3 \times(2 + 3 \times 2) = 1+2 \times 3 + 2 \times 3^2.</math>
Donc 
:<math>(3) \qquad \frac{25}{9} = \frac{1}{3^2} + \dfrac{2}{3} + 2.</math>
Il suffit de remplacer dans (1) les résultats trouvés dans (2) et (3)
: <math>\frac{259}{90} = 1 + \frac{1}{3^2} + \dfrac{2}{3} + \dfrac{3}{5} + \dfrac{1}{2}.</math>

=== Généralisation aux  dimensions supérieures ===
Les techniques mises en place pour la résolution de l'équation ''ax + by = c ''peuvent être réinvesties pour la résolution des équations linéaires à plus d'inconnues. En particulier, elles permettent de résoudre l'équation diophantienne linéaire ''ax + by + cz = d''.

Comme dans le cas de la dimension 2, on peut remarquer que l'équation n'admet pas de solution si ''d ''n'est pas un multiple du PGCD de (''a'', ''b'', ''c''). Si ''d ''est multiple du PGCD, on peut diviser chacun des coefficients par le PGCD, on se ramène alors à une équation du même type dans lequel les coefficients devant ''x'', ''y ''et ''z ''sont premiers entre eux dans leur ensemble.

Dans l'équation ''ax  + by + cz = d'', où ''a'', ''b'', ''c ''sont premiers entre eux, on pose ''b''∧''c ''le PGCD de ''b'' et ''c ''et note ''b''{{ind|1}} et ''c''{{ind|1}} les entiers relatifs premiers entre eux tels que 
:<math>b=b_1.b\wedge c</math>
:<math>c=c_1.b\wedge c</math>
''by + cz ''étant toujours un multiple de ''b''∧''c'', l'équation est équivalente au système 
: <math>\begin{cases} (1) \qquad by+cz=(b\wedge c) Y\\(2) \qquad ax + (b \wedge c)Y=d.\end{cases}</math>
Les entiers ''a ''et ''b''∧''c'' étant premiers entre eux, la seconde équation admet des solutions et, pour tout ''Y'' la première équation admet des solutions. L'équation ''ax + by + cz = d ''admet donc toujours des solutions.

On appelle (''x''{{ind|1}}, ''y''{{ind|1}}, ''z''{{ind|1}}) l'une d'entre elles et (''y''{{ind|0}}, ''z''{{ind|0}}) une solution de l'équation ''b''{{ind|1}}''y ''+ ''c''{{ind|1}}''z ''= 1. On peut noter ''by''{{ind|1}} + ''cz''{{ind|1}} = (''b''∧''c'')''Y''{{ind|1}}.

Les solutions de l'équation (2) sont les couples :
{{retrait|<math>(x_1+(b \wedge c)k, Y_1-ak)</math>}}
où ''k ''est un entier relatif quelconque.

L'équation (1) s'écrit alors :
: <math>by + cz = by_1+ cz_1 - a(b \wedge c)k \Leftrightarrow b_1(y-y_1)+c_1(z - z_1)=-ak</math>
dont les solutions sont les couples :
: <math>(y_1-aky_0+c_1h, z_1-akz_0-b_1h)\,</math>
où ''h ''est un entier relatif quelconque.

Les solutions de l'équation de départ sont donc données par l'égalité matricielle suivante 
: <math>\begin{pmatrix}x\\y\\z\end{pmatrix}= \begin{pmatrix}x_1\\y_1\\z_1\end{pmatrix}+  \begin{pmatrix}b\wedge c&0\\-ay_0&c_1\\-az_0&-b_1\end{pmatrix} \begin{pmatrix}k\\h\end{pmatrix}</math>
où ''h ''et ''k ''sont des entiers relatifs quelconques.

== Recherche de solutions dans l'ensemble des entiers naturels ==
On ne considère ici que la résolution de l'équation ''ax + by = c'' où ''a'', ''b'', ''c'' sont des entiers naturels, ''a'' et ''b'' non nuls et premiers entre eux, les solutions étant cherchées parmi les entiers naturels.

Lucas attribue à Petri Paoli<ref>Voir aussi {{Dickson1}}, [https://books.google.fr/books?id=dO7C02z4LlcC&pg=PA64 vol. II, chap. 2, p. 64], qui fait référence à {{Ouvrage|lang=la|auteur=Petri Paoli|titre=Liburnensis Opuscula analytica|année=1780|page=114|url=https://books.google.fr/books?id=2_TmAAAAMAAJ&pg=PA114}}.</ref> et [[Ernesto Cesàro]] les deux résultats suivants<ref>{{Harvsp|Lucas|1891}}, § 264, « Théorèmes de Paoli et de Cesàro », {{p.|480-484}}.</ref> : 
{{Théorème |Théorème de Paoli|2=Si ''q ''est le quotient de la division de ''c'' par ''ab'' et ''r'' le reste, le nombre de couples d'entiers naturels solutions de l'équation ''ax + by = c'' est ''q'' ou ''q'' + 1 selon que l'équation ''ax + by = r'' admet aucune ou une solution.}} 

Si l'on s'intéresse alors plus précisément aux entiers ''r'' compris entre 0 et ''ab'' – 1 pour lesquels l'équation ''ax + by = r'' admet une solution, on peut démontrer que : 
* si ''r'' est multiple de ''a'' ou de ''b'', l'équation comporte une unique solution ;
* parmi les deux équations ''ax + by = r'' et ''ax + by = ab – r'' où ''r'' n'est multiple ni de ''a'' ni de ''b'', une exactement a une solution entière positive ;
*  si ''r'' est inférieur à ''a + b'' et n'est multiple ni de ''a'' ni de ''b'', l'équation ne comporte pas de solution.
On déduit de ces trois points que le plus grand entier ''r'' pour lequel l'équation ''ax + by = r'' n'a pas de solution positive (appelé le [[nombre de Frobenius]] de {''a'', ''b''}) est égal à ''ab – a – b''.

Des deux premiers points, on déduit le théorème suivant :
{{Théorème|Théorème de Cesàro<ref>[[Ernesto Cesàro]], ''Sur diverses questions d'arithmétique'', 1883.</ref>{{,}}<ref>Proposé en exercice dans {{article|lang=en|prénom1 =J. J.|nom1= Sylvester | année = 1884| titre = Question 7382| journal = Mathematical Questions from the Educational Times| volume = 41| page=21 |url=https://archive.org/stream/mathematicalque05unkngoog#page/n150}}, et cas particulier d'un théorème de {{Article|auteur=J. J. Sylvester|titre=Théorie des nombres|url=http://visualiseur.bnf.fr/CadresFenetre?O=NUMM-3007|page=367|année=1860|revue=[[Comptes rendus hebdomadaires des séances de l'Académie des sciences]]|vol=50|numéro=1}} cité dans {{Harvsp|Dickson|p=66}}.</ref>{{,}}<ref>Pour d'autres théorèmes de ce nom, voir {{Page h|Théorème de Cesàro}}.</ref>|2=Il existe exactement ''ab'' – ½ (''a'' – 1)(''b'' – 1) entiers naturels ''r'' compris entre 0 et ''ab'' – 1 pour lesquels  l'équation ''ax + by = r'' admet une solution.}}

Lorsqu'un entier ''r'' compris entre 1 et ''ab'' – 1 est donné, pour déterminer si l'équation ''ax + by = r'' admet une solution, il faut observer le système minimal. Le point de la droite ''ax + by = r''  le plus proche de l'origine est de coordonnées rationnelles positives.

L'unique solution entière positive (si elle existe) de l'équation ''ax + by = r'' correspond à  un des points de la droite à coordonnées entières les plus proches de ce point. Si (''x''{{ind|1}}, ''y''{{ind|1}}) est une solution dans l'ensemble des entiers relatifs de l'équation ''ax + by = r'', l'unique solution positive (si elle existe) de l'équation est donc à chercher dans les deux couples (''x''{{ind|1}} + ''bk''{{ind|1}}, ''y''{{ind|1}} – ''ak''{{ind|1}}) ou (''x''{{ind|1}} + ''bk''{{ind|2}}, ''y''{{ind|1}} – ''ak''{{ind|2}}) où ''k''{{ind|1}} et ''k''{{ind|2}} sont les deux entiers les plus proches de (''ay''{{ind|1}} – ''bx''{{ind|1}})/(''a''{{2}} + ''b''{{2}}). Si aucun de ces deux couples n'est dans ℕ{{2}}, l'équation n'admet pas de solution.

== Notes et références ==
{{Références}}

== Liens externes ==
* {{MathWorld|nom_url=DiophantineEquation|titre=Diophantine Equation}}

{{Portail|arithmétique}}

{{DEFAULTSORT:Equation diophantienne ax by c}}
[[Catégorie:Équation diophantienne|ax + by = c]]