Задача от Созопол 2013

[alexander_ivanov]

Да се докаже, че съществуват безброй много числа [tex]n[/tex] , които да имат поне три прости делителя и да е изпълнено [tex]n|2^n-8[/tex]

[georgi111]

Лесно се вижда, че [tex]n=15p[/tex], където [tex](2,p)=(3,p)=(5,p)=1[/tex], където [tex]p[/tex] е просто върши работа А защо върши ? Защото [tex]2^n-8=2(2^{5p-1}-1)(2^{10p}+2^{5p+1}+4)[/tex] се дели на [tex]3.5.p[/tex] поради факта,че от Ферма имаме [tex](2,5p)=1, 2^{5p-1} \equiv 1(mod 5p)[/tex] и [tex]2^{10p}+2^{5p+1}+4[/tex] се дели на 3([tex]5p+1[/tex]-четно, защо ?)

[pal702004]

[tex]2^{5p-1}\equiv 1 \pmod {5p}[/tex]

Това не е вярно.

[georgi111]

Оффф очевидно че не е вярно

[georgi111]

По скоро нека[tex]n=3pq[/tex], където [tex](2,p)=(2,q)=(3,p)=(3,q)=1[/tex], където [tex]p,q[/tex] са прости върши работа. Тогава [tex]2^n-8=(2^{pq}-2)(4^{pq}+2^{pq+1}+4)[/tex] се дели на [tex]3.p.q[/tex] поради факта,че от Ферма имаме [tex]2^p \equiv 2(mod p), 2^q \equiv 2(mod q)[/tex] и [tex]4^{pq}+2^{pq+1}+4[/tex] очевидно се дели на 3. От първото имаме [tex], 2^{pq} \equiv 2(mod p), 2^{pq} \equiv 2(mod q)[/tex] и понеже [tex](p,q)=1[/tex] имаме [tex]2^{pq} \equiv 2(mod pq)[/tex]. Така доказахме, че [tex]n=3pq[/tex] дели [tex]2^n-8[/tex]

[alexander_ivanov]

[tex]2^{pq} \equiv 2(mod p), 2^{pq} \equiv 2(mod q)[/tex]

Това не е вярно! [tex]p=5, q=7[/tex]

[pal702004]

След полагане [tex]n=3k[/tex] се получава условие [tex]2^{k-1} \equiv 1 \pmod k[/tex], където k е съставно. Задачата е еквивалентна на това да се докаже, че псевдопростите числа на Ферма с основа 2 са безброй много. Тук се доказава, естествено, чрез Мерсеновите числа.
http://number.subwiki.org/wiki/Mersenne_number_for_prime_or_Poulet_implies_prime_or_Poulet