Επίλυση Γραμμικής Διοφαντικής Εξίσωσης

ΘΕΩΡΗΜΑ

Η γραμμική διοφαντική εξίσωση $αx +βy = γ$ έχει λύση, αν και μόνο αν ο μέγιστος κοινός διαιρέτης $δ$ των $α,β$ διαιρεί το $γ$.

Αν η εξίσωση αυτή έχει μια λύση $(x_0,y_0)$, τότε έχει άπειρες λύσεις $(x,y)$, που δίνονται από τους τύπους

ΑΠΟΔΕΙΞΗ

• Έστω ότι ,δηλαδή ότι . Γνωρίζουμε ότι για τον $δ=(α,β)$ υπάρχουν ακέραιοι $κ,λ$ τέτοιοι, ώστε

Πολλαπλασιάζοντας τα μέλη της (1) με $μ$ βρίσκουμε $μκα + μλβ= μδ$, δηλαδή

Άρα, το ζεύγος $(κμ,λμ)$ είναι μια λύση της εξίσωσης.

Αντιστρόφως, αν $(x_0,y_0)$ είναι μια λύση της διοφαντικής εξίσωσης, τότε θα ισχύει $αx_0+ βy_0 = γ $. Επειδή , συμπεραίνουμε ότι , δηλαδή .

• Έστω $(x_0,y_0)$ μια λύση της διοφαντικής εξίσωσης $αx +βy = γ$. Τότε θα ισχύει

Αν (x',y') είναι μια άλλη λύση της διοφαντικής εξίσωσης $αx +βy = γ$, τότε θα ισχύει

οπότε με αφαίρεση των δυο ισοτήτων κατά μέλη παίρνουμε

 

ή ισοδύναμα

Επειδή $δ=(α,β)$, οι αριθμοί είναι πρώτοι μεταξύ τους. Από την (2), με διαίρεση και των δύο μελών της με $δ$, έχουμε

Έτσι, ο $p$ διαιρεί το πρώτο μέλος της ισότητας, οπότε θα διαιρεί και το δεύτερο και επειδή είναι πρώτος προς το $σ$, θα διαιρεί τον ακέραιο $y_0 - y'$. Επομένως, θα υπάρχει ακέραιος $t$, τέτοιος, ώστε $yo - y' =pt$, δηλαδή , οπότε, λόγω της (2), θα είναι

.

Αντιστρόφως, για κάθε , ισχύει

που σημαίνει ότι και το ζεύγος είναι λύση της εξίσωσης.

Ώστε, αν μια διοφαντική εξίσωση έχει μια λύση $(x_0,y_0)$, τότε έχει άπειρες λύσεις της μορφής 

■

Στην περίπτωση που είναι $(α,δ)=1$, οι παραπάνω τύποι παίρνουν τη μορφή:

Η γεωμετρική ερμηνεία του παραπάνω θεωρήματος προκύπτει, αν λάβουμε υπόψη ότι κάθε εξίσωση της μορφής αx +βy = γ, με , παριστάνει στο επίπεδο μια ευθεία. Στην περίπτωση που, η ευθεία αυτή διέρχεται από άπειρα σημεία με ακέραιες συντεταγμένες, αν και μόνο αν ο , όπου $δ=(α,β)$.

Για παράδειγμα, η ευθεία $2x +3y = 1$ διέρχεται από άπειρο πλήθος σημείων με ακέραιες συντεταγμένες, ενώ η $6x +4y = 5$ δε διέρχεται από κανένα τέτοιο σημείο.
Από το σχολικό βιβλίο των Μαθηματικών κατεύθυνσης της Β΄ Λυκείου.