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

WLOG · #1

Να αποδείξετε ότι για κάθε c>0

υπάρχουν άπειροι αριθμοί

ώστε ο μεγαλύτερος πρώτος διαιρέτης του n^2 + 1

να είναι μεγαλύτερος του

.

Τροβαδούρος · #2

Έστω

ο iοστός πρώτος αριθμός.
Έστω p_k

ο ελάχιστος πρώτος που είναι μεγαλύτερος από

τότε ο αριθμός
$n=(p_1\cdot p_2 \cdot ... \cdot p_{k-1})^{l}$ ικανοποιεί το ζητούμενο για κάθε ακέραιο l>0

.

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

#3

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

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

Μάλλον κάπου κάνεις λάθος. Ορίζεις το p_k

χρησιμοποιώντας το

και μετά ορίζεις το

χρησιμοποιώντας το p_k

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

Υπάρχει πρόβλημα με την εκφώνηση. Μάλλον πρέπει να λέει « ... ο μεγαλύτερος πρώτος διαιρέτης ... »

WLOG · #4

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

Δε μου φαίνεται να ανήκει σε αυτό το φάκελο.
Μάλλον κάπου κάνεις λάθος. Ορίζεις το χρησιμοποιώντας το και μετά ορίζεις το χρησιμοποιώντας το

WLOG έγραψε:Να αποδείξετε ότι για κάθε υπάρχουν άπειροι αριθμοί ώστε ο μεγαλύτερος διαιρέτης του να είναι μεγαλύτερος του .
Υπάρχει πρόβλημα με την εκφώνηση. Μάλλον πρέπει να λέει « ... ο μεγαλύτερος πρώτος διαιρέτης ... »

Ναι έχετε δίκιο έκανα λάθος μετάφραση!!

WLOG · #5

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

#6

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

Υπάρχουν άπειροι

ώστε ο

να έχει πρώτο διαιρέτη μεγαλύτερο από $2n+\sqrt{2n}$ .

JimNt. · #7

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

#8

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

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

Έστω

πρώτος. Γνωρίζουμε ότι υπάρχει

ώστε $x^2 \equiv -1 \bmod p$ . Επιπλέον στο διάστημα $\{1,2,\ldots,4k\}$ υπάρχουν ακριβώς δύο τέτοια

. Το άθροισμά τους ισούται με

οπότε μπορούμε να υποθέσουμε πως αυτά είναι τα 2k-r

και το

για κάποιο $r \geqslant 0$ .

Θέτουμε n = 2k-r

. Από την επιλογή του

, ο

διαιρεί τον 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

είναι πολλαπλάσιο του

οπότε $2r+1 \geqslant \sqrt{p-4} = \sqrt{4k-3} = \sqrt{2n+2r-3} \geqslant \sqrt{2n}$ εκτός και αν r=0,1

το οποίο μπορεί να συμβεί μόνο για αρκετά μικρό

.

Τέλος έχουμε

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

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

#9

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

#10

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

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

WLOG · #11

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

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

Μου φαίνεται ότι πρέπει να χρησιμοποιηθούν βαριά όπλα

#12

Μου ζητήθηκε να βάλω τη λύση στην οποία αναφερόμουν. Έπρεπε να το λύσω ξανά μιας και δεν θυμόμουν τη λύση μου. Δεν ξέρω καν αν είναι ίδια με αυτή που είχα βρει τότε ή όχι. Ίσως να είχα και κάτι πιο απλό, ίσως και όχι.

Θέτω $f(N) = \prod_{n=1}^N (n^2+1)$ .

Παρατηρώ ότι $\displaystyle f(N) \geqslant (N!)^2 = \prod_{p \leqslant N} p^{2a_p}$ όπου a_p

είναι η μεγαλύτερη δύναμη του πρώτου

η οποία διαιρεί το

. Επομένως $a_p = \sum_{k=1}^{\infty} \left\lfloor N/p^k \right\rfloor$ .

Έχουμε επίσης $\displaystyle f(N) = \prod_{n=1}^N (n^2+1) = \prod_{p \leqslant N^2+1} p^{b_p}.$ Παρατηρούμε τα εξής:

b_p = 0

για $p \equiv 3 \bmod 4$ αφού αν $p \equiv 3 \bmod 4$ και $n \in \mathbb{N}$ τότε $p \nmid n^2+1$ .
$b_2 =\left\lceil N/2\right\rceil$ αφού $4 \nmid n^2+1$ και επιπλέον $2|n^2+1 \iff n$ περιττός.
$b_p \leqslant 1$ για p > N

.

Επιπλέον, αν $p \leqslant N$ με $p \equiv 1 \bmod 4$ τότε υπάρχουν δύο υπόλοιπα $x \bmod p$ ώστε $x^2+1 \equiv 0 \bmod p$ . Από το Λήμμα Hensel ( f(x) = x^2+1

τότε $f'(x) = 2x \neq 0 \bmod p$ για $x \neq 0 \bmod p$ ) για κάθε

υπάρχουν δύο υπόλοιπα $x \bmod p^k$ ώστε $x^2+1 \equiv 0 \bmod p^k$ . Άρα για αυτά τα

έχουμε

$\displaystyle b_p \leqslant 2\sum_{k=1}^{m} \left\lceil N/p^k \right\rceil \leqslant 2a_p + 2m \leqslant 2a_p + 2\log_p(N^2+1)$

όπου το

είναι μέγιστο ώστε $(N^2+1)/p^m \geqslant 1$ .

Παίρνουμε ότι

$\displaystyle \prod_{N < p \leqslant N^2+1} p^{b_p} \geqslant 2^{2a_2 - (N+1)/2} \prod_{\stackrel{ p \leqslant N}{p \equiv 1 \bmod 4}} p^{-2\log_p(N^2+1)} \prod_{\stackrel{ p \leqslant N}{p \equiv 3 \bmod 4}} p^{a_p}$

Έχουμε $a_2 \geqslant (N-1)/2$ , άρα $2a_2 - (N+1)/2 \geqslant 0$ .

Έχουμε επίσης $\displaystyle \prod_{\stackrel{ p \leqslant N}{p \equiv 1 \bmod 4}} p^{-2\log_p(N^2+1)} = \frac{1}{(N^2+1)^{\pi_{4,1}(N)}} \geqslant N^{-2N/\log{N}}$

όπου $\pi_{4,1}(N)$ το πλήθος των πρώτων της μορφής $1 \bmod 4$ που είναι μικρότεροι ή ίσοι του

. Στην τελευταία ανισότητα χρησιμοποιήσαμε ότι $\pi_{4,1}(N) \sim \frac{N}{2\log{N}}$ οπότε η ανισότητα ισχύει άνετα για αρκετά μεγάλα

Επιπλέον, αν $p^r \leqslant N < p^{r+1}$ βλέπουμε ότι $\displaystyle a_p \leqslant 1+p+p^2 + \cdots + p^{r-1} = \frac{p^r-1}{p-1} > \frac{N-1}{p}$

Άρα $\displaystyle \prod_{\stackrel{ p \leqslant N}{p \equiv 3 \bmod 4}} p^{a_p} \geqslant \prod p^{(N-1)/p} = e^{(N-1)S(N)}$

όπου $\displaystyle S(N) = \sum \frac{\log{p}}{p}$ όπου το άθροισμα είναι σε όλους τους πρώτους $p \leqslant N$ της μορφής $p \equiv 3 \bmod 4$ .

Από το Θεώρημα πρώτων αριθμών σε αριθμητικές προόδους έχουμε $S(N) \sim \frac{\log{N}}{2}$ .

Καταλήγουμε (με αρκετή χαλαρότητα) στο

$\displaystyle \prod_{N < p \leqslant N^2+1} p^{b_p} \geqslant N^{N/3}$

Όμως $\displaystyle \prod_{N < p \leqslant N^2+1} p^{b_p} \leqslant (N^2+1)^t$ όπου

το πλήθος των πρώτων για τους οποίους b_p=1

. Δηλαδή αυτούς για τους οποίους υπάρχει $n \leqslant N$ με p|n^2+1

.

Έχουμε $(N^2+1)^t \geqslant N^{N/3}$ που δίνει $t \geqslant (N/3)(\log{N})/(\log(N^2+1))\sim N/6$ .

Για αρκετά μεγάλο

θα έχουμε τουλάχιστον N/7

τόσους πρώτους. Μέχρι όμως το

έχουμε το πολύ $\frac{2cN}{\log{N}}$ πρώτους αριθμούς.

Άρα θα έχουμε τουλάχιστον N/8

πρώτους μεγαλύτερους του

ώστε κάθε ένας να διαιρεί το n^2+1

για κάποιο $n \leqslant N$ .

Το ζητούμενο έπεται.

2nisic · #13

silouan έγραψε: ↑
Τρί Ιουν 13, 2017 12:03 pm
Ας δείξουμε πρώτα το ευκολότερο:

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

WLOG έγραψε: ↑
Τρί Ιουν 13, 2017 3:50 am
Να αποδείξετε ότι για κάθε υπάρχουν άπειροι αριθμοί ώστε ο μεγαλύτερος πρώτος διαιρέτης του να είναι μεγαλύτερος του .

Υπάρχουν άπειροι φυσικοί αριθμοί

για τους οποίους ο αριθμός n^2+1

έχει έναν πρώτο δειερετη μεγαλύτερο τού $n^{1.279}$ .

llenny · #14

2nisic έγραψε: ↑
Δευ Ιούλ 05, 2021 11:52 am

silouan έγραψε: ↑
Τρί Ιουν 13, 2017 12:03 pm
Ας δείξουμε πρώτα το ευκολότερο:

Υπάρχουν άπειροι ώστε ο να έχει πρώτο διαιρέτη μεγαλύτερο από $2n+\sqrt{2n}$ .
WLOG έγραψε: ↑
Τρί Ιουν 13, 2017 3:50 am
Να αποδείξετε ότι για κάθε υπάρχουν άπειροι αριθμοί ώστε ο μεγαλύτερος πρώτος διαιρέτης του να είναι μεγαλύτερος του .
Υπάρχουν άπειροι φυσικοί αριθμοί για τους οποίους ο αριθμός έχει έναν πρώτο δειερετη μεγαλύτερο τού $n^{1.279}$ .

Η απόδειξη αφήνεται λόγω απλότητας ως άσκηση για τον αναγνώστη. ( https://arxiv.org/abs/1908.08816 )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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