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

Στην θεωρία αριθμών, μία **γραμμική διοφαντική εξίσωση** είναι μία διοφαντική εξίσωση της μορφής
:ax + by = c
όπου a, b, c είναι δοσμένοι ακέραιοι αριθμοί και  x, y είναι οι άγνωστοι ακέραιοι αριθμοί τους οποίους καλούμαστε να βρούμε.

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

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

## Επίλυση

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

### Παράδειγμα 1ο
Θεωρούμε την γραμμική διοφαντική εξίσωση 
:35x + 8y = 1. 
Χρησιμοποιώντας τον επεκταμένο αλγόριθμο του Ευκλείδη βρίσκουμε ότι το ΜΚΔ των 23 και 8, είναι 1 καθώς
:
\begin{align}
35 & = 8 \cdot 4 + 3 \\
8 & = 3 \cdot 2 + 2 \\
3 & = 2 \cdot 1 + 1 \\
2 & = 1 \cdot 2 + 0.
\end{align}

Με τον επεκταμένο αλγόριθμο, βρίσκουμε μία λύση (x_0, y_0)
:
\begin{align}
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{align}

Επομένως, μπορούμε να θέσουμε x_0 = 3 και y_0 = -13, και οι γενικές λύσεις θα είναι 
:x = 3 + 8 \cdot t και y = -13 - 35 \cdot t, για κάθε t \in \Z.

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

Θεωρούμε την γραμμική διοφαντική εξίσωση του πρώτου παραδείγματος, αλλά με διαφορετικό συντελεστή 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 \Z.

### Παράδειγμα 3ο
Η γραμμική διοφαντική εξίσωση 
:24x + 16y = 62
δεν έχει λύσεις καθώς \operatorname{MK\Delta}(24, 16) = 8 δεν διαιρεί το 62.

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

Θεωρούμε την γραμμική διοφαντική εξίσωση 
:175x + 40y = 15.
Ο μέγιστος κοινός διαιρέτης των 175 και 40 είναι 
:
\begin{align}
\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{align}

Διαιρώντας και τα δύο μέλη με 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 \Z, 
:ax \equiv b \pmod{m}. 
Δηλαδή ψάχνουμε τα x για τα οποία υπάρχει κάποιος ακέραιος y ώστε
:ax -b = m \cdot y 
ή ισοδύναμα
:ax + (-m)y = b, 
που είναι μία γραμμική διοφαντική εξίσωση.

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

## Παραπομπές


Κατηγορία:Θεωρία αριθμών