Ελάχιστος πρώτος - JBMO Shortlist 2008

#1

Για τους λάτρεις της θεωρίας αριθμών:

Να προσδιορίσετε τον ελάχιστο πρώτο αριθμό p>3

για τον οποίο δεν υπάρχει φυσικός αριθμός n>0

ώστε να ισχύει $2^n+3^n\equiv 0 \pmod{p}$ .

Το παραπάνω πρόβλημα το είχα κατασκευάσει για την Βαλκανική Ολυμπιάδα Νέων του 2008, το οποίο μπήκε στη Shortlist των προβλημάτων αλλά δεν επιλέχθηκε τελικά για το διαγωνισμό. Μια και έχει περάσει αρκετός καιρός από τότε το παραθέτω προς λύση!

Αλέξανδρος

#2

cretanman έγραψε:Για τους λάτρεις της θεωρίας αριθμών:

Να προσδιορίσετε τον ελάχιστο πρώτο αριθμό για τον οποίο δεν υπάρχει φυσικός αριθμός ώστε να ισχύει $2^n+3^n\equiv 0 \pmod{p}$ .

Το παραπάνω πρόβλημα το είχα κατασκευάσει για την Βαλκανική Ολυμπιάδα Νέων του 2008, το οποίο μπήκε στη Shortlist των προβλημάτων αλλά δεν επιλέχθηκε τελικά για το διαγωνισμό. Μια και έχει περάσει αρκετός καιρός από τότε το παραθέτω προς λύση!

Αλέξανδρος

Αν το

μπορεί να πάρει την τιμή 0 - το 0 είναι φυσικός;-, τότε προφανώς, p=3

.

Αν το n>0

, τότε πάλι προφανώς, p=2

.

Μήπως υπάρχει τυπογραφικό στη διατύπωση ή είναι τόσο απλό;

'Η, απλά μου διαφεύγει κάτι;

Φιλικά,

Αχιλλέας

#3

Το ίδιο θα ρωτούσα και εγώ Αχιλλέα. Μου φαίνεται αρκετά εύκολη για Junior BMO.

#4

Με συγχωρείτε έκανα λάθος στο copy-paste μια και το αντέγραψα από αρχείο word όπου το mathtype στο οποίο ήταν γραμμένη η άσκηση δεν μεταφέρει εδώ το μαθηματικό κείμενο το οποίο έγραψα με το χέρι. Εννοώ p>3

και

θετικό φυσικό. Το διορθώνω αμέσως και στην εκφώνηση.

Αλέξανδρος

#5

Είναι

.

Πράγματι, τα υπόλοιπα της διαίρεσης με το 19 των αριθμών 12^k

, για $k=1,2,\dots,6$ είναι 12, 11, 18, 7, 8

, και,

, αντίστοιχα.

Τα υπόλοιπα της διαίρεσης με το 19 των αριθμών 18^k=(19-1)^k

, για $k=1,2,\dots,6$ είναι 18, 1, 18, 1, 18

, και,

, αντίστοιχα.

Συνεπώς, οι αριθμοί 12^n+18^n

δε διαιρούνται με το 19 για κανένα

.

Αφού 12^n+18^n=6^n(2^n+3^n)

και $\colorbox{red}{\boxed{\gcd(6^n,19)=1}}$ για κάθε

, οι αριθμοί 2^n+3^n

δε διαιρούνται με το 19 για κανένα

.

Για να αποδείξουμε το ελάχιστο του 19 με την παραπάνω ιδιότητα αρκεί να παρατηρήσουμε ότι

5/ (2^1+3^1)

,

,

και

(Σημείωση: πιο σύντομα μπορεί κανείς να δείξει ότι οι αριθμοί 26^n+39^n=13^n(2^n+3^n)

δε διαιρούνται με το 19 για κανένα

.

Πράγματι, τα υπόλοιπα της διαίρεσης με το 19 των αριθμών 26^k

, για

είναι

, και,

, αντίστοιχα.

Τα υπόλοιπα της διαίρεσης με το 19 των αριθμών $39^k=(2\cdot 19+1)^k$ , για k=1,2,3

είναι

, και,

, αντίστοιχα.

κ.τ.λ.)

