Μέγιστος κοινός διαιρέτης

xmaze · #1

Καλησπέρα φίλοι μου.

Προν λίγες ώρες γύρισα απο εξετάσεις θεωρίας αριθμών και τα πηγα πολύ άσχημα. Η πρώτη άσκηση έλεγε να βρούμε τον μέγιστο κοινό διαιρέτη ανάμεσα στο (2^345)+6 και του 15. Ακομη προσπαθώ σπίτι αλλα δεν βρίσκω τον τροπο λύσης. Μπορεί να βοηθήσει κάποιος;

#2

Μια λύση -με την προϋπόθεση ότι (2^345) σημαίνει $2^{345}$ :

$(2^{345}+6,15)=\big({2(2^{344}+3),15}\big)=(2^{344}+3,15)$ .
Από το θεώρημα Euler: $(2,15)=1\;\wedge\; \phi(15)=8\;\Rightarrow\;2^{8}\equiv1\pmod{15}$ .
Άρα $2^{344}\equiv2^{8\cdot43}\equiv(2^{8})^{43}\equiv1\pmod{15}$ .
Έτσι $2^{344}=1+15k\;\Rightarrow\;2^{344}+3=1+3+15k=15k+4\,,\; k\in\mathbb{Z}$ .
Τελικά $(2^{345}+6,15)=(15k+4,15)=(4,15)=1$ .

#3

Αλλιώς: αρκεί να δείξουμε ότι ο $2^{345}+6$ δεν διαιρείται ούτε δια του

ούτε δια του

. Το πρώτο είναι προφανές καθώς ο

διαρεί τον

αλλά όχι τον $2^{345}$ . Για το δεύτερο παρατηρούμε ότι ο $2^{345}$ έχει ως πιθανά τελευταία ψηφία τα 2, 4, 8, 6,

άρα ο $2^{345}+6$ τα 8, 0, 4, 2,

αντίστοιχα, συνεπώς μπορεί να διαιρείται από τον

μόνον αν ο $2^{345}$ έχει ως τελευταίο ψηφίο το

: αυτό δεν συμβαίνει επειδή οι δυνάμεις του

που έχουν ως τελευταίο ψηφίο το

είναι οι $2^2, 2^6, 2^{10}, ... , 2^{342}, 2^{346}, ...$

[Κάπως διαφορετικά για την μη διαιρετότητα δια

: $2^{345}=2\cdot(2^{344})=2\cdot(4^{172})=2\cdot(5-1)^{172}=2mod5$ , κλπ]

xmaze · #4

grigkost έγραψε: ↑
Σάβ Σεπ 24, 2022 8:48 am
Μια λύση -με την προϋπόθεση ότι (2^345) σημαίνει $2^{345}$ :

$(2^{345}+6,15)=\big({2(2^{344}+3),15}\big)=(2^{344}+3,15)$ .
Από το θεώρημα Euler: $(2,15)=1\;\wedge\; \phi(15)=8\;\Rightarrow\;2^{8}\equiv1\pmod{15}$ .
Άρα $2^{344}\equiv2^{8\cdot43}\equiv(2^{8})^{43}\equiv1\pmod{15}$ .
Έτσι $2^{344}=1+15k\;\Rightarrow\;2^{344}+3=1+3+15k=15k+4\,,\; k\in\mathbb{Z}$ .
Τελικά $(2^{345}+6,15)=(15k+4,15)=(4,15)=1$ .

Ευχαριστώ, και γω προσπάθησα να το λύσω με το θεώρημα igcd(a,b) = igcd(b,r) όπου r το υπόλοιπο a/b απο τον αλγόριθμο του ευκλειδη αλλά δεν πήγε ποτε το μυαλό μου στην συνάρτηση του euler. Αστα να πανε

xmaze · #5

μου ήρθε και σήμερα το πρωί μια φλασιά, ακόμη πιο απλή λύση.
Με τους κανονες του 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 κ.λ.π οπότε $2^{345} = 2^{4\cdot 86+1} = 2^{4\cdot 86}\cdot 2$
$2^{4\cdot 86} mod 15 = 1$ λόγο ότι είναι πολλάπλασιο του 4. Οπότε ισουτε igcd(2+6,15)= igcd(8,15) = 1

stranger · #6

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 κ.λ.π οπότε $2^{345} = 2^{4\cdot 86+1} = 2^{4\cdot 86}\cdot 2$
$2^{4\cdot 86} mod 15 = 1$ λόγο ότι είναι πολλάπλασιο του 4. Οπότε ισουτε igcd(2+6,15)= igcd(8,15) = 1

Αυτή τη λύση περίμενε να δει ο εξεταστής σου και είναι ο ενδεδειγμένος τρόπος λύσης.
Παρατηρείς δηλαδη ότι $2^4 \equiv 1 (mod 15)$ και μετά κάνεις μια ευκλείδεια διαίρεση με το

.
Ασκήσεις αυτού του πνεύματος είναι από τις πιο κλασικές ασκήσεις στοιχειώδους αριθμοθεωρίας.

Μέγιστος κοινός διαιρέτης

Μέγιστος κοινός διαιρέτης

Re: Μέγιστος κοινός διαιρέτης

Re: Μέγιστος κοινός διαιρέτης

Re: Μέγιστος κοινός διαιρέτης

Re: Μέγιστος κοινός διαιρέτης

Re: Μέγιστος κοινός διαιρέτης

Μέλη σε σύνδεση