Просто число

[v1rusman]

Да се намерят всички прости числа [tex]p[/tex] от вида
[tex]p = 2^{a_{n}} + 1[/tex],
където с [tex]a_{n}[/tex] е означено число на Фибоначи. Числата на Фибоначи се
дефинират по следния начин:
[tex]a_{1}=a_{2}=1, a_{n+1} = a_{n}+a_{n-1}[/tex]

[Реклама]

[dim]

Ако а_n e нечетно или има някой нечетен делител t и a_n=t.s, то:

2^s.t+1=(2^s)^t=(2^s+1)(2^s(t-1)-2^s(t-2)+2^s(t-3)-...+1), откъдето се вижда, че p не може да е просто.Значи 2 трябва да е на степен, в която не могат да присъстват нечетни множители=>а_n e степен на 2 или а_n=2^x

Сега остава да се провери кои числа от редицата на фибоначи са степени на 2.Ако това са само 8 и 2, то работата е ясна.

Ама тука нещо запецнах

[Пафнутий]

И аз стигам до там, но трудното(поне според мен) е да се намерят всички числа на Фибоначи от вида [tex]2^n[/tex]. Задачата обаче доста ми напомня за простите числа на Ферма [tex](2^{2^n}+1)[/tex]
ПП не трябва да се забравя и за случая [tex]2^1+1=3[/tex]

[v1rusman]

@dim:Браво, добре си разсъждавал ! Трудността на задачата обаче идва в доказателството, че няма други числа на Фибоначи, освен 2 и 8, които да са степени на 2.

@stanislav.atanasov: Не се бях замислял, че наистина са числа на Ферма, но това едва ли олеснява положението. Иначе добро оточнение.

[Пафнутий]

Ще изложа разсъжденията си Както показа dim трябва да намерим всички [tex]a_{n}=2^k[/tex] ,където с [tex]a_{n}[/tex] отбелязваме [tex]n[/tex]-тото число на Фибоначи.При [tex]k=0[/tex] , получаваме [tex]p=2^1+1=3[/tex] , което е просто Ще разглеждаме [tex]k>0\Rightarrow a_{n}[/tex] е четно.Оттук получаваме, че [tex]a_{n-1}[/tex] и [tex]a_{n-2}[/tex]- нечетни[tex](1)[/tex].
Да допуснем, че за [tex]a_{t}=2^k[/tex] , за произволно естествено [tex]t[/tex].Тогава използвайки вярното равенство ([tex]2^{r-1}+2^{r-1}=2^r[/tex]) можем да запишем [tex]a_{t-1}=2^{k-1}+s[/tex] и [tex]a_{t-2}=2^{k-1}-s[/tex], където [tex]s[/tex] е нечетно естествено число, съгласно [tex](1)[/tex]. Тогава са верни и равенствата [tex]a_{t-1}-s=a_{t-2}+s=2^{k-1} \Leftrightarrow a_{t-1}-a_{t-2}=2s=2^{k-1}\Rightarrow \cancel a_{t-2}+a_{t-3}-\cancel a_{t-2}=2s=2^{k-1}\Rightarrow a_{t-3}=2s=2^{k-1}\leftrightarrow s=2^{k-2}[/tex]. Понеже [tex]s[/tex] е нечетно, то [tex]2^{k-2}[/tex] също е нечетно, следователно [tex]s=1[/tex].Оттук [tex]a_{t-3}=2[/tex] и [tex]a_{t}=8[/tex],т.е единствените [tex]a_{n}[/tex], за които [tex]2^{a_{n}}+1[/tex] e просто са 1,2,8
ПП Решението ми ми е малко съмнително

[Gringo]

Този материал за кой клас е?

[v1rusman]

Този материал не е за никой клас в училище, защото се "води" като материал за 9-12. клас ако ходиш на състезания по математика като ЗМС, ПМТ, Националната олимпиада по математика и др.

[Пафнутий]

Би ли постнал авторското решение? Или ми го прати на ЛС

[v1rusman]

Решение:
Ясно е, че ако [tex]a_{n}>1[/tex] и притежава нечетен делител по-голям от 1, числото [tex]2^{a_{n}} + 1[/tex] ще бъде съставно.
Следователно числото [tex]2^{a_{n}} + 1[/tex] може да бъде просто само ако [tex]a_{n}[/tex] е степен на 2. Такива са [tex]a_{1}=a_{2}=1, a_{3}=2, a_{6}=8[/tex].

Да разгледаме сега остатъците на [tex]a_{n} (n=1,2,....)[/tex] при деление на 16. Индуктивно се проверява, че тези остатъци образуват периодична редица с период 24, като на 16 се делят само числата [tex]a_{12m}[/tex]. От друга страна обаче, ако разгледаме остатъците на [tex]a_{n}[/tex] при деление на 3, виждаме, че всяко число [tex]a_{4l}[/tex] се дели на 3. Следователно никое от числата [tex]a_{n}, n > 6[/tex], не е степен на 2 и единствените прости числа от дадения вид са [tex]3, 5, 257[/tex].

ПП: Гледам, че си станал фен на parkour-а и freerun-а.

[Пафнутий]

Решението е доста по-добро от моето, но и доста по-сложно Това с периода през 24 никога нямаше да ми дойде на акъла
ПП Аз отдавна се занимавам с PK и Freerun, само че бях спрял и сега отново почвам

[dim]

Много добро решение, v1rusman!

Аз бях тръгнал да разглеждам остатъците при делене на 8, стигнах до 144 и реших, че тая работа с остатъците няма да я бъде

[v1rusman]

Решението не е мое. Все пак е добре, че си се сетил за остатъците при деление на 8. Браво!