Σελίδα 1 από 1

Μία δύσκολη Διαιρετότητα

Δημοσιεύτηκε: Τετ Ιαν 11, 2017 4:16 pm
από ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ
Να βρείτε όλους τους θετικούς ακεραίους a,b μεγαλύτερους του 1 ώστε:

b^a | a^b-1

Re: Μία δύσκολη Διαιρετότητα

Δημοσιεύτηκε: Πέμ Ιαν 12, 2017 2:31 pm
από thrassos
Καλημέρα Χάρη,
Μία προσπάθεια με L.T.E.
Αρχικά, υποθέτουμε ότι \exists p, όπου p ο μικρότερος πρώτος, τέτοιος ώστε ώστε p|b και έστω t \in \mathbb{N} , ο μικρότερος φυσικός για τον οποίο ισχύει p|a^t-1.
Άρα έχουμε t|b και από μικρό θεώρημα του Fermat
t|p-1 άρα αν t\neq 1 τότε θα υπάρχει ένας πρώτος παράγοντας του t όπου θα διαιρεί τον b, άτοπο.Άρα
πρέπει t=1.
Τώρα, έστω p περιττός πρώτος και άρα από την δοθείσα έχουμε au_{p}(b)\leq u_{p}(a-1) + u_{p}(b) (*) και άρα από εδώ έπεται πως (a-1)u_{p}(b)\leq u_p(a-1) άτοπο γιατί τότε a-1 \leq u_p(a-1).Άρα p=2.
Τώρα, από την τελευταία διαπίστωση έχουμε ότι b=2k και a περιττός.
Επίσης, η (*) γράφεται( αφου p=2)
au_2(b) \leq u_2(a-1) + u_2(a+1) +u_2(b) -1 \Leftrightarrow (a-1)u_2(b) +1 \leq u_2(a-1) + u_2(a+1)

Ακόμη, παρατηρούμε ότι LHS \geq a και άρα a \leq u_2(a-1) + u_2(a+1) (***) το οποίο ισχύει μόνο αν a=3, καθώς αν a>3 τότε a>u_2(a-1) + u_2(a+1).Άρα αφού ισχύει η ισότητα στην (***) τότε θα πρέπει να ισχύει και στην (**) και άρα a=3 και u_2(b)=1.
Επομένως, αφού b=2k και u_2(b)=1 έπεται ότι k είναι περιττός.Επιπλέον , η δοθείσα γράφεται
(2k)^3|3^{2k}-1 και όπως και στην αρχή θα υποθέσουμε ότι \exists q , όπου q ο μικρότερος πρώτος, τέτοιος ώστε q|k ,και άρα q περιττός, και n ο μικρότερος φυσικός για τον οποίο ισχύει q|3^n-1.Από τις τελευταίες έπεται ότι n|2k και n|q-1 και άρα πρέπει n=2 γιατί αλλιώς ο k θα έχει μικρότερο πρώτο παράγοντα από το q.
Επομένως , q|3^2 -1 , πράγμα αδύνατο αν k\neq1 , και άρα συμπεραίνουμε ότι b=2.Άρα μοναδική λύση η (a,b)=(3,2)

Φιλικά,
Θράσος

Re: Μία δύσκολη Διαιρετότητα

Δημοσιεύτηκε: Πέμ Ιαν 12, 2017 3:11 pm
από Διονύσιος Αδαμόπουλος
Μια προσπάθεια, αν και δεν είμαι πολύ σίγουρος...

Έστω p ένας πρώτος που διαιρεί το b, με p>2. Έστω p^k||b, με k\geq 1. Ακόμη έστω p^l||a-1. Από το θεώρημα Lift the exponent προκύπτει ότι p^{k+l}||a^b-1

Ακόμη ισχύει ότι p^{ak}||b^a. Συνεπώς για να ισχύει ότι b^a|a^b-1, πρέπει να ισχύει ότι p^{ak}|p^{k+l}\Leftrightarrow ak\leq k+l\Leftrightarrow k(a-1)\leq l.

Όμως, αφού p^l||a-1 και a>1, ισχύει ότι l<a-1. Άρα πρέπει να ισχύει ότι k(a-1)< a-1\Leftrightarrow k<1 άτοπο.

Άρα πρέπει να ισχύει ότι b=2^n, με n\geq 1.

Η σχέση μας γίνεται 2^{na}|a^{2^n}-1\Leftrightarrow 2^{na}|(a^{2^{n-1}}+1)(a^{2^{n-1}}-1)

Συνεπώς, ισχύει ότι a^{2^{n-1}}+1=2^e και a^{2^{n-1}}-1=2^f με e+f \geq na. Όμως 2^e-2^f=2, άρα e=2 και f=1, άρα 3 \geq na. Επειδή a>1 ισχύει ότι n=1, άρα b=2 και a=3 ή a=2. Δεκτή μόνο η περίπτωση a=3.

Μοναδική λύση λοιπόν είναι η (a, b)=(3, 2)

Edit: Βλέπω ότι με πρόλαβε ο Θράσος... με παρόμοιο σκεπτικό!

Re: Μία δύσκολη Διαιρετότητα

Δημοσιεύτηκε: Πέμ Ιαν 12, 2017 3:32 pm
από ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ
:coolspeak: :coolspeak: