Γραμμική διοφαντική εξίσωση

Στην θεωρία αριθμών, μία γραμμική διοφαντική εξίσωση είναι μία διοφαντική εξίσωση της μορφής

$ax+by=c$

όπου $a,b,c$ είναι δοσμένοι ακέραιοι αριθμοί και $x,y$ είναι οι άγνωστοι ακέραιοι αριθμοί τους οποίους καλούμαστε να βρούμε.

Λέγεται διοφαντική, καθώς οι λύσεις τις πρέπει να είναι ακέραιοι αριθμοί (αντί για πραγματικοί), και γραμμική γιατί το είναι γραμμική συνάρτηση των δύο αγνώστων της (π.χ. δεν υπάρχουν όροι της μορφής $x^{2}$ ή $xy$).

Η εξίσωση μπορεί (i) να μην έχει καμία λύση ή (ii) να έχει αριθμήσιμο πλήθος από λύσεις.

Επίλυση

Θεώρημα —  Έστω οι ακέραιοι $a,b,c\in \mathbb {Z}$ με $a,b\neq 0$ και $d=\operatorname {MK\Delta } (a,b)$. Η εξίσωση $ax+by=c$

• Δεν έχει λύσεις, αν $d\not \mid c$.
• Διαφορετικά έχει τις εξής λύσεις

$x=x_{0}+{\frac {b}{d}}\cdot t$ και $y=y_{0}-{\frac {a}{d}}\cdot t$ για κάθε ακέραιο $t\in \mathbb {Z}$,

όπου $(x_{0},y_{0})$ μία αρχική λύση που μπορεί να βρεθεί με την χρήση του επεκταμένου αλγορίθμου του Ευκλείδη.

Απόδειξη  

Έστω $d=\operatorname {MK\Delta } (a,b)$, τότε για ακεραίους $a',b'\in \mathbb {Z}$ με $\operatorname {MK\Delta } (a',b')=1$

$a=da'$ και $b=db'$

και

$da'x+db'y=c$.

Επομένως, $d\mid c$, δηλαδή αν $d\mid c$ τότε δεν υπάρχουν λύσεις. Έστω $c=dc'$, τότε η αρχική εξίσωση είναι ισοδύναμη με

$a'x+b'y=c'$.

Από τον επεκταμένο αλγόριθμο του Ευκλείδη, μπορούμε να βρούμε ακεραίους $x_{0}'$ και $y_{0}'$ τέτοιους ώστε

$a'x_{0}'+b'y_{0}'=1$.

Πολλαπλασιάζοντας επί $c'$ έχουμε ότι $x_{0}=cx_{0}'$ και $y_{0}=cy_{0}'$ είναι λύση της έξίσωσης

$a'x_{0}+b'y_{0}=c'$,

και επομένως και της αρχικής

$ax_{0}+by_{0}=c$.

Τώρα έστω ότι έχουμε μία ακόμα λύση $(x,y)$, δηλαδή

$ax+by=c$.

Παίρνοντας τη διαφορά από τις τελευταίες σχέσεις έχουμε ότι

$a(x-x_{0})=-b(y-y_{0})$

ή ισοδύναμα

$a'(x-x_{0})=-b'(y-y_{0})$.

Αφού $\operatorname {MK\Delta } (a',b')=1$, έπεται ότι

$a'\mid y-y_{0}$, δηλαδή $y-y_{0}=a'\cdot t_{2}$

και $b'\mid x-x_{0}$, δηλαδή $x-x_{0}=b'\cdot t_{1}$ άρα

$a'b't_{2}=-b'a't_{1}\Rightarrow t_{1}=-t_{2}$.

Θέτοντας $t=t_{1}=-t_{2}$ λαμβάνουμε ότι

$x=x_{0}+{\frac {b}{d}}\cdot t$ και $y=y_{0}-{\frac {a}{d}}\cdot t$.

Βάζοντας αυτή τη λύση στην αρχική εξίσωση, επιβεβαιώνουμε ότι την επαληθεύει για κάθε τιμή της παραμέτρου $t\in \mathbb {Z}$,

$a\cdot \left(x_{0}+{\frac {b}{d}}\cdot t\right)+b\cdot \left(y_{0}-{\frac {a}{d}}\cdot t\right)=ax_{0}+by_{0}=c$.

Παραδείγματα

Λύσεις γραμμικής διοφαντικής εξίσωσης $35x+8y=1$.

Παράδειγμα 1ο

Θεωρούμε την γραμμική διοφαντική εξίσωση

$35x+8y=1$.

Χρησιμοποιώντας τον επεκταμένο αλγόριθμο του Ευκλείδη βρίσκουμε ότι το ΜΚΔ των $23$ και $8$, είναι $1$ καθώς

