Διαιρετότητα και πρώτοι

stranger · #1

Έστω

διακεκριμένοι πρώτοι όλοι $\equiv 3 (mod 4)$ .
Να δείξετε ότι $\prod_{i=1}^{k}(p_i^2-1) \mid (\prod_{i=1}^{k}p_i )^2 -1$ αν και μόνο αν k=1

stranger · #2

Η εικασία του Lehmer λέει το εξής. Αν d>1

και

φυσικός αριθμός τότε αν $\phi(d) \mid d-1$ τότε ο

είναι πρώτος, όπου $\phi$ η ολική συνάρτηση του Euler. Είναι ανοιχτό πρόβλημα.
Δείξτε ότι η εικασία του Lehmer είναι ισοδύναμη με την πρόταση:
Για κάθε d>1

με $\phi(d) \mid d-1$ ισχύει $\phi(d)+1 \mid d$ .

stranger · #3

stranger έγραψε: Δευ Δεκ 21, 2020 9:48 pm Έστω διακεκριμένοι πρώτοι όλοι $\equiv 3 (mod 4)$ .
Να δείξετε ότι $\prod_{i=1}^{k}(p_i^2-1) \mid (\prod_{i=1}^{k}p_i )^2 -1$ αν και μόνο αν

2nisic · #4

Να αποδειχθεί ότι αν $\phi(d)|d-1$ και ο

δεν είναι πρώτος:

α) Ο

είναι

β)Ο

έχει τουλάχιστον

πρώτους διαιρέτες

#5

stranger έγραψε: Δευ Δεκ 21, 2020 9:48 pm Έστω διακεκριμένοι πρώτοι όλοι $\equiv 3 (mod 4)$ .
Να δείξετε ότι $\prod_{i=1}^{k}(p_i^2-1) \mid (\prod_{i=1}^{k}p_i )^2 -1$ αν και μόνο αν

Θα το δείξω για οποιασδήποτε μορφής διακεκριμένους πρώτους. Έστω $\mathbb{P}$ το σύνολο όλων των πρώτων. Έχουμε

$\displaystyle N = \frac{\left(\prod\limits_{i=1}^{k}p_i\right)^2 -1}{\prod\limits_{i=1}^{k} (p_i^2-1)} = \prod_{i=1}^{k}\frac{p_i^2}{p_i^2-1} \leqslant \prod_{p\in \mathbb{P}} \frac{p^2}{p^2-1} = \prod_{p\in \mathbb{P}} \sum_{m=0}^{\infty} \frac{1}{p^{2m}} = \sum_{n=1}^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6} < 2$

Όμως ο

είναι θετικός ακέραιος, άρα N = 1

. Όμως για $k \geqslant 2$ είναι απλό να δειχθεί επαγωγικά ότι N > 1

, άτοπο.

stranger · #6

2nisic έγραψε: Τρί Μαρ 16, 2021 9:30 pm Να αποδειχθεί ότι αν $\phi(d)|d-1$ και ο δεν είναι πρώτος:

α) Ο είναι

β)Ο έχει τουλάχιστον πρώτους διαιρέτες

Το α) είναι αρκετά απλό και το απέδειξε πρώτος ο Lehmer όταν διατύπωνε την εικασία του Lehmer.
Αν ο

διαιρείται από τετράγωνο πρώτου p^2

τότε $\phi(p^2) \mid \phi(d)$ και επειδή $\phi(p^2)=p(p-1)$ αυτό σημαίνει $p \mid \phi(d) \mid d-1$ . Άρα ο

διαιρεί το d-1

και το

, το οποίο είναι άτοπο.

stranger · #7

stranger έγραψε: Τρί Δεκ 22, 2020 10:44 am Η εικασία του Lehmer λέει το εξής. Αν και φυσικός αριθμός τότε αν $\phi(d) \mid d-1$ τότε ο είναι πρώτος, όπου $\phi$ η ολική συνάρτηση του Euler. Είναι ανοιχτό πρόβλημα.
Δείξτε ότι η εικασία του Lehmer είναι ισοδύναμη με την πρόταση:
Για κάθε με $\phi(d) \mid d-1$ ισχύει $\phi(d)+1 \mid d$ .

2nisic · #8

stranger έγραψε: Δευ Μάιος 31, 2021 11:40 am
stranger έγραψε: Τρί Δεκ 22, 2020 10:44 am Η εικασία του Lehmer λέει το εξής. Αν και φυσικός αριθμός τότε αν $\phi(d) \mid d-1$ τότε ο είναι πρώτος, όπου $\phi$ η ολική συνάρτηση του Euler. Είναι ανοιχτό πρόβλημα.
Δείξτε ότι η εικασία του Lehmer είναι ισοδύναμη με την πρόταση:
Για κάθε με $\phi(d) \mid d-1$ ισχύει $\phi(d)+1 \mid d$ .

Αν

,

και $n\neq m$ τότε m>=n(n+2)

αλλά $f(d)\geq \sqrt{d}$ για κάθε d>=7

Οπότε

αρα

πρώτος
Ή

....

2nisic έγραψε: Τρί Μαρ 16, 2021 9:30 pm Να αποδειχθεί ότι αν $\phi(d)|d-1$ και ο δεν είναι πρώτος:

β)Ο έχει τουλάχιστον πρώτους διαιρέτες

stranger · #9

