Γραμμικές Διοφαντικές Εξισώσεις: Θεωρία, Παραδείγματα και Πλήρης Μέθοδος Επίλυσης

Οι Διοφαντικές εξισώσεις είναι εξισώσεις των οποίων ζητούμε λύσεις μόνο σε ακέραιους αριθμούς. Πήραν το όνομά τους από τον Διόφαντο της Αλεξάνδρειας (3ος αιώνας μ.Χ.), ο οποίος μελέτησε συστηματικά τρόπους εύρεσης τέτοιων λύσεων.

Η πιο βασική μορφή τέτοιων εξισώσεων είναι η γραμμική Διοφαντική εξίσωση δύο μεταβλητών:

$$ax + by = c,$$

όπου $a, b, c \in \mathbb{Z}$. Στόχος είναι η εύρεση όλων των ακέραιων ζευγών $(x, y)$ που ικανοποιούν την εξίσωση.

---

1. Πότε έχει λύσεις η εξίσωση;

Η εξίσωση:

$$ax + by = c$$

έχει ακέραιες λύσεις αν και μόνο αν ο μέγιστος κοινός διαιρέτης των $a$ και $b$ διαιρεί το $c$. Δηλαδή:

$$\gcd(a, b) \mid c.$$

Εάν αυτό δεν ισχύει, τότε δεν υπάρχει καμία ακέραια λύση.

Παράδειγμα (καμία λύση):

$$12345678x + 98765432y = 123456789.$$

Η αριστερή πλευρά είναι πάντοτε ζυγός αριθμός, ενώ η δεξιά πλευρά είναι περιττός. Άρα δεν υπάρχουν ακέραιες λύσεις.

---

2. Εάν υπάρχει λύση - μείωση με τον Ευκλείδειο Αλγόριθμο

Αν $d = \gcd(a, b)$ και $d \mid c$, τότε γράφουμε:

$$x = x_0 + \frac{b}{d} t,\quad y = y_0 - \frac{a}{d} t, \quad t \in \mathbb{Z}.$$

Άρα υπάρχουν άπειρες λύσεις, εκφρασμένες παραμετρικά.

Για την εύρεση μιας συγκεκριμένης λύσης, χρησιμοποιούμε τον Ευκλείδειο Αλγόριθμο προς τα εμπρός και έπειτα «αναστροφή» των βημάτων (back-substitution).

---

3. Παράδειγμα 1 – Ο Αφηρημένος Ταμίας

Ο Shane ζήτησε ένα ποσό $x$ δολάρια και $y$ σεντς. Ο ταμίας αντέστρεψε τους αριθμούς και του έδωσε $100y + x$ σεντς αντί $100x + y$. Μετά την αγορά παγωτού αξίας $2.55, έμεινε με τετραπλάσιο ποσό από αυτό που ζήτησε.

Άρα:

$$4(100x + y) + 255 = 100y + x.$$

Με άλγεβρα:

$$133x - 32y = -85.$$

Εφαρμόζοντας τον Ευκλείδειο Αλγόριθμο και βρίσκοντας την παραμετρική λύση προκύπτει:

$$x = 15,\quad y = 65.$$

Ο Shane ζήτησε $15.65.

---

4. Παράδειγμα 2 – Οι 5 Ναύτες και οι Καρύδες

Το πρόβλημα καταλήγει σε επαναλαμβανόμενη σχέση της μορφής:

$$n \equiv 1 \pmod 5 \quad \text{και} \quad \frac{n-1}{5} \equiv 1 \pmod 5 \quad \text{και ούτω καθεξής.}$$

Η ελάχιστη λύση είναι:

$$n = 3121 \text{ καρύδες.}$$

Με μία καρύδα για τη μαϊμού στο τέλος:

$$n = 3121 + 1 = 3122.$$

5. Σημαντικές Εφαρμογές στη Σύγχρονη Επιστήμη

Πεδίο	Παράδειγμα	Διοφαντική Εξίσωση
Κρυπτογραφία RSA	Υπολογισμός του ιδιωτικού κλειδιού	$ex + \phi(n)y = 1$
Χημεία	Ισοζυγισμός αντιδράσεων	Γραμμικά συστήματα ακεραίων
Αλγόριθμοι δικτύων	Peer-to-peer routing	Εξισώσεις ακεραίων βαρών

Οι εξισώσεις αυτές εμφανίζονται λοιπόν σε:

• υπολογιστική ασφάλεια,

• φυσικές επιστήμες,

• θεωρία αριθμών,

• συνδυαστική βελτιστοποίηση.

---

6. Συνοπτική Διαδικασία Επίλυσης

1. Υπολογίζουμε $\gcd(a, b)$.

2. Ελέγχουμε αν $\gcd(a, b)\mid c$.

3. Αν ναι, εφαρμόζουμε τον Ευκλείδειο Αλγόριθμο για μια λύση.

4. Χρησιμοποιούμε την παραμετρική μορφή για όλες τις λύσεις.

5. Αν χρειάζεται, επιλέγουμε κατάλληλες τιμές του $t$ βάσει επιπλέον περιορισμών.