Putnam 2018/B3

#1

Να βρεθούν όλοι οι θετικοί ακέραιοι $n < 10^{100}$ ώστε ταυτόχρονα ο

να διαιρεί τον 2^n

, ο

να διαιρεί τον 2^n-1

και ο

να διαιρεί τον 2^n - 2

.

Διονύσιος Αδαμόπουλος · #2

Υποθέτουμε για ευνόητους λόγους $n\geq 3$ .

Προφανώς πρέπει 2^m=n

, $m\geq 2$ , ώστε να ικανοποιείται η πρώτη συνθήκη. Κάθε τέτοιο

την ικανοποιεί.

Σύμφωνα με τη δεύτερη συνθήκη πρέπει $2^m-1|2^{2^m}-1$ .

Θα χρησιμοποιήσουμε το εξής λήμμα:

Αν 2^a-1|2^b-1

, τότε

και αντίστροφα.

Προφανώς $b\geq a$ και μπορούμε να θέσουμε b=ka+l

, όπου

θετικός ακέραιος και

μη αρνητικός ακέραιος μικρότερος του

.

Ισχύει ότι $2^a-1|2^{ak}-1$

Τότε είναι $2^a-1|2^b-1\Leftrightarrow 2^a-1|2^b-1-2^{ka}+1\Leftrightarrow 2^a-1|2^b-2^{ka}\Leftrightarrow 2^a-1|2^{ka}(2^l-1)\Leftrightarrow 2^a-1|2^l-1$ , που ισχύει αν και μόνο αν 2^l-1=0

ή $2^l-1\geq 2^a-1$ , που δεν ισχύει. Άρα 2^l=1

και

.

Πίσω στην άσκηση:

Σύμφωνα με το λήμμα πρέπει m|2^m

, άρα

, όπου $l\geq 1$ . Άρα $n=2^{2^l}$ , $l\geq 1$ . Κάθε τέτοιο

ικανοποιεί τις δύο πρώτες συνθήκες.

Σύμφωνα με την τρίτη συνθήκη πρέπει $2^{2^l}-2|2^{2^{2^l}}-2\Leftrightarrow 2^{2^l-1}-1|2^{2^{2^l}-1}-1$ .

Το λήμμα υποδεικνύει ότι $2^l-1|2^{2^l}-1$ , άρα από τα παραπάνω συμπεραίνουμε ότι l=2^r

, όπου $r\geq 0$ .

Συνοψίζοντας $n=2^{2^{2^r}}, r\geq 0$ . Κάθε τέτοιο

ικανοποιεί όλες τις συνθήκες.

Πρέπει ωστόσο $n<10^{100}$ .

Για r=3

, έχουμε $n=2^{256}<2^{258}<8^{86}<10^{100}$ .

Για r=4

ωστόσο έχουμε $2^{65536}>16^{16384}>10^{100}$ .

Συνεπώς τα μόνα

που ικανοποιούν είναι αυτά στα οποία $3\geq r\geq 0$ , δηλαδή n=4

,

, $n=2^{256}$ .

Putnam 2018/B3

Putnam 2018/B3

Re: Putnam 2018/B3

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