2nisic έγραψε: Δευ Μάιος 31, 2021 3:31 pm
stranger έγραψε: Δευ Μάιος 31, 2021 11:40 am
stranger έγραψε: Τρί Δεκ 22, 2020 10:44 am Η εικασία του Lehmer λέει το εξής. Αν και φυσικός αριθμός τότε αν $\phi(d) \mid d-1$ τότε ο είναι πρώτος, όπου $\phi$ η ολική συνάρτηση του Euler. Είναι ανοιχτό πρόβλημα.
Δείξτε ότι η εικασία του Lehmer είναι ισοδύναμη με την πρόταση:
Για κάθε με $\phi(d) \mid d-1$ ισχύει $\phi(d)+1 \mid d$ .

Αν , και $n\neq m$ τότε αλλά $f(d)\geq \sqrt{d}$ για κάθε
Οπότε αρα πρώτος
Ή ....
2nisic έγραψε: Τρί Μαρ 16, 2021 9:30 pm Να αποδειχθεί ότι αν $\phi(d)|d-1$ και ο δεν είναι πρώτος:

β)Ο έχει τουλάχιστον πρώτους διαιρέτες

Η ανισότητα $m \geq n(n+2)$ δεν ισχύει. Ισχύει η ανάποδη. Δηλαδή ισχύει η $m \leq n(n+2)$ για m=d-1

και $n=\phi(d)$ .
Οπότε,όλη η απόδειξη είναι λάθος.
Σημείωση: Θα βάλω τη λύση σε λίγο.

stranger · #10

stranger έγραψε: Τρί Δεκ 22, 2020 10:44 am Η εικασία του Lehmer λέει το εξής. Αν και φυσικός αριθμός τότε αν $\phi(d) \mid d-1$ τότε ο είναι πρώτος, όπου $\phi$ η ολική συνάρτηση του Euler. Είναι ανοιχτό πρόβλημα.
Δείξτε ότι η εικασία του Lehmer είναι ισοδύναμη με την πρόταση:
Για κάθε με $\phi(d) \mid d-1$ ισχύει $\phi(d)+1 \mid d$ .

Έστω ότι ισχύει η δεύτερη πρόταση.
Έστω ότι δεν ισχύει η εικασία του Lehmer. Έστω

ο ελάχιστος σύνθετος με $\phi(d) \mid d-1$ .
Άρα από υπόθεση έχουμε $\phi(d)+1 \mid d$ . Έστω $d'=\phi(d)+1$ . Τότε έχουμε $d' \mid d$ . Άρα $\phi(d') \mid \phi(d) = d'-1$ .Όμως d'<d

επειδή $d' \neq d$ γιατί αλλιώς θα είχαμε $\phi(d)+1=d$ , το οποίο είναι άτοπο αφού ο

είναι σύνθετος.
Τελικά έχουμε δείξει ότι d'<d

και $\phi(d') \mid d'-1$ , το οποίο σημαίνει ότι ο

είναι πρώτος.
Άρα $\phi(d')= d'-1=\phi(d)$ .
Επίσης, επειδή ο

είναι squarefree(βλεπε ποστ 6) παίρνουμε d=d'

που είναι άτοπο επειδή ο

είναι σύνθετος και ο

είναι πρώτος και το συμπέρασμα έπεται.

2nisic · #11

stranger έγραψε: Δευ Μάιος 31, 2021 4:11 pm Η ανισότητα $m \geq n(n+2)$ δεν ισχύει. Ισχύει η ανάποδη. Δηλαδή ισχύει η $m \leq n(n+2)$ για και $n=\phi(d)$ .
Οπότε,όλη η απόδειξη είναι λάθος.
Σημείωση: Θα βάλω τη λύση σε λίγο.

Ακριβώς επειδή ισχύει η ανάποδη περνώ άτοπο.
Αφού n|m

έχουμε

με

αφού $n\neq m$
n+1|k(n+1)-(m+1)=k-1

άρα

$\Rightarrow$ m>=n(n+2)

Όμως για

και

ισχύει η ανάποδη.

Άρα $m=n\Rightarrow f(d)=d-1\Leftrightarrow d=prime$

stranger · #12

2nisic έγραψε: Δευ Μάιος 31, 2021 7:17 pm
stranger έγραψε: Δευ Μάιος 31, 2021 4:11 pm Η ανισότητα $m \geq n(n+2)$ δεν ισχύει. Ισχύει η ανάποδη. Δηλαδή ισχύει η $m \leq n(n+2)$ για και $n=\phi(d)$ .
Οπότε,όλη η απόδειξη είναι λάθος.
Σημείωση: Θα βάλω τη λύση σε λίγο.
Ακριβώς επειδή ισχύει η ανάποδη περνώ άτοπο.
Αφού έχουμε με αφού $n\neq m$
άρα $\Rightarrow$

Όμως για και ισχύει η ανάποδη.

Άρα $m=n\Rightarrow f(d)=d-1\Leftrightarrow d=prime$

Τελικά έχεις δίκιο και σου ζητώ συγγνώμη. Είσαι σωστός και μάλιστα με πιο σύντομη απόδειξη από εμένα. Απλά δεν είχες γράψει την απόδειξη και δεν το έβλεπα σωστό.
Έκανα λάθος.

Διαιρετότητα και πρώτοι

Διαιρετότητα και πρώτοι

Re: Διαιρετότητα και πρώτοι,

Re: Διαιρετότητα και πρώτοι

Re: Διαιρετότητα και πρώτοι

Re: Διαιρετότητα και πρώτοι

Re: Διαιρετότητα και πρώτοι

Re: Διαιρετότητα και πρώτοι,

Re: Διαιρετότητα και πρώτοι,

Re: Διαιρετότητα και πρώτοι,

Re: Διαιρετότητα και πρώτοι,

Re: Διαιρετότητα και πρώτοι,

Re: Διαιρετότητα και πρώτοι

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