Μαθηματικά (Θετικής και Τεχνολογικής Κατεύθυνσης) - Βιβλίο Μαθητή
4.5 ΠΡΩΤΟΙ ΑΡΙΘΜΟΙ 4.7 ΙΣΟΫΠΟΛΟΙΠΟΙ ΑΡΙΘΜΟΙ Επιστροφή στην αρχική σελίδα του μαθήματος

4.6 Η ΓΡΑΜΜΙΚΗ ΔΙΟΦΑΝΤΙΚΗ ΕΞΙΣΩΣΗ

Εισαγωγή

Ένα από τα αρχαιότερα προβλήματα της Θεωρίας Αριθμών είναι η αναζήτηση των ακέραιων αριθμών που ικανοποιούν κάποιες δεδομένες σχέσεις. Με σύγχρονη ορολογία θα διατυπώσουμε το ίδιο πρόβλημα ως επίλυση, στο Ζ, πολυωνυμικών εξισώσεων με έναν ή περισσότερους αγνώστους και με ακέραιους συντελεστές. Ο κλάδος που ασχολείται με αυτό το ζήτημα ονομάζεται Διοφαντική Ανάλυση προς τιμήν του Διόφαντου (250 περίπου μ.Χ.), που ασχολήθηκε συστηματικά με τέτοιου είδους προβλήματα στο έργο του "Αριθμητικά".

Η αναζήτηση Πυθαγόρειων τριάδων (δηλαδή ακέραιων λύσεων της εξίσωσης x2+y2= z2 ) συγκαταλέγεται ανάμεσα στα κλασικά προβλήματα της Διοφαντικής Ανάλυσης. Υπάρχουν ενδείξεις ότι η λύση αυτού του προβλήματος (που δίνεται σήμερα από τους τύπους x=μ2 - v2, y=2μν z=μ2 + v2 ) ήταν γνωστή στους Βαβυλώνιους, αλλά η πλήρης θεωρητική διαπραγμάτευση του ζητήματος έγινε από τους Αρχαίους Έλληνες μαθηματικούς. Ο Ευκλείδης διατυπώνει το πρόβλημα στη μορφή

"Ευρείν δύο τετραγώνους αριθμούς, ώστε και το συγκείμενον εξ αυτών είναι τετράγωνον"

και δίνει τη γενική λύση στη γεωμετρική γλώσσα των "Στοιχείων" (Βιβλίο Χ, Λήμμα 1, Πρότ. 28).

Ο Διόφαντος διαπραγματεύεται το ίδιο πρόβλημα στα "Αριθμητικά"

"Τον επιταχθέντα τετράγωνον διελείν εις δύο τετραγώνους",

αλλά η λύση που δίνει βρίσκεται πιο κοντά στο σύγχρονο αλγεβρικό τρόπο σκέψης. Αυτό ακριβώς το πρόβλημα ήταν η αφορμή να ισχυριστεί ο P. Fermat (1601-1665) ότι η διοφαντική εξίσωση xv+yv= zv είναι αδύνατη, όταν ο ν είναι φυσικός μεγαλύτερος του 2, σημειώνοντας μάλιστα πάνω στο βιβλίο του Διόφαντου που μελετούσε: "έχω μια αληθινά θαυμάσια απόδειξη αυτής της πρότασης, αλλά το περιθώριο είναι πολύ στενό για να τη χωρέσει". Ο ισχυρισμός αυτός του Fermat αποδείχτηκε αληθής το 1994 από τον A. Wiles, αφού υπήρξε για 350 χρόνια ένα από τα διασημότερα άλυτα προβλήματα της Θεωρίας Αριθμών.

Η επίλυση διοφαντικών εξισώσεων βαθμού μεγαλύτερου του 2ου αποτελεί ένα ανοικτό μαθηματικό πρόβλημα, καθώς δεν έχουν βρεθεί γενικοί τύποι επίλυσης. Ο D. Hilbert διατύπωσε το 1900, ως ένα ζήτημα βασικής μαθηματικής έρευνας στη διάρκεια του 20ού αιώνα, την αναζήτηση ενός αλγόριθμου επίλυσης μιας διοφαντικής εξίσωσης με οποιοδήποτε αριθμό αγνώστων. Το 1970, ο Y. Matyasevich, σε ηλικία 22 χρόνων, απέδειξε ότι ένας τέτοιος αλγόριθμος δεν υπάρχει.

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

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

Μερικές διοφαντικές εξισώσεις μπορεί να έχουν πολλές λύσεις, όπως, για παράδειγμα, η 3x +6y = 18 , για την οποία μπορούμε να διαπιστώσουμε με αντικατάσταση ότι τα ζεύγη (4,1), ( -6,6), (10, -2) είναι ακέραιες λύσεις της.Υπάρχουν όμως διοφαντικές εξισώσεις που δεν έχουν καμιά λύση. Για παράδειγμα, η διοφαντική εξίσωση 2x + 6y = 13 δεν έχει καμιά λύση, αφού για όλες τις ακέραιες τιμές των το πρώτο μέλος της είναι άρτιος αριθμός, ενώ το δεύτερο μέλος της είναι περιττός αριθμός. Το θεώρημα που ακολουθεί δίνει απάντηση στο ερώτημα πότε μια διοφαντική εξίσωση έχει λύση, και αν έχει, πόσες είναι αυτές οι λύσεις.


