Équation diophantienne ax+by = c

Équation diophantienne ax+by = c

L'équation ax + by = c, où les coefficients a, b, et c, sont trois entiers relatifs et où les inconnues x et y sont entiers relatifs, est une des équations diophantiennes les plus simples à résoudre. Sa résolution s'appuie sur l'algorithme d'Euclide, le théorème de Bachet-Bézout et le théorème de Gauss. Lorsque c est égal au PGCD de a et b, on parle parfois d’identité de Bézout.

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 entiers naturels, l'équation possède un nombre fini de solutions. Le théorème de Paoli en donne le nombre à 1 près.

Sommaire

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 d'entiers relatifs (x0, y0) vérifiant : ax0 + by0 = 1.

  • L'algorithme d'Euclide étendu permet d'en exhiber une.
  • Une autre méthode consiste à utiliser le développement en fraction continue de a/b, l'avant dernière réduite fournit une solution du problème: Si \frac{h_{n-1}}{k_{n-1}} est l'avant dernière réduite de \frac ab alors kn − 1a − hn − 1b = ( − 1)n + 1.
  • Mais on peut aussi, si b n'est pas trop grand, chercher une solution par simple balayage en travaillant modulo b et en cherchant un entier x0 compris entre 1 et |b| - 1, vérifiant ax \equiv 1 \pmod b, l'entier y0 se calcule alors comme étant égal à \frac{1-ax_0}{b}.

Ensemble des solutions — Une solution particulière (x0, y0) étant connue, l'ensemble des solutions est formé des couples (x0 + bk, y0 - 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 :

\forall k \in \mathbb Z ,\, a(x_0+bk)+b(y_0-ak)=ax_0+by_0=1

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

(1):\qquad ax+by=1=ax_0+by_0

En regoupant autrement les termes, on obtient

(2):\qquad a(x-x_0)=-b(y-y_0)

L'entier b divise donc le produit a(x - x0). Comme a et b sont premiers entre eux, le lemme de Gauss permet de dire que b divise x - x0. Il existe donc un entier relatif k tel que x - x0 = kb. Soit encore

(3):\qquad x=x_0+kb

En remplaçant x - x0 par kb dans (2) on obtient :

(4) \qquad akb=-b(y-y_0)

Puis en simplifiant par -b

(5) \qquad y-y_0=-ak

Soit encore

(6) \qquad y=y_0-ak