EDIT. Η εξέταση του Μ.Κ.Δ. δεν είναι απαραίτητη. Το διεπίστωσα αμέσως, αλλά απάντησε γρήγορα ο Αλέξανδρος και θεώρησα πως θα μπορούσα να μην επεξεργασθώ την απάντηση. Ο Νίκος Κατσίπης το παρατήρησε επίσης και μου το ανέφερε σε προσωπικό μήνυμα. Για χάρη της μαθηματικής ακρίβειας, λοιπόν, ας το επισημάνουμε εδώ κι επισήμως.

Φιλικά,

Αχιλλέας

#6

Τέλεια Αχιλλέα!

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

είναι ένας πρώτος για τον οποίο ο 2^n+3^n

δεν διαιρείται από το

για κανένα

) αλλά και μερικά υπολογιστικά κομμάτια (η διαπίστωση ότι το

είναι πράγματι ο ελάχιστος πρώτος για τον οποίο συμβαίνει το συμπέρασμα της εκφώνησης, βρίσκοντας κατάλληλα

για σταθερό p<19

κάθε φορά για τα οποία δεν ισχύει το συμπέρασμα). Ίσως το τελευταίο να ήταν ένα από τους λόγους για τους οποίους δεν επιλέχθηκε η συγκεκριμένη άσκηση για το διαγωνισμό.

Αλέξανδρος

#7

cretanman έγραψε: Να προσδιορίσετε τον ελάχιστο πρώτο αριθμό για τον οποίο δεν υπάρχει φυσικός αριθμός ώστε να ισχύει $2^n+3^n\equiv 0 \pmod{p}$ .

Έψαχνα κάτι άλλο και έπεσα πάνω σε αυτό το όμορφο πρόβλημα. Έξτρα ερώτημα: Να βρεθεί άλλος ένας πρώτος με την παραπάνω ιδιότητα.

#8

cretanman έγραψε:Να προσδιορίσετε τον ελάχιστο πρώτο αριθμό για τον οποίο δεν υπάρχει φυσικός αριθμός ώστε να ισχύει $2^n+3^n\equiv 0 \pmod{p}$ .

Όταν

η $2^n+3^n\equiv 0 \pmod{p}$ είναι ισοδύναμη με $11^n\equiv -1 \pmod{19}.$
Όμως, $11^1\equiv 11 \pmod{19}, 11^2\equiv 7 \pmod{19}, 11^3 \equiv 1 \pmod{19}$ άρα είναι αδύνατη.

#9

silouan έγραψε:
cretanman έγραψε: Να προσδιορίσετε τον ελάχιστο πρώτο αριθμό για τον οποίο δεν υπάρχει φυσικός αριθμός ώστε να ισχύει $2^n+3^n\equiv 0 \pmod{p}$ .
Έψαχνα κάτι άλλο και έπεσα πάνω σε αυτό το όμορφο πρόβλημα. Έξτρα ερώτημα: Να βρεθεί άλλος ένας πρώτος με την παραπάνω ιδιότητα.

Όταν

η $2^n+3^n\equiv 0 \pmod{p}$ είναι ισοδύναμη με $20^n\equiv -1 \pmod{29}.$
Όμως,
$\displaystyle{20^1 \equiv 20 \pmod{29}, }$
$\displaystyle{20^2 \equiv 23 \pmod{29}, }$
$\displaystyle{20^3 \equiv 25 \pmod{29}, }$
$\displaystyle{20^4 \equiv 7 \pmod{29}, }$
$\displaystyle{20^5 \equiv 24 \pmod{29}, }$
$\displaystyle{20^6 \equiv 16 \pmod{29}, }$
$\displaystyle{20^7 \equiv 1 \pmod{29}, }$
άρα είναι αδύνατη.

#10

Να δειχθεί ότι υπάρχουν άπειροι πρώτοι με αυτήν την ιδιότητα.

#11

Demetres έγραψε:Να δειχθεί ότι υπάρχουν άπειροι πρώτοι με αυτήν την ιδιότητα.

