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

#1

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

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

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

Ορέστης Λιγνός · #2

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

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

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

Έστω ότι δεν υπάρχει τέτοιος φυσικός

, δηλαδή έχω $b \nmid a^n-1$ για κάθε

.

Οι άπειροι όμως αριθμοί της μορφής a^n-1

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

, συγκεκριμένα τα $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$ για κάθε

.

Άρα, καταλήξαμε σε αντίφαση, οπότε η αρχική υπόθεση ήταν λανθασμένη, συνεπώς υπάρχει φυσικός

ώστε $b \mid a^n-1$ ό.έ.δ.

#3

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

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #4

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

Τσιαλας Νικολαος · #5

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

Νομίζω πως έχετε απόλυτο δίκιο!

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

#6

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

#7

Αν $b=\displaystyle\prod_{i=1}^m p_i^{k_i}$ η ανάλυση του

σε πρώτους παράγοντες, τότε επιλέγουμε $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

.

Αλέξανδρος

#8

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

#9

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

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

Έστω για ευκολία ότι ο ένας αριθμός είναι ο a=10

(η γενίκευση, μετά). Γράφουμε τον $\dfrac {1}{b}$ , όπου (b,10)=1

, στο δεκαδικό του ανάπτυγμα, οπότε υπάρχει ένα αρχικό κομμάτι

μήκους

(μπορεί να είναι m=0

) και ένα περιοδικό κομμάτι

μήκους

τέτοια ώστε $\displaystyle{\dfrac {1}{b}=0,c\bar {p}}$ . Προσοχή, το ανάπτυγμα είναι σίγουρα άπειρο περιοδικό - δεν τελειώνει - ακριβώς γιατί ο

δεν περιέχει

ή

ως πρώτο παράγοντα.

Προσθέτουμε τώρα το περιοδικό κομμάτι ως γεωμετρική πρόοδο με λόγο $\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}$

Όμως το

διαιρεί το δεξί μέλος και επειδή είναι πρώτο προς το

, και άρα προς το 10^m

, έπεται ότι $\displaystyle{b|10^n-1}$ . Τελειώσαμε! Αυτό είναι το αποδεικτέο.

Γενικά τώρα. Κάνουμε ακριβώς την ίδια δουλειά αλλά αντί να γράψουμε το

στο δεκαδικό του ανάπτυγμα, το γράφουμε ως προς βάση το

. Ρουά ματ.

#10

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

Σωστά Δημήτρη! Έκανα τα εύκολα δύσκολα και δεν πρόσεξα αυτό που είπε ο Σταύρος παραπάνω! Ευχαριστώ!

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

Αλέξανδρος

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

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

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

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

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

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

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

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

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

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

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

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