Donc, si (x,y) est solution de (1) alors, il existe un entier relatif k tel que (x,y) = (x0+bk, y0 - 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 (x0, y0) vérifie ax0 + by0 = 1 alors ax0c + by0c = c, le couple (x0c, y0c) est alors solution de l'équation ax + by = c.

Un raisonnement analogue au précédent permet de trouver l'ensemble des solutions :

Ensemble des solutions — Une solution particulière (x1, y1) étant connue, l'ensemble des solutions est formé des couples (x1 + bk, y1 - ak) où k est un entier relatif quelconque.

Cas général

On appelle d le pgcd de a et de b.

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ù a et b sont des entiers relatifs, donc d doit diviser c

On suppose maintenant que d divise c, il existe alors 3 entiers relatifs a1, b1, et c1 tels que

a = da1
b = db1
c = dc1

avec a1et b1 premiers entre eux.

L'équation ax + by = c est alors équivalente à l'équation a1x + b1y = c1 dans laquelle a1 et b1 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 (x1, y1) étant connue, l'ensemble des solutions est formé des couples (x1+b1k, y1 - a1k) où k est un entier relatif quelconque.

D'où la propriété :

Si c est un multiple de d —  L'équation admet toujours des solutions. Une solution particulière (x1, y1) étant connue, l'ensemble des solutions est formé des couples \left(x_1+ \frac{bk}{d}; y_1 - \frac{ak}{d}\right) 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 x2 + y2 soit la plus petite possible.

Il s'agit de rendre minimal la valeur (x1 + b1k)2 + (y1 − a1k)2. Si on considère la fonction de la variable réelle t définie parf(t) = (x1 + b1t)2 + (y1 − a1t)2, l'étude de cette fonction du second degré montre que celle-ci possède un minimum en

t=\frac{a_1y_1-b_1x_1}{a_1^2+b_1^2}

Si t est entier, le couple solution est alors (x1 + b1t,y1 − a1t), sinon, l'entier qui rend f minimal 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 x2 + y2 est minimale sont le (ou les) couple(s) (x1 + b1k,y1 − a1k) où k est le (ou les) entier(s) k le(s) plus proche(s) de t=\frac{a_1y_1-b_1x_1}{a_1^2+b_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 a2 + b2. La solution du système minimal est alors \left(\frac{ac}{a^2+b^2},\frac{bc}{a^2+b^2}\right).

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 \frac{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 \equiv 1 \pmod b. L'ensemble des solutions permet de dire qu'il existe une unique classe x tel que ax=1 dans \mathbb Z/b\mathbb Z. 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 correspond 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.

Résolution graphique de l'équation 9x + 12y = 483
La droite d'équation 4x + 6y = 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 x2 + y2 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.

Les coordonnées de H fournissent la solution au système minimum de l'équation 2x +3y = 26
Les coordonnées de M1 et M2 fournissent les solutions au système minimum de l'équation 3x + 5y = 51
Les coordonnées de M fournissent la solution au système minimum de l'équation 2x + 3y = 31

Réduction d'une fraction en éléments simples

Décomposer une fraction irréductible \frac AB en éléments simples , c'est la décomposer en somme d'un entier relatif et de fractions de la forme \frac{r_{j,i}}{p_i^j} dans laquelle pi 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 pi dans la décomposition de B et rj,i est un entier compris entre 0 et pi − 1.

Lucas[1] prouve l'existence d'une telle décomposition. Il procède en plusieurs étapes.

Si B = pn, où p est un nombre premier, une simple écriture de A dans la base p permet d'aboutir. En effet

A = r_0+ r_1p+r_2p^2+\cdots + r_{n-1}p^{n-1}+ Ep^n

où les ri sont des entiers compris entre 0 et p - 1 et E est un entier relatif. D'où en divisant par B

\frac AB = \frac {r_0}{p^n}+\frac{r_1}{p^{n-1}}+ \cdots + \frac{r_{n-1}}{p} + E

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

\frac AB = \frac A{ab}= \frac{x}{b} +\frac{y}{a}

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 B=p_1^{n_1}\times p_2^{n_2} \times \cdots \times p_k^{n_k} alors on peut poser a = p_1^{n_1} et b = \frac Ba

\frac AB = \frac A{ab}= \frac{x}{b} +\frac{y}{a} = \frac{x}{b} + \frac{y}{p_1^{n_1}}

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 \frac{259}{90}

On décompose 90 en 9 × 10. On cherche deux entiers x et y tels que 9x + 10y = 259. On peut prendre x=1 et y=25.

(1) \qquad \frac{259}{90} =\frac{1}{10}+ \frac{25}{9}

On décompose 10 en 2 ×5. On cherche deux entiers x et y tels que 2x + 5y = 1. On peut prendre x = 3 et y = - 1.

(2) \qquad \dfrac{1}{10} = \dfrac{3}{5} - \dfrac{1}{2} = -1 + \dfrac{3}{5} + \dfrac{1}{2}

On écrit 25 en base 3

\qquad 25 = 1+3\times 8 = 1 + 3 \times(2 + 3 \times 2) = 1+2 \times 3 + 2 \times 3^2

Donc

(3) \qquad \frac{25}{9} = \frac{1}{3^2} + \dfrac{2}{3} + 2

Il suffit de remplacer dans (1) les résultats trouvés dans (2) et (3)

\frac{259}{90} = 1 + \frac{1}{3^2} + \dfrac{2}{3} + \dfrac{3}{5} + \dfrac{1}{2}

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 \scriptstyle b\wedge c le PGCD de b et c et note b1 et c1 les entiers relatifs, premiers entre eux tels que

b=b_1.b\wedge c
c=c_1.b\wedge c

by + cz étant toujours un multiple de \scriptstyle b\wedge c, l'équation est équivalente au système

\begin{cases} (1) \qquad by+cz=(b\wedge c) Y\\(2) \qquad ax + (b \wedge c)Y=d\end{cases}

Les entiers a et \scriptstyle b\wedge 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.

Si on appelle (x1,y1,z1) l'une d'entre elle et (y0,z0) une solution de l'équation b1y + c1z = 1. On peut noter by_1 + cz_1=(b\wedge c)Y_1.

Les solutions de l'équation (2) sont les couples :

(x_1+(b \wedge c)k, Y_1-ak)

où k est un entier relatif quelconque

L'équation (1) s'écrit alors :

by + cz = by_1+ cz_1 - a(b \wedge c)k \Leftrightarrow b_1(y-y_1)+c_1(z - z_1)=-ak

dont les solutions sont les couples :

(y_1-aky_0+c_1h, z_1-akz_0-b_1h)\,

où h est un entier relatif quelconque.

Les solutions de l'équation de départ sont donc données par l'égalité matricielle suivante

\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}

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 premiers entre eux, les solutions étant cherchées parmi les entiers naturels. Lucas attribue à Paoli et Cesàro les deux résultats suivants:

Théorème de Paoli — Si q est le quotient de la division de c par ab et r le reste, le nombre de solutions entières positives ou nulle de l'équation ax + by = c est de 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;
  • Si r est inférieur à a + b et n'est multiple ni de a ni de b, l'équation ne comporte pas de solution;
  • Parmi les équations ax + by = r et ax + by = ab - r où r n'est ni multiple de b ni multiple de a, une seule d'entre elles possède une solution entière positive.

On en déduit le nombre d'entiers r compris entre 0 et ab - 1 pour lesquels l'équation ax + by = r admet une solution.

Théorème de Cesàro[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

Lorsque 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 (x1,y1) 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 (x1 + bk1,y1 − ak1) ou (x1 + bk2,y1 − ak2) où k1 et k2 sont les deux entiers les plus proches de \frac{ay_1-bx_1}{a^2+b^2}. Si aucun de ces deux couples n'est dans \mathbb N^2 , l'équation n'admet pas de solution.

Notes et références

  1. ↑ Édouard Lucas, Théorie des nombres
  2. ↑ Ernesto Cesàro, Sur diverses questions d'arithmétique (1883)

Annexes

Bibliographie


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Équation diophantienne ax+by = c de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Equation diophantienne — Équation diophantienne Édition de 1670 des Arithmétiques de Diophante d Alexandrie. Une équation diophantienne, en mathématiques, est une équation dont les coefficients sont des nombres entiers et dont les solutions recherchées sont également… …   Wikipédia en Français

  • Équation diophantienne — Édition de 1670 des Arithmétiques de Diophante d Alexandrie. Une équation diophantienne, en mathématiques, est une équation dont les coefficients sont des nombres entiers et dont les solutions recherchées sont également entières. Le terme est… …   Wikipédia en Français

  • Equation — Équation (mathématiques)  Cet article concerne les équations mathématiques dans leur généralité. Pour une introduction au concept, voir Équation (mathématiques élémentaires).   …   Wikipédia en Français

  • Équation (mathématiques) —  Cet article concerne les équations mathématiques dans leur généralité. Pour une introduction au concept, voir Équation (mathématiques élémentaires).   …   Wikipédia en Français

  • Équation symétrique — Équation (mathématiques)  Cet article concerne les équations mathématiques dans leur généralité. Pour une introduction au concept, voir Équation (mathématiques élémentaires).   …   Wikipédia en Français

  • Équation vectorielle — Équation (mathématiques)  Cet article concerne les équations mathématiques dans leur généralité. Pour une introduction au concept, voir Équation (mathématiques élémentaires).   …   Wikipédia en Français

  • Diophantienne — Équation diophantienne Édition de 1670 des Arithmétiques de Diophante d Alexandrie. Une équation diophantienne, en mathématiques, est une équation dont les coefficients sont des nombres entiers et dont les solutions recherchées sont également… …   Wikipédia en Français

  • Equation de Pell — Équation de Pell Fermat Pierre de Fermat montre que l équation de Pell Fermat possède toujours une infinité de solutions si m est égal à un en valeur absolue. En mathématiques et plus précisément en arithmétique, l équation de Pell Fermat est une …   Wikipédia en Français

  • Équation de Pell — Fermat Pierre de Fermat montre que l équation de Pell Fermat possède toujours une infinité de solutions si m est égal à un en valeur absolue. En mathématiques et plus précisément en arithmétique, l équation de Pell Fermat est une équation… …   Wikipédia en Français

  • Équation de pell — Fermat Pierre de Fermat montre que l équation de Pell Fermat possède toujours une infinité de solutions si m est égal à un en valeur absolue. En mathématiques et plus précisément en arithmétique, l équation de Pell Fermat est une équation… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”