BURHAN.

Équation diophantienne ax + by = c : Cours de Mathématiques 2BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ

Équation diophantienne ax + by = c : notion du chapitre Arithmétique dans ℤ du programme de maths 2BAC SM, expliquée pas à pas, avec 3 exemples guidés. Pour les élèves de 2BAC SM A et SM B, option française (BIOF).

Notions du cours (11)

Apprendre avec Burhan

Équation ax + by = c

Étape 1 sur 3

Existe-t-il des solutions

Devine : Un total impossible ?

On cherche des entiers relatifs xx et yy tels que 6x+15y=506x + 15y = 50. Quel raisonnement est juste ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Aucune solution, car 6x+15y6x + 15y est toujours un multiple de 33, et 5050 ne l'est pas.

Juste.

33 divise 66 et 1515, donc 33 divise 6x+15y6x + 15y (propriétés de la divisibilité, point 2). Or 3∤503 \nmid 50.

Choix B :Il y a des solutions, car 6∧15≠06 \wedge 15 \neq 0.

Faux.

Le PGCD n'est jamais nul ici. Ce qui compte, c'est de savoir s'il divise 5050.

Choix C :Aucune solution, car 5050 n'est multiple ni de 66 ni de 1515.

Faux.

Ce raisonnement ne vaut rien : 2121 n'est multiple ni de 66 ni de 1515, et pourtant 6×1+15×1=216 \times 1 + 15 \times 1 = 21.

Besoin d'aide ? Indice 1

Cherche un entier qui divise à coup sûr 6x+15y6x + 15y, quels que soient xx et yy.

Encore bloqué ? Indice 2

Calcule 6∧156 \wedge 15.

Voir la correction complète

6∧15=36 \wedge 15 = 3. Pour tous entiers xx et yy, 33 divise 6x+15y6x + 15y. Comme 50=3×16+250 = 3 \times 16 + 2, 3∤503 \nmid 50 : l'équation n'a aucune solution. L'énoncé suivant dit que ce test du PGCD suffit toujours.

ThéorèmeExistence de solutions de ax + by = c

Soient aa et bb deux entiers relatifs non nuls, cc un entier relatif et d=a∧bd = a \wedge b. L'équation ax+by=cax + by = c, d'inconnue (x,y)∈Z2(x, y) \in \mathbb{Z}^2, admet au moins une solution si et seulement si d∣cd \mid c.

Démonstration

Sens direct. Si (x,y)(x, y) est une solution, alors d∣ad \mid a et d∣bd \mid b, donc d∣ax+by=cd \mid ax + by = c (« Propriétés de la divisibilité », point 2).

Réciproque. Si d∣cd \mid c, on écrit c=dkc = dk avec k∈Zk \in \mathbb{Z}. L'identité de Bézout donne uu et vv tels que au+bv=dau + bv = d. En multipliant par kk : a(uk)+b(vk)=ca(uk) + b(vk) = c. Le couple (uk,vk)(uk, vk) est une solution.

ExempleDeux équations voisines

On a 15∧21=315 \wedge 21 = 3.

  • 15x+21y=915x + 21y = 9 : 3∣93 \mid 9, donc il y a des solutions, d'après l'existence de solutions de ax+by=cax + by = c. Par exemple, 15×2+21×(−1)=915 \times 2 + 21 \times (-1) = 9.
  • 15x+21y=1015x + 21y = 10 : 3∤103 \nmid 10, donc il n'y en a aucune.

Les coefficients sont les mêmes : seul le second membre décide.

AttentionBézout ne fabrique pas n'importe quel second membre

Pour 10x+15y=810x + 15y = 8, on lit parfois : « par Bézout, il existe uu et vv, donc il y a une solution ». C'est faux. Bézout donne 10u+15v=510u + 15v = 5, le PGCD, et non 88. Ici 5∤85 \nmid 8 : aucune solution. Calcule toujours d=a∧bd = a \wedge b et teste d∣cd \mid c avant de chercher une solution.

Continuer : Toutes les solutions →

Étape 2 sur 3

Toutes les solutions

