Διαιρετότητα και άπειροι αριθμοί

themiskant · #1

Να αποδειχθεί ότι υπάρχουν άπειροι φυσικοί αριθμοί

,ώστε ο αριθμός

να διαιρεί το $2^{n}+1$

nickthegreek · #2

Ωραία άσκηση!!!Θα αποδείξουμε το ακόλουθο, το οποίο λύνει και την άσκηση:

Λήμμα:

Αν $a \in Z^{+} \Rightarrow 3^a \mid 2^{3^a}+1$

Απόδειξη

Αρκεί να δείξουμε ότι ο μεγαλύτερος εκθέτης

ώστε $3^k \mid 2^{3^a}+1$ είναι μεγαλύτερος ή ίσος του

.

Σύμφωνα με το λήμμα Lift the Exponent, ,αν συμβολίσουμε με u_p(x)

τη μέγιστη δύναμη του πρώτου

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

, έχουμε

$u_3(2^{3^a}+1)=u_3(2+1)+u_3(3^a)=1+a>a$ και το ζητούμενο έπεται...

#3

Και μια παραδοσιακή, αναλυτική απόδειξη του γεγονότος ότι

$\displaystyle{\bullet}$ Αν $\displaystyle{k}$ θετικός ακέραιος, τότε $\displaystyle{3^k|2^{(3^k)}+1}$

Από το θεώρημα του Euler έχουμε

$\displaystyle{2^{\phi (3^k)}\equiv 1\mod 3^k}$ , που επειδή είναι $\displaystyle{\phi (3^k)=2\cdot 3^k,}$ έχουμε

$\displaystyle{2^{2\cdot 3^{k-1}}\equiv 1\mod 3^k}$ ,

άρα, με ύψωση εις την τρίτη,

$\displaystyle{2^{2\cdot 3^{k}}\equiv 1\mod 3^k}$ ,

δηλαδή

$\displaystyle{\Big(2^{3^k}\Big)^2\equiv 1\mod 3^k}$ ,

όπερ σημαίνει ότι

το $\displaystyle{3^k}$ διαιρεί το γινόμενο $\displaystyle{(2^{3^k}+1)(2^{3^k}-1)}$ .

Δείχνουμε ότι οι $\displaystyle{3^k,~2^{3^k}-1}$ είναι πρώτοι μεταξύ τους και τελειώσαμε.

Έστω ότι δεν είναι πρώτοι μεταξύ τους. Τότε, για κάποιο $\displaystyle{k}$ θα είχαμε

$3|(2^{3^k}-1)$ .

Ας είναι $\displaystyle{3^k=2m+1,~m\in \mathbb{N}.}$

Τότε

$\displaystyle{3|2^{2m+1}-1\implies 3|2\cdot 2^{2k}+2-3\implies 3|2(2^{2k}+1)\implies 3|(2^k)^2+1}$ , αφού $\displaystyle{(3,2)=1}$ .

Αυτό όμως είναι άτοπο, αφού γνωρίζουμε ότι $\displaystyle{3|(a^2+b^2)\implies 3|a \wedge 3|b.}$

#4

Ας δούμε και την απολύτως στοιχειώδη απόδειξη του ισχυρισμού

$\displaystyle{\boxed{3^k|(2^{3^k}+1),~\forall k\in \mathbb{N}}$

Με επαγωγή:

$\displaystyle{\bullet}$ Για $\displaystyle{k=1}$ ο ισχυρισμός είναι προφανής.

$\displaystyle{\bullet}$ Έστω ότι ισχύει $\displaystyle{3^k|(2^{3^k}+1)}$ για κάποιο $\displaystyle{k\in \mathbb{N}.}$

$\displaystyle{\bullet}$ Θα αποδείξουμε ότι $\displaystyle{3^{k+1}|(2^{3^{k+1}}+1)}$

Είναι

$\displaystyle{2^{3^{k+1}}+1=\Big(2^{3^k}\Big)^3+1=(2^{3^k}+1)(2^{2\cdot 3^k}-2^{3^k}+1)}$ .

Λόγω της επαγωγικής υπόθεσης, η πρώτη παρένθεση είναι διαιρετή με το $\displaystyle{3^k,}$ άρα απομένει να αποδειχθεί ότι

$\displaystyle{3|(2^{2\cdot 3^k}-2^{3^k}+1)}$ .

Αυτό ισχύει, αφού

$\displaystyle{2^{2\cdot 3^k}-2^{3^k}+1=4^{3^k}-1-\Big(2^{3^k}+1\Big)+3}$ ,

οπότε αρκεί να θυμηθούμε ότι
$\displaystyle{(x-y)|(x^n-y^n)}$

και

$\displaystyle{(x+y)|(x^n+y^n),}$ όταν $\displaystyle{n}$ περιττός.

Διαιρετότητα και άπειροι αριθμοί

Διαιρετότητα και άπειροι αριθμοί

Re: Διαιρετότητα και άπειροι αριθμοί

Re: Διαιρετότητα και άπειροι αριθμοί

Re: Διαιρετότητα και άπειροι αριθμοί

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