Δύσκολο πρόβλημα!!

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

WLOG
Δημοσιεύσεις: 26
Εγγραφή: Δευ Δεκ 26, 2016 5:07 pm

Δύσκολο πρόβλημα!!

#1

Μη αναγνωσμένη δημοσίευση από WLOG » Τρί Ιουν 13, 2017 3:50 am

Να αποδείξετε ότι για κάθε c>0 υπάρχουν άπειροι αριθμοί n ώστε ο μεγαλύτερος πρώτος διαιρέτης του n^2 + 1 να είναι μεγαλύτερος του cn.
τελευταία επεξεργασία από WLOG σε Τρί Ιουν 13, 2017 11:36 am, έχει επεξεργασθεί 1 φορά συνολικά.



Λέξεις Κλειδιά:
Τροβαδούρος
Δημοσιεύσεις: 40
Εγγραφή: Κυρ Απρ 16, 2017 4:10 pm

Re: Δύσκολο πρόβλημα!!

#2

Μη αναγνωσμένη δημοσίευση από Τροβαδούρος » Τρί Ιουν 13, 2017 4:17 am

Έστω p_i ο iοστός πρώτος αριθμός.
Έστω p_k ο ελάχιστος πρώτος που είναι μεγαλύτερος από cn τότε ο αριθμός
n=(p_1\cdot p_2 \cdot ... \cdot p_{k-1})^{l} ικανοποιεί το ζητούμενο για κάθε ακέραιο l>0.

Δε μου φαίνεται να ανήκει σε αυτό το φάκελο.


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

Re: Δύσκολο πρόβλημα!!

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Ιουν 13, 2017 11:05 am

Τροβαδούρος έγραψε:Έστω p_i ο iοστός πρώτος αριθμός.
Έστω p_k ο ελάχιστος πρώτος που είναι μεγαλύτερος από cn τότε ο αριθμός
n=(p_1\cdot p_2 \cdot ... \cdot p_{k-1})^{l} ικανοποιεί το ζητούμενο για κάθε ακέραιο l>0.

Δε μου φαίνεται να ανήκει σε αυτό το φάκελο.
Μάλλον κάπου κάνεις λάθος. Ορίζεις το p_k χρησιμοποιώντας το n και μετά ορίζεις το n χρησιμοποιώντας το p_k
WLOG έγραψε:Να αποδείξετε ότι για κάθε c>0 υπάρχουν άπειροι αριθμοί n ώστε ο μεγαλύτερος διαιρέτης του n^2 + 1 να είναι μεγαλύτερος του cn.
Υπάρχει πρόβλημα με την εκφώνηση. Μάλλον πρέπει να λέει « ... ο μεγαλύτερος πρώτος διαιρέτης ... »


WLOG
Δημοσιεύσεις: 26
Εγγραφή: Δευ Δεκ 26, 2016 5:07 pm

Re: Δύσκολο πρόβλημα!!

#4

Μη αναγνωσμένη δημοσίευση από WLOG » Τρί Ιουν 13, 2017 11:35 am

Demetres έγραψε:
Τροβαδούρος έγραψε:Έστω p_i ο iοστός πρώτος αριθμός.
Έστω p_k ο ελάχιστος πρώτος που είναι μεγαλύτερος από cn τότε ο αριθμός
n=(p_1\cdot p_2 \cdot ... \cdot p_{k-1})^{l} ικανοποιεί το ζητούμενο για κάθε ακέραιο l>0.

Δε μου φαίνεται να ανήκει σε αυτό το φάκελο.
Μάλλον κάπου κάνεις λάθος. Ορίζεις το p_k χρησιμοποιώντας το n και μετά ορίζεις το n χρησιμοποιώντας το p_k
WLOG έγραψε:Να αποδείξετε ότι για κάθε c>0 υπάρχουν άπειροι αριθμοί n ώστε ο μεγαλύτερος διαιρέτης του n^2 + 1 να είναι μεγαλύτερος του cn.
Υπάρχει πρόβλημα με την εκφώνηση. Μάλλον πρέπει να λέει « ... ο μεγαλύτερος πρώτος διαιρέτης ... »
Ναι έχετε δίκιο έκανα λάθος μετάφραση!!


WLOG
Δημοσιεύσεις: 26
Εγγραφή: Δευ Δεκ 26, 2016 5:07 pm

Re: Δύσκολο πρόβλημα!!

#5

Μη αναγνωσμένη δημοσίευση από WLOG » Τρί Ιουν 13, 2017 11:35 am

WLOG έγραψε:Να αποδείξετε ότι για κάθε c>0 υπάρχουν άπειροι αριθμοί n ώστε ο μεγαλύτερος πρώτος διαιρέτης του n^2 + 1 να είναι μεγαλύτερος του cn.


Άβαταρ μέλους
silouan
Επιμελητής
Δημοσιεύσεις: 1282
Εγγραφή: Τρί Ιαν 27, 2009 10:52 pm

Re: Δύσκολο πρόβλημα!!

#6