Pour 5x+8y=35x + 8y = 3, le couple (−1,1)(-1, 1) convient : −5+8=3-5 + 8 = 3. Ajoute 88 à xx et retire 55 à yy : (7,−4)(7, -4) convient aussi, car 35−32=335 - 32 = 3. On peut recommencer sans fin. Pourquoi est-ce vrai, et pourquoi n'y a-t-il pas d'autres solutions ? Le théorème suivant répond, grâce à Gauss.

ThéorèmeSolutions de ax + by = c

Soient aa et bb deux entiers relatifs non nuls et premiers entre eux, cc un entier relatif, et (x0,y0)(x_0, y_0) une solution de l'équation ax+by=cax + by = c dans Z2\mathbb{Z}^2. Les solutions de cette équation dans Z2\mathbb{Z}^2 sont exactement les couples (x0+bk, y0−ak),k∈Z.(x_0 + bk, \ y_0 - ak), \quad k \in \mathbb{Z}.

Démonstration

Étape 1 (ces couples sont des solutions). Pour tout k∈Zk \in \mathbb{Z} : a(x0+bk)+b(y0−ak)=ax0+by0=ca(x_0 + bk) + b(y_0 - ak) = ax_0 + by_0 = c.

Étape 2 (il n'y en a pas d'autres). Soit (x,y)(x, y) une solution. Par différence avec ax0+by0=cax_0 + by_0 = c : a(x−x0)=b(y0−y)a(x - x_0) = b(y_0 - y). Donc b∣a(x−x0)b \mid a(x - x_0). Comme b∧a=1b \wedge a = 1, le théorème de Gauss donne b∣x−x0b \mid x - x_0 : il existe k∈Zk \in \mathbb{Z} tel que x=x0+bkx = x_0 + bk.

Étape 3. En reportant : abk=b(y0−y)abk = b(y_0 - y). Comme b≠0b \neq 0, on simplifie par bb : y0−y=aky_0 - y = ak, soit y=y0−aky = y_0 - ak.

À retenirCe qu'il faut retenir de la preuve

Deux solutions d'une même équation se soustraient : a(x−x0)=b(y0−y)a(x - x_0) = b(y_0 - y). Le théorème de Gauss donne alors b∣x−x0b \mid x - x_0. Retiens ce réflexe : soustraire, puis Gauss.

Vérifie : L'hypothèse qui fait tout

À l'étape 2 de la preuve, quelle hypothèse permet d'appliquer le théorème de Gauss à b∣a(x−x0)b \mid a(x - x_0) ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :b≠0b \neq 0

Faux.

Elle sert à l'étape 3, pour simplifier abk=b(y0−y)abk = b(y_0 - y) par bb.

Choix B :a∧b=1a \wedge b = 1

Juste.

Gauss demande que bb soit premier avec le facteur aa : c'est exactement l'hypothèse a∧b=1a \wedge b = 1.

Choix C :c≠0c \neq 0

Faux.

L'énoncé ne suppose rien sur cc : la preuve marche aussi pour c=0c = 0.

Besoin d'aide ? Indice 1

Rappelle-toi Gauss : si a∣bca \mid bc et a∧b=1a \wedge b = 1, alors a∣ca \mid c.

Encore bloqué ? Indice 2

Ici, le diviseur est bb et le facteur à « enlever » est aa.

Voir la correction complète

On a b∣a(x−x0)b \mid a(x - x_0). Le théorème de Gauss en déduit b∣x−x0b \mid x - x_0 à condition que b∧a=1b \wedge a = 1 : c'est l'hypothèse « aa et bb premiers entre eux » du théorème. L'hypothèse b≠0b \neq 0 sert ensuite, à l'étape 3.

ExempleContre-exemple : sans diviser par d

Pour 18x+30y=2418x + 30y = 24, on a 18∧30=6≠118 \wedge 30 = 6 \neq 1. Le couple (3,−1)(3, -1) est solution : 54−30=2454 - 30 = 24. Appliquer tel quel le théorème des solutions donnerait les couples (3+30k, −1−18k)(3 + 30k, \ -1 - 18k). On oublierait (−2,2)(-2, 2), qui est solution : −36+60=24-36 + 60 = 24. Il faut d'abord diviser par 66 : 3x+5y=43x + 5y = 4, dont les solutions sont (3+5k, −1−3k)(3 + 5k, \ -1 - 3k), k∈Zk \in \mathbb{Z}.

← Étape précédenteContinuer : La méthode complète →

Étape 3 sur 3