ΘΕΩΡΗΜΑ 10

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

Εικόνα



ΑΠΟΔΕΙΞΗ

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

Εικόνα

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

Εικόνα

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

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

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

Εικόνα

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

Εικόνα

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

Εικόνα

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

Εικόνα

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

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

Εικόνα

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

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


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

Εικόνα

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

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

ΕΦΑΡΜΟΓΗ

Κάποιος οδηγός που χρειάζεται κέρματα, για να ρίξει στο μηχάνημα στάθμευσης (parking), ζητάει από τον περιπτερά να του ανταλλάξει ένα χιλιάρικο με κέρματα των 100 δραχμών και των 50 δραχμών. Με πόσους τρόπους μπορεί να γίνει η ανταλλαγή, αν ο οδηγός θέλει οπωσδήποτε και κατοστάρικα και πενηντάρικα;

ΛΥΣΗ

Αν η ανταλλαγή μπορεί να γίνει με x κατοστάρικα και y πενηντάρικα, τότε

Εικόνα

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

Εκφράζουμε γραμμικά το Μ.Κ.Δ. των 2 και 1 και έχουμε

Εικόνα

Πολλαπλασιάζουμε τα μέλη της (2) με 20 και έχουμε 2(20)+1(-20)=20 , που σημαίνει ότι(x0,y0)=(20, -20) . Επομένως, οι ακέραιες λύσεις της εξίσωσης (1) δίνονται από τους τύπους:

Εικόνα

Από τις λύσεις αυτές πρέπει να βρούμε εκείνες για τις οποίες ισχύει Εικόνα, δηλαδή πρέπει να βρούμε πού συναληθεύουν οι ανισώσεις

Εικόνα

Από την επίλυση του συστήματος των ανισώσεων προκύπτει ότι Εικόνα. Επομένως, t= -19, -18, -17, -16, -15, -14, -13, -12, -11 και οι αντίστοιχες τιμές των x και y φαίνονται στον παρακάτω πίνακα:

Εικόνα

ΑΣΚΗΣΕΙΣ

Α' ΟΜΑΔΑΣ
1.

Ποιες από τις παρακάτω εξισώσεις έχουν ακέραιες λύσεις;

Εικόνα
2.

Να βρείτε τις ακέραιες λύσεις των εξισώσεων

Εικόνα
3

Να βρείτε τις θετικές ακέραιες λύσεις των εξισώσεων
(i)111x + 78y= 300,    (ii)47x -31y =78.

4.

Να αποδείξετε ότι οι παρακάτω εξισώσεις δεν έχουν θετικές ακέραιες λύσεις:
(i) 3x + 5y = -15,    (ii) 111x + 78y = 50,   (iii) 5x + 7y = 5.

5.

Με ποιους τρόπους μπορούμε να αλλάξουμε ένα νόμισμα 10.000 δραχμών με νομίσματα των 1.000 και 500 δραχμών;


Β' ΟΜΑΔΑΣ
1.

Ένας καταστηματάρχης παραγγέλνει 19 μεγάλα και 3 μικρά πακέτα συσκευασίας με σαπούνια του ίδιου τύπου. Όταν όμως πήρε την παραγγελία, είδε έκπληκτος ότι η συσκευασία είχε καταστραφεί και τα σαπούνια ήταν σκόρπια στο κοντέινερ. Μπορείτε να τον βοηθήσετε να τα τακτοποιήσει με τον τρόπο που ήταν αρχικά συσκευασμένα, αν ξέρετε ότι το πλήθος των σαπουνιών είναι 224;

2.

Να γράψετε τον αριθμό 100 ως άθροισμα δύο προσθετέων, έτσι ώστε ο ένας να είναι πολλαπλάσιο του 7 και ο άλλος πολλαπλάσιο του 11. (Euler 1770).

3.

Να βρείτε την ελάχιστη δυνατή απόσταση ανάμεσα σε δύο σημεία, με ακέραιες συντεταγμένες, της ευθείας με εξίσωση αx + βy= γ , όταν Εικόνα.

4.

Έστω Εικόνα με (α,β)=1. Να αποδείξετε ότι
(i) Η εξίσωση αx + βy= αβ δεν έχει θετικές ακέραιες λύσεις.

(ii) Η εξίσωση αx + βy= 2αβ έχει μία μόνο θετική ακέραια λύση.

5.

Να βρείτε δύο κλάσματα με παρονομαστές 7 και 13 και με άθροισμα Εικόνα.