Μη αναγνωσμένη δημοσίευση από silouan » Τρί Ιουν 13, 2017 12:03 pm

Ας δείξουμε πρώτα το ευκολότερο:

Υπάρχουν άπειροι n ώστε ο n^2+1 να έχει πρώτο διαιρέτη μεγαλύτερο από 2n+\sqrt{2n}.


Σιλουανός Μπραζιτίκος
Άβαταρ μέλους
JimNt.
Δημοσιεύσεις: 593
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Δύσκολο πρόβλημα!!

#7

Μη αναγνωσμένη δημοσίευση από JimNt. » Τρί Ιουν 13, 2017 12:11 pm

Oυσιαστικά όταν n^2+1=2p


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

Re: Δύσκολο πρόβλημα!!

#8

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιουν 15, 2017 10:43 am

silouan έγραψε:Ας δείξουμε πρώτα το ευκολότερο:

Υπάρχουν άπειροι n ώστε ο n^2+1 να έχει πρώτο διαιρέτη μεγαλύτερο από 2n+\sqrt{2n}.
Έστω p = 4k+1 πρώτος. Γνωρίζουμε ότι υπάρχει x ώστε x^2 \equiv -1 \bmod p. Επιπλέον στο διάστημα \{1,2,\ldots,4k\} υπάρχουν ακριβώς δύο τέτοια x. Το άθροισμά τους ισούται με p οπότε μπορούμε να υποθέσουμε πως αυτά είναι τα 2k-r και το 2k+r+1 για κάποιο r \geqslant 0.

Θέτουμε n = 2k-r. Από την επιλογή του n, ο p διαιρεί τον n^2+1. Επιπλέον, αφού 4k \equiv -1 \bmod p τότε

\displaystyle{ 4(n^2+1) = 16k^2- 16kr+4r^2+4 \equiv -4k-16kr + 4r^2+4 \equiv 1+4r+4r^2+4 = (2r+1)^2 + 4 \bmod p }

Άρα το (2r+1)^2+4 είναι πολλαπλάσιο του p οπότε 2r+1 \geqslant \sqrt{p-4} = \sqrt{4k-3} = \sqrt{2n+2r-3} \geqslant \sqrt{2n} εκτός και αν r=0,1 το οποίο μπορεί να συμβεί μόνο για αρκετά μικρό p.

Τέλος έχουμε

\displaystyle{ p = 4k+1 = 2n + 2r+1 \geqslant 2n+\sqrt{2n}}

Για να ολοκληρωθεί το ζητούμενο επικαλούμαστε το γεγονός ότι υπάρχουν άπειροι πρώτοι της μορφής 1 \bmod 4.


Άβαταρ μέλους
silouan
Επιμελητής
Δημοσιεύσεις: 1282
Εγγραφή: Τρί Ιαν 27, 2009 10:52 pm

Re: Δύσκολο πρόβλημα!!

#9

Μη αναγνωσμένη δημοσίευση από silouan » Πέμ Ιουν 15, 2017 12:18 pm

Πολύ ωραία Δημήτρη!
Πρόκειται για το πρόβλημα 3 της ΙΜΟ 2008.
https://artofproblemsolving.com/communi ... 21p1190546


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

Re: Δύσκολο πρόβλημα!!

#10

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιουν 16, 2017 2:05 pm

Μου φαίνεται εύκολο για πρόβλημα 3. Ιδίως για σχετικά πρόσφατη ολυμπιάδα.

Από την άλλη το αρχικό πρόβλημα φαίνεται εξαιρετικά δύσκολο. Έχω μια ιδέα η οποία πρέπει να δουλεύει αλλά θέλει θεώρημα πρώτων αριθμών και μάλιστα με μη τετριμμένο τρόπο. Γνωρίζουμε αν το πρόβλημα έχει πιο στοιχειώδη λύση ή αν χρειάζονται τα βαρέα όπλα;


WLOG
Δημοσιεύσεις: 26
Εγγραφή: Δευ Δεκ 26, 2016 5:07 pm

Re: Δύσκολο πρόβλημα!!

#11

Μη αναγνωσμένη δημοσίευση από WLOG » Παρ Ιουν 16, 2017 3:23 pm

Demetres έγραψε:Μου φαίνεται εύκολο για πρόβλημα 3. Ιδίως για σχετικά πρόσφατη ολυμπιάδα.

Από την άλλη το αρχικό πρόβλημα φαίνεται εξαιρετικά δύσκολο. Έχω μια ιδέα η οποία πρέπει να δουλεύει αλλά θέλει θεώρημα πρώτων αριθμών και μάλιστα με μη τετριμμένο τρόπο. Γνωρίζουμε αν το πρόβλημα έχει πιο στοιχειώδη λύση ή αν χρειάζονται τα βαρέα όπλα;
Μου φαίνεται ότι πρέπει να χρησιμοποιηθούν βαριά όπλα :D


Απάντηση

Επιστροφή σε “Θεωρία Αριθμών - Προχωρημένο Επίπεδο (Seniors)”

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

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