La méthode complète

Méthoderésoudre ax + by = c

Résoudre dans Z2\mathbb{Z}^2 l'équation 33x+24y=1533x + 24y = 15.

  1. PGCD. 33=1×24+933 = 1 \times 24 + 9, 24=2×9+624 = 2 \times 9 + 6, 9=1×6+39 = 1 \times 6 + 3, 6=2×36 = 2 \times 3. Donc 33∧24=333 \wedge 24 = 3, et 3∣153 \mid 15 : il y a des solutions.
  2. Simplifier. On divise par 33 : 11x+8y=511x + 8y = 5, avec 11∧8=111 \wedge 8 = 1.
  3. Solution particulière. La remontée d'Euclide donne un couple de Bézout : 11×3+8×(−4)=111 \times 3 + 8 \times (-4) = 1. En multipliant par 55 : 11×15+8×(−20)=511 \times 15 + 8 \times (-20) = 5. Ici, une solution plus simple se voit : 11×(−1)+8×2=511 \times (-1) + 8 \times 2 = 5. On prend (x0,y0)=(−1,2)(x_0, y_0) = (-1, 2).
  4. Conclure avec a=11a = 11 et b=8b = 8 : les solutions sont les couples (−1+8k, 2−11k)(-1 + 8k, \ 2 - 11k), k∈Zk \in \mathbb{Z}.

Rédaction attendue. « 11∧8=111 \wedge 8 = 1 et (−1,2)(-1, 2) est solution. D'après le théorème des solutions de ax+by=cax + by = c, les solutions sont les couples (−1+8k, 2−11k)(-1 + 8k, \ 2 - 11k). »

À toi : À toi de résoudre

Résous dans Z2\mathbb{Z}^2 l'équation 9x+4y=29x + 4y = 2.

Besoin d'aide ? Indice 1

Calcule 9∧49 \wedge 4 : faut-il simplifier ?

Encore bloqué ? Indice 2

Pars d'un couple de Bézout : 9×1+4×(−2)=19 \times 1 + 4 \times (-2) = 1, puis multiplie par 22.

Encore bloqué ? Indice 3

Applique le théorème des solutions avec a=9a = 9 et b=4b = 4 : attention à l'ordre des coefficients.

Voir la solution complète

9∧4=19 \wedge 4 = 1 et 1∣21 \mid 2 : il y a des solutions, sans simplification. On a 9×1+4×(−2)=19 \times 1 + 4 \times (-2) = 1 ; en multipliant par 22, 9×2+4×(−4)=29 \times 2 + 4 \times (-4) = 2, donc (x0,y0)=(2,−4)(x_0, y_0) = (2, -4). D'après le théorème des solutions de ax+by=cax + by = c, les solutions sont les couples (2+4k, −4−9k)(2 + 4k, \ -4 - 9k), k∈Zk \in \mathbb{Z}. Contrôle avec k=1k = 1 : 9×6+4×(−13)=54−52=29 \times 6 + 4 \times (-13) = 54 - 52 = 2.

ExempleCoin examen

La partie « il n'y a pas d'autres solutions » se rédige ainsi, pour 11x+8y=511x + 8y = 5. Points indicatifs, barème BURHAN.

  • Soit (x,y)(x, y) une solution. Par différence avec 11×(−1)+8×2=511 \times (-1) + 8 \times 2 = 5 : 11(x+1)=8(2−y)11(x + 1) = 8(2 - y). 0,25 pt
  • Donc 8∣11(x+1)8 \mid 11(x + 1). Or 8∧11=18 \wedge 11 = 1 : d'après le théorème de Gauss, 8∣x+18 \mid x + 1. 0,5 pt
  • On écrit x=−1+8kx = -1 + 8k, k∈Zk \in \mathbb{Z}. Alors 88k=8(2−y)88k = 8(2 - y), d'où y=2−11ky = 2 - 11k. 0,5 pt
  • Réciproquement, ces couples conviennent : 11(−1+8k)+8(2−11k)=511(-1 + 8k) + 8(2 - 11k) = 5. 0,25 pt

← Étape précédenteFin de la notion

S'entraîner sur cette notion

Sources du cours

  • Référentiel BURHAN du chapitre « Arithmétique dans ℤ » (2bac · sciences-mathematiques · mathematiques)