${\begin{aligned}35&=8\cdot 4+3\\8&=3\cdot 2+2\\3&=2\cdot 1+1\\2&=1\cdot 2+0.\end{aligned}}$

Με τον επεκταμένο αλγόριθμο, βρίσκουμε μία λύση $(x_{0},y_{0})$

${\begin{aligned}1&=3-2\cdot 1\\&=3-(8-3\cdot 2)\cdot 1\\&=-8+3\cdot 3\\&=-8+(35-8\cdot 4)\cdot 3\\&=35\cdot 3+8\cdot (-13).\end{aligned}}$

Επομένως, μπορούμε να θέσουμε $x_{0}=3$ και $y_{0}=-13$, και οι γενικές λύσεις θα είναι

$x=3+8\cdot t$ και $y=-13-35\cdot t$, για κάθε $t\in \mathbb {Z}$.

Παράδειγμα 2ο

Λύσεις γραμμικής διοφαντικής εξίσωσης 35x + 8y = 3.

Θεωρούμε την γραμμική διοφαντική εξίσωση του πρώτου παραδείγματος, αλλά με διαφορετικό συντελεστή $c=3$.

$35x+8y=3$.

Η λύση $x_{0}'=3$ και $y_{0}'=-13$ που είδαμε προηγουμένως μας δίνει

$35x_{0}'+8y_{0}'=1$.

Πολλαπλασιάζοντας επί $c=3$ έχουμε ότι $x_{0}=9$ και $y_{0}=-39$ είναι λύση της εξίσωσης, καθώς

$35x_{0}+8y_{0}=3$.

Άρα οι γενικές λύσεις είναι

$x=9+8\cdot t$ και $y=-39-35\cdot t$, για κάθε $t\in \mathbb {Z}$.

Παράδειγμα 3ο

Η γραμμική διοφαντική εξίσωση

$24x+16y=62$

δεν έχει λύσεις καθώς $\operatorname {MK\Delta } (24,16)=8$ δεν διαιρεί το $62$.

Παράδειγμα 4ο

Θεωρούμε την γραμμική διοφαντική εξίσωση

$175x+40y=15$.

Ο μέγιστος κοινός διαιρέτης των $175$ και $40$ είναι

${\begin{aligned}\operatorname {MK\Delta } (175,40)&=\operatorname {MK\Delta } (40,15)&({\text{καθώς }}175=40\cdot 4+15)\\&=\operatorname {MK\Delta } (15,10)&({\text{καθώς }}40=15\cdot 2+10)\\&=\operatorname {MK\Delta } (10,1)&({\text{καθώς }}15=10\cdot 1+5)\\&=5&({\text{καθώς }}10=5\cdot 2)\end{aligned}}$

Διαιρώντας και τα δύο μέλη με $3$ λαμβάνουμε την ισοδύναμη διοφαντική εξίσωση

$35x+8y=3$.

Επομένως, οι λύσεις δίνονται όπως στο 2ο παράδειγμα.

Εφαρμογές

Θετικές λύσεις γραμμικής διοφαντικής εξίσωσης

Σε κάποιες περιπτώσεις θέλουμε επιπλέον περιορισμούς στις λύσεις που θα πάρουμε, όπως για παράδειγμα να είναι θετικοί αριθμοί (όπως στο παράδειγμα με τα ρέστα). Για να βρεθούν οι ζητούμενες λύσεις, βάζουμε επιπλέον τους περιορισμούς

$x_{0}+{\frac {b}{d}}\cdot t\geq 0$ και $y_{0}-{\frac {a}{d}}\cdot t\geq 0$,

και λύνουμε ως προς την παράμετρο $t$

$-x_{0}\cdot {\frac {d}{b}}\leq t$ και $t\leq y_{0}\cdot {\frac {d}{a}}$.

Οι ακέραιοι σε αυτό το εύρος μας δίνουν τις ζητούμενες λύσεις.

Λύση της γραμμικής ισοτιμίας

Έστω ότι θέλουμε να λύσουμε την γραμμική ισοτιμία για δοσμένα $a,b,m\in \mathbb {Z}$,

$ax\equiv b{\pmod {m}}$.

Δηλαδή ψάχνουμε τα $x$ για τα οποία υπάρχει κάποιος ακέραιος $y$ ώστε

$ax-b=m\cdot y$

ή ισοδύναμα

$ax+(-m)y=b$,

που είναι μία γραμμική διοφαντική εξίσωση.

Δείτε επίσης

• Αλγόριθμος του Ευκλείδη
• Μέγιστος κοινός διαιρέτης