Διαιρέτης από τον Lewis Carroll

Συντονιστές: silouan, rek2

Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11474
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Διαιρέτης από τον Lewis Carroll

#1

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Πέμ Νοέμ 07, 2019 11:28 am

Είδα την ακόλουθη άσκηση στο Pillow Problems του Charles Dodgson, γνωστότερου με το ψευδώνυμο Lewis Carroll με το οποίο έγραψε το βιβλίο του Αλίκη στην χώρα των Θαυμάτων.

Αν a,b πρώτοι προς αλλήλους φυσικοί αριθμοί, να αποδειχθεί ότι υπάρχει φυσικός αριθμός n τέτοιος ώστε ο b να διαιρεί τον a^n-1.

Αναρτώ το θέμα γιατί βρήκα πολύ κομψή την λύση του ίδιου του Dodgson. Η δική μου λύση, την οποία έκανα πριν διαβάσω την δική του, είναι σε άλλο μήκος κύματος (απλή αλλά στάνταρ, θα έλεγα). Επειδή μου άρεσε η λύση που είδα, θέλω να την μοιραστώ μαζί σας. Αναμένω λοιπόν τουλάχιστον δύο διαφορετικές αντιμετωπίσεις στο πρόβλημα.



Λέξεις Κλειδιά:
Άβαταρ μέλους
Ορέστης Λιγνός
Δημοσιεύσεις: 1471
Εγγραφή: Κυρ Μάιος 08, 2016 7:19 pm
Τοποθεσία: Χαλάνδρι Αττικής

Re: Διαιρέτης από τον Lewis Carroll

#2

Μη αναγνωσμένη δημοσίευση από Ορέστης Λιγνός » Πέμ Νοέμ 07, 2019 11:55 am

Mihalis_Lambrou έγραψε:
Πέμ Νοέμ 07, 2019 11:28 am
Είδα την ακόλουθη άσκηση στο Pillow Problems του Charles Dodgson, γνωστότερου με το ψευδώνυμο Lewis Carroll με το οποίο έγραψε το βιβλίο του Αλίκη στην χώρα των Θαυμάτων.

Αν a,b πρώτοι προς αλλήλους φυσικοί αριθμοί, να αποδειχθεί ότι υπάρχει φυσικός αριθμός n τέτοιος ώστε ο b να διαιρεί τον a^n-1.

Αναρτώ το θέμα γιατί βρήκα πολύ κομψή την λύση του ίδιου του Dodgson. Η δική μου λύση, την οποία έκανα πριν διαβάσω την δική του, είναι σε άλλο μήκος κύματος (απλή αλλά στάνταρ, θα έλεγα). Επειδή μου άρεσε η λύση που είδα, θέλω να την μοιραστώ μαζί σας. Αναμένω λοιπόν τουλάχιστον δύο διαφορετικές αντιμετωπίσεις στο πρόβλημα.
Έστω ότι δεν υπάρχει τέτοιος φυσικός n, δηλαδή έχω b \nmid a^n-1 για κάθε n.

Οι άπειροι όμως αριθμοί της μορφής a^n-1 μπορούν να αφήνουν πεπερασμένο αριθμό υπολοίπων στη διαίρεση με το b, συγκεκριμένα τα 1,2 \ldots, b-1.

Οπότε, υπάρχουν k>\ell φυσικοί, ώστε a^k-1 \equiv x \pmod b και a^\ell -1 \equiv x \pmod b.

Άρα, (a^k-1)-(a^\ell-1) \equiv x-x \equiv 0 \pmod b, άρα b \mid a^k-a^\ell=a^\ell(a^{k-\ell}-1), και αφού (a,b)=(a^\ell,b)=1, έχω b \mid a^{k-\ell}-1, άτοπο από την αρχική μας υπόθεση ότι b \nmid a^n-1 για κάθε n.

Άρα, καταλήξαμε σε αντίφαση, οπότε η αρχική υπόθεση ήταν λανθασμένη, συνεπώς υπάρχει φυσικός n ώστε b \mid a^n-1 ό.έ.δ.


Κερδίζουμε ό,τι τολμούμε !
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11474
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Διαιρέτης από τον Lewis Carroll

#3

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Πέμ Νοέμ 07, 2019 12:00 pm

:10sta10:

Ορέστη, αυτή είναι και η δική μου λύση. Του Dodgson είναι τελείως διαφορετική, και μου τράβηξε το ενδιαφέρον.


ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2619
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

Re: Διαιρέτης από τον Lewis Carroll

#4

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Πέμ Νοέμ 07, 2019 1:12 pm

Δεν είναι άμεση εφαρμογή του θεωρήματος Euler;


Τσιαλας Νικολαος
Δημοσιεύσεις: 365
Εγγραφή: Σάβ Ιαν 17, 2015 1:04 pm

Re: Διαιρέτης από τον Lewis Carroll

#5

Μη αναγνωσμένη δημοσίευση από Τσιαλας Νικολαος » Πέμ Νοέμ 07, 2019 1:50 pm

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε:
Πέμ Νοέμ 07, 2019 1:12 pm
Δεν είναι άμεση εφαρμογή του θεωρήματος Euler;
Νομίζω πως έχετε απόλυτο δίκιο!

Υ.γ: η λύση του Ορέστη είναι υπέροχη!!


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11474
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Διαιρέτης από τον Lewis Carroll

#6

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Πέμ Νοέμ 07, 2019 2:40 pm

Η λύση του Dodgson είναι στοιχειωδέστατη και μικρή. Απλά μία ωραία ιδέα.