Δημήτρη μου έκλεψες το επόμενο ερώτημα

#12

Demetres έγραψε:Να δειχθεί ότι υπάρχουν άπειροι πρώτοι με αυτήν την ιδιότητα.

Για να το δούμε για να μην ξεχαστεί. Η ιδέα είναι να βρούμε άπειρους πρώτους έτσι ώστε το 2 και το 3 να είναι τετραγωνικά κατάλοιπα αλλά το -1 να μην είναι.(*)

Τότε έχουμε το ζητούμενο γιατί η ισοτιμία γράφεται $2^n\equiv -3^n\pmod p$ . Αφού τα 2 και 3 είναι τετραγωνικά κατάλοιπα, γράφουμε
$x^{2n}\equiv -y^{2n}\pmod p$ αλλά αν

είναι τέτοιος ώστε $ya\equiv 1\pmod p$ έχουμε ότι $(xa)^{2n}\equiv -1\pmod p$ το οποίο είναι άτοπο γιατί το -1 δεν είναι τετραγωνικό κατάλοιπο.

Ας αποδείξουμε τώρα ότι υπάρχουν άπειροι πρώτοι που ικανοποιούν την (*). Το 2 είναι τετραγωνικό κατάλοιπο όταν $p\equiv 1,7\pmod 8$ και το 3 είναι όταν $p\equiv 1,11\pmod{12}$ . Το -1 δεν είναι όταν $p\equiv 3\pmod 4$ . Άρα αρκεί να βρούμε άπειρους πρώτους ώστε $p\equiv 7\pmod 8$ και $p\equiv 11\pmod{12}$ , που συμβαίνει ας πούμε όταν $p\equiv 23\pmod{24}$ . Υπάρχουν άπειροι πρώτοι της μορφής $p\equiv 23\pmod{24}$ από το Θεώρημα Dirichlet και τελειώσαμε.

Δημήτρη έχεις άλλη απόδειξη κατά νου;

#13

silouan έγραψε: Δημήτρη έχεις άλλη απόδειξη κατά νου;

Παρόμοιες ιδέες αλλά βρήκα περισσότερους πρώτους. Επιτρέπω επιπλέον τα 2,3

να είναι και τα δύο τετραγωνικά υπόλοιπα $\bmod p$ . Κατέληξα λίγο διαφορετικά σε αυτό:

(α) Για n = 2k

άρτιο πρέπει $(2^k)^2 \equiv -(3^k)^2 \bmod p$ οπότε αν το

δεν είναι τετραγωνικό υπόλοιπο $\bmod p$ αυτό δεν μπορεί να συμβεί.

(β) Για n = 2k+1

περιττό πρέπει $(2^{k+1})^2 \equiv -6(3^k)^2 \bmod p$ οπότε αν το

δεν είναι τετραγωνικό υπόλοιπο $\bmod p$ αυτό δεν μπορεί να συμβεί.

Από το (α) θέλω $p \equiv 3 \bmod 4$ . Από το (β), και χρησιμοποιώντας το $p \equiv 3 \bmod 4$ , θέλω:

$\displaystyle{ -1 = \left( \frac{-6}{p}\right) = \left( \frac{-1}{p}\right)\left( \frac{2}{p}\right)\left( \frac{3}{p}\right) = \left( \frac{2}{p}\right)\left( \frac{p}{3}\right)}$

Για $p \equiv 3 \bmod 8$ είναι $\left( \frac{2}{p}\right) = -1$ οπότε θέλω $\left( \frac{p}{3}\right) = 1$ , δηλαδή $p \equiv 1 \bmod 3$ . Αυτό δίνει $p \equiv 19 \bmod 24$ .

Για $p \equiv 7 \bmod 8$ είναι $\left( \frac{2}{p}\right) = 1$ οπότε θέλω $\left( \frac{p}{3}\right) = -1$ , δηλαδή $p \equiv 2 \bmod 3$ . Αυτό δίνει $p \equiv 23 \bmod 24$ .

Ελάχιστος πρώτος - JBMO Shortlist 2008

Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

Re: Ελάχιστος πρώτος - JBMO Shortlist 2008

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