Да се намерят всички прости числа от вида ...

[Mr.G{}{}Fy]

Да се намерят всичките прости числа от вида [tex]p=2^{a_n} +1[/tex],където [tex]a_n[/tex] е редицата определена от числата на Фибоначи.

[mkmarinov]

1) [tex]2^r+1[/tex] е просто единствено когато [tex]r=2^t[/tex]. Ако [tex]r=q.2^k, q>1[/tex], [tex]2^r+1=(2^{2^k})^q+1^q[/tex], което се дели на [tex]2^{2^k}+1[/tex] и не съвпадат.
2) Ако [tex]s[/tex] е нечетно, то [tex]2^s+1 \equiv (-1)^{2k+1}+1 \equiv 0 (mod 3)[/tex]

От тези двете => искаме числото на Фибоначи да е [tex]2^z, z \in N[/tex]. Ще докажем,ч е единствено [tex]1,2,8[/tex] отговарят на това условие.
Нека гледаме четните степени на двойката.
Лесно се вижда, че само числата на Фибоначи с индекс кратен на 3 са четни. Нека видим как стоят нещата при тях:
[tex]F_{3n}=\frac{1}{\sqrt{5}}(\varphi^{3n}-(1-\varphi)^{3n})=\frac{1}{\sqrt{5}}(\varphi^n-(1-\varphi)^n)(\varphi^{2n}-2\varphi^n(1-\varphi)^n+(1-\varphi)^{2n}+3\varphi^n(1-\varphi)^n)=\\=F_n((\varphi^n-(1-\varphi^n))^2+3(\varphi-\varphi^2)^n)=F_n(5F_n^2+3(-1)^n)[/tex]
За да е степен на двойката, трябва и [tex]F_n[/tex], и [tex]5F_n^2+3(-1)^n[/tex] да са степени на двойката. Като второто число е нечетно => е равно на 1. Решенията са [tex]n=1 (F_{3n}=2)[/tex] и [tex]n=2 (F_{3n}=8)[/tex]. Като прибавим и нечетните степени на двойката (1), за кандидат-решения остават числата [tex]1,2,8[/tex].
[tex]2^1+1=3 \in P[/tex]
[tex]2^2+1 = 5 \in P[/tex]
[tex]2^8+1 = 257 \in P[/tex]
И това са единствените решения на задачата.

[Mr.G{}{}Fy]

За жалост,още не знам използвания материал,но когато стигна до него със сигурност ще видя и твоето решение.Иначе авторовото е като пак се доказва,че [tex]a_n[/tex] е степен на [tex]2[/tex]-ката и директно е проверено за [tex]1,2,8[/tex] (тъй като е ясно,че те са от редицата).След това използват,че всяко число от вида [tex]a{_12m}[/tex] се дели на 16,но пък всяко число от вида [tex]a_{4k}[/tex] се дели на [tex]3[/tex] ===> тъй като всяка по-висока от трета степен на двойката се дели на 16,то няма повече числа,които да изпълняват условието,тъй като всяко число от редицата делящо се на [tex]16[/tex] се дели и на [tex]3[/tex] т.е. не е точна степен на [tex]2[/tex].
А как мога да докажа,че всеки член от горепосочения вид се дели на [tex]16[/tex] ?Аз по индукция се пробвах като за първия такъв проверих директно,след това допуснах там,че е вярно за [tex]m=k[/tex] и като използвах това доказах,че е вярно за [tex]m=k+1[/tex],обаче така тръгнах да изразявам всеки член с предходния и стана малко дългичко.Това ли е начина или има по-лесен?
Иначе отговорите са тези,които си написал.Браво.

[mkmarinov]

Не беше ли 12 клас? Това горното идва от
[tex]F_n=F_{n-1}+F_{n-2}[/tex]
Характеристичното уравнение на рекурентното отношение е
[tex]r^2=r+1[/tex], с корени [tex]r_1=\varphi, r_2=1-\varphi[/tex], където [tex]\varphi = \frac{1+\sqrt{5}}{2}[/tex], откъдето следва, че
[tex]F_n=a\varphi^n+b(1-\varphi)^n[/tex]
Остава да замести [tex]n[/tex] с някои лесни за смятане стойности (например 0 и 1) и да намерим коефициентите a и b.

Иначе и индукцията ще ти свърши работа, но за 12 члена изглежда като много писане .

[Mr.G{}{}Fy]

11 клас съм.И сме учили рекурентните зависимости,но не съм виждал как се изкарва зависимост между редицата на Фибоначи.
П.П.Иначе,според мен, решението ти е по-хубаво от авторовото.

[kucheto]

...но не съм виждал как се изкарва зависимост между редицата на Фибоначи.

Тук е подробно обяснено: viewtopic.php?f=71&t=4043

[strangerforever]

Всяко просто число от вида [tex]2^k + 1[/tex] е число на Ферма и единствените прости числа са при [tex]k = 2^0, 2^1, 2^2, 2^3, 2^4[/tex]. Само 1, 2 и 8 принадлежат на редицата на Фибоначи.

[kucheto]

Всяко просто число от вида [tex]2^k + 1[/tex] е число на Ферма и единствените прости числа са при [tex]k = 2^0, 2^1, 2^2, 2^3, 2^4[/tex]. Само 1, 2 и 8 принадлежат на редицата на Фибоначи.

Доколкото знам Ферма е формулирал хипотезата, че всички числа от този вид са прости, но по-късно се оказало, че не само греши, но и че за [tex]k\ge 5[/tex] не са открити други такива прости числа. Но не е доказано и противното, така че това е открит проблем. Линк по темата: http://en.wikipedia.org/wiki/Fermat_number

[Mr.G{}{}Fy]

Точно щях да искам доказателство ,че само тези са прости.Ойлер е доказал за [tex]2^{2^{5}}[/tex],че се дели на 641.Или поне мисля,че беше Ойлер.А как да докажем,че 2^{2^{4}} не е от Фибоначевските числа. Може би от някоя от горните зависимости?Ако може само някой да посочи коя и аз ще си го докарам.

[kucheto]

Точно щях да искам доказателство ,че само тези са прости.Ойлер е доказал за [tex]2^{2^{5}}[/tex],че се дели на 641.Или поне мисля,че беше Ойлер.А как да докажем,че 2^{2^{4}} не е от Фибоначевските числа. Може би от някоя от горните зависимости?Ако може само някой да посочи коя и аз ще си го докарам.

Може да си го пресметнеш. Наистина [tex]2^{16}=65536,\ F_{24}=46368,\ F_{25}=75025:[/tex] http://bg.wikipedia.org/wiki/%D0%A7%D0% ... 1%87%D0%B8

[Mr.G{}{}Fy]

Ясно .Благодаря и за горния линк.