Άβαταρ μέλους
cretanman
Διαχειριστής
Δημοσιεύσεις: 3922
Εγγραφή: Πέμ Δεκ 18, 2008 12:35 pm
Τοποθεσία: Ηράκλειο Κρήτης
Επικοινωνία:

Re: Διαιρέτης από τον Lewis Carroll

#7

Μη αναγνωσμένη δημοσίευση από cretanman » Πέμ Νοέμ 07, 2019 8:39 pm

Αν b=\displaystyle\prod_{i=1}^m p_i^{k_i} η ανάλυση του b σε πρώτους παράγοντες, τότε επιλέγουμε n=\displaystyle\prod_{i=1}^m\varphi\left(p_i^{k_i}\right), όπου \varphi η συνάρτηση του Euler και έχουμε το ζητούμενο καθώς a^{\varphi\left(p_1^{k_1}\right)}\equiv 1\pmod{p_1^{k_1}} κι έτσι a^n\equiv 1\pmod{p_1^{k_1}}. Όμοια a^n\equiv 1\pmod{p_i^{k_i}} για κάθε i=2,\ldots, m κι έτσι b|a^n-1.

Αλέξανδρος


Αλέξανδρος Συγκελάκης
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8238
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Διαιρέτης από τον Lewis Carroll

#8

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Νοέμ 08, 2019 11:21 am

Αλέξανδρε, αν επιτρέπεται να χρησιμοποιήσουμε τη συνάρτηση του Euler τότε μπορούμε να πάμε και απευθείας στο a^{\varphi(b)} \equiv 1 \bmod b. (Όπως είπε και ο Σταύρος πιο πάνω.) Μάλλον όμως κάτι άλλο έχει υπόψη του ο Μιχάλης.


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11474
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Διαιρέτης από τον Lewis Carroll

#9

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Παρ Νοέμ 08, 2019 5:13 pm

Γράφω την λύση του Dodgson, που μου άρεσε.

Την κάνω σε δύο βήματα (όπως ο ίδιος) για λόγους διδακτικούς, αν και δεν είναι απαραίτητα και τα δύο αλλά μπορούμε να πάμε απευθείας στο δεύτερο τμήμα της λύσης του. Επίσης θα είμαι λίγο αναλυτικός επειδή μας διαβάζουν μαθητές.

Έστω για ευκολία ότι ο ένας αριθμός είναι ο a=10 (η γενίκευση, μετά). Γράφουμε τον \dfrac {1}{b}, όπου (b,10)=1, στο δεκαδικό του ανάπτυγμα, οπότε υπάρχει ένα αρχικό κομμάτι c μήκους m (μπορεί να είναι m=0) και ένα περιοδικό κομμάτι p μήκους n τέτοια ώστε \displaystyle{\dfrac {1}{b}=0,c\bar {p}}. Προσοχή, το ανάπτυγμα είναι σίγουρα άπειρο περιοδικό - δεν τελειώνει - ακριβώς γιατί ο b δεν περιέχει 2 ή 5 ως πρώτο παράγοντα.

Προσθέτουμε τώρα το περιοδικό κομμάτι ως γεωμετρική πρόοδο με λόγο \dfrac {1}{10^n}. Θα βρούμε

\displaystyle{\dfrac {1}{b}= \dfrac {c}{10^m} + \dfrac {p}{10^{m}} \left ( \dfrac {1}{10^n } + \dfrac {1}{10^{n+ 1}}+... \right )= \dfrac {c}{10^m} + \dfrac {p}{10^{m}}\cdot  \dfrac {10^n}{10^n -1}  }

και άρα, διώχνοντας τους παρονομαστές, θα βρούμε

\displaystyle{10^m(10^n -1)= (akeraios)\times  b}

Όμως το b διαιρεί το δεξί μέλος και επειδή είναι πρώτο προς το 10, και άρα προς το 10^m, έπεται ότι \displaystyle{b|10^n-1}. Τελειώσαμε! Αυτό είναι το αποδεικτέο.

Γενικά τώρα. Κάνουμε ακριβώς την ίδια δουλειά αλλά αντί να γράψουμε το b στο δεκαδικό του ανάπτυγμα, το γράφουμε ως προς βάση το a. Ρουά ματ.


Άβαταρ μέλους
cretanman
Διαχειριστής
Δημοσιεύσεις: 3922
Εγγραφή: Πέμ Δεκ 18, 2008 12:35 pm
Τοποθεσία: Ηράκλειο Κρήτης
Επικοινωνία:

Re: Διαιρέτης από τον Lewis Carroll

#10

Μη αναγνωσμένη δημοσίευση από cretanman » Σάβ Νοέμ 09, 2019 8:01 am

Demetres έγραψε:
Παρ Νοέμ 08, 2019 11:21 am
Αλέξανδρε, αν επιτρέπεται να χρησιμοποιήσουμε τη συνάρτηση του Euler τότε μπορούμε να πάμε και απευθείας στο a^{\varphi(b)} \equiv 1 \bmod b. (Όπως είπε και ο Σταύρος πιο πάνω.) Μάλλον όμως κάτι άλλο έχει υπόψη του ο Μιχάλης.
Σωστά Δημήτρη! Έκανα τα εύκολα δύσκολα και δεν πρόσεξα αυτό που είπε ο Σταύρος παραπάνω! Ευχαριστώ!

κ. Μιχάλη πολύ όμορφη η λύση που παραθέσατε παραπάνω!

Αλέξανδρος


Αλέξανδρος Συγκελάκης
Απάντηση

Επιστροφή σε “Γενικά - Επίπεδο Θαλή/Ευκλείδη (Seniors)”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης