Μέγιστος κοινός διαιρέτης
Συντονιστής: nkatsipis
Μέγιστος κοινός διαιρέτης
Καλησπέρα φίλοι μου.
Προν λίγες ώρες γύρισα απο εξετάσεις θεωρίας αριθμών και τα πηγα πολύ άσχημα. Η πρώτη άσκηση έλεγε να βρούμε τον μέγιστο κοινό διαιρέτη ανάμεσα στο (2^345)+6 και του 15. Ακομη προσπαθώ σπίτι αλλα δεν βρίσκω τον τροπο λύσης. Μπορεί να βοηθήσει κάποιος;
Προν λίγες ώρες γύρισα απο εξετάσεις θεωρίας αριθμών και τα πηγα πολύ άσχημα. Η πρώτη άσκηση έλεγε να βρούμε τον μέγιστο κοινό διαιρέτη ανάμεσα στο (2^345)+6 και του 15. Ακομη προσπαθώ σπίτι αλλα δεν βρίσκω τον τροπο λύσης. Μπορεί να βοηθήσει κάποιος;
Λέξεις Κλειδιά:
- grigkost
- Διαχειριστής
- Δημοσιεύσεις: 3053
- Εγγραφή: Πέμ Δεκ 18, 2008 12:54 pm
- Τοποθεσία: Ιωάννινα
- Επικοινωνία:
Re: Μέγιστος κοινός διαιρέτης
Μια λύση -με την προϋπόθεση ότι (2^345) σημαίνει :
.
Από το θεώρημα Euler: .
Άρα .
Έτσι .
Τελικά .
.
Από το θεώρημα Euler: .
Άρα .
Έτσι .
Τελικά .
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3341
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Μέγιστος κοινός διαιρέτης
Αλλιώς: αρκεί να δείξουμε ότι ο δεν διαιρείται ούτε δια του ούτε δια του . Το πρώτο είναι προφανές καθώς ο διαρεί τον αλλά όχι τον . Για το δεύτερο παρατηρούμε ότι ο έχει ως πιθανά τελευταία ψηφία τα άρα ο τα αντίστοιχα, συνεπώς μπορεί να διαιρείται από τον μόνον αν ο έχει ως τελευταίο ψηφίο το : αυτό δεν συμβαίνει επειδή οι δυνάμεις του που έχουν ως τελευταίο ψηφίο το είναι οι
[Κάπως διαφορετικά για την μη διαιρετότητα δια : , κλπ]
[Κάπως διαφορετικά για την μη διαιρετότητα δια : , κλπ]
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Re: Μέγιστος κοινός διαιρέτης
Ευχαριστώ, και γω προσπάθησα να το λύσω με το θεώρημα igcd(a,b) = igcd(b,r) όπου r το υπόλοιπο a/b απο τον αλγόριθμο του ευκλειδη αλλά δεν πήγε ποτε το μυαλό μου στην συνάρτηση του euler. Αστα να πανε
Re: Μέγιστος κοινός διαιρέτης
μου ήρθε και σήμερα το πρωί μια φλασιά, ακόμη πιο απλή λύση.
Με τους κανονες του mod: έχουμε 2^4=16, 16 mod 15 = 1, οπότε απο τον κανόνα αβ mod g = ((α mod g)(β mod g)) mod g
έχουμε 2^8 mod 15 = 1, 2^12 mod 15 = 1 κ.λ.π οπότε
λόγο ότι είναι πολλάπλασιο του 4. Οπότε ισουτε igcd(2+6,15)= igcd(8,15) = 1
Με τους κανονες του mod: έχουμε 2^4=16, 16 mod 15 = 1, οπότε απο τον κανόνα αβ mod g = ((α mod g)(β mod g)) mod g
έχουμε 2^8 mod 15 = 1, 2^12 mod 15 = 1 κ.λ.π οπότε
λόγο ότι είναι πολλάπλασιο του 4. Οπότε ισουτε igcd(2+6,15)= igcd(8,15) = 1
Re: Μέγιστος κοινός διαιρέτης
Αυτή τη λύση περίμενε να δει ο εξεταστής σου και είναι ο ενδεδειγμένος τρόπος λύσης.xmaze έγραψε: ↑Δευ Σεπ 26, 2022 11:51 amμου ήρθε και σήμερα το πρωί μια φλασιά, ακόμη πιο απλή λύση.
Με τους κανονες του mod: έχουμε 2^4=16, 16 mod 15 = 1, οπότε απο τον κανόνα αβ mod g = ((α mod g)(β mod g)) mod g
έχουμε 2^8 mod 15 = 1, 2^12 mod 15 = 1 κ.λ.π οπότε
λόγο ότι είναι πολλάπλασιο του 4. Οπότε ισουτε igcd(2+6,15)= igcd(8,15) = 1
Παρατηρείς δηλαδη ότι και μετά κάνεις μια ευκλείδεια διαίρεση με το .
Ασκήσεις αυτού του πνεύματος είναι από τις πιο κλασικές ασκήσεις στοιχειώδους αριθμοθεωρίας.
Κωνσταντίνος Σμπώκος
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 5 επισκέπτες