Sprawdzić czy dana liczba jest liczbą pierwszą.

[Ridos]

Witam.
Znam sposób w stylu \(\displaystyle{ p \le \sqrt{n}}\)
Ale jak mam sprawdzić czy \(\displaystyle{ 2 ^{20} +1}\) jest liczbą pierwsza?
Sprawdzanie wszystkich dzielników \(\displaystyle{ 2 ^{10}}\) jest bardzo czasochłonne a wręcz niewykonalne bez komputera... Proszę o podpowiedź jak się za to zabrać. Komputer pokazał, że nie jest to liczba pierwsza bo ma dzielniki 1, 17, 61681, 1048577. Tylko jak to sprawdzić bez kompa?

[kerajs]

\(\displaystyle{ (2^4)^5+1=(2^4+1)\left[ (2^4)^4-(2^4)^3+(2^4)^2-(2^4)+1\right]}\)

[Premislav]

\(\displaystyle{ 2^4 \equiv -1\pmod{17}\\2^{20}=(2^4)^5\equiv (-1)^5 \pmod{17}\\2^{20}+1\equiv 0\pmod{17}}\)
czyli ta liczba dzieli się przez \(\displaystyle{ 17}\) (i jest oczywiście większa niż \(\displaystyle{ 17}\)), a więc nie jest pierwsza.

[szw1710]

Premislav, ale to rozwiązanie przy wiedzy, że ta liczba jest podzielna przez \(\displaystyle{ 17}\) - sprawdzasz tylko tę podzielność. Pytanie było nie o rozkład na czynniki, ale o łatwą możliwość sprawdzenia. To widać we wpisie kerajs-a.

[Ridos]

Cieszę się, że tak szybko odpisaliście, dziękuję kerajs, że to rozpykałes, ale nie mogę tego zobaczyć, da radę to bardziej wyjaśnić?

[szw1710]

To bardzo proste. Każdą sumę postaci \(\displaystyle{ x^{2n+1}+y^{2n+1}}\) (gdzie \(\displaystyle{ n\in\NN}\)) łatwo rozkłada się na czynniki. Wszędzie możesz znaleźć odpowiedni wzór. A ze szkoły powinieneś znać wzór na \(\displaystyle{ x^3+y^3=\dots}\).

Tak więc złożona jest np. liczba \(\displaystyle{ 2^{707}+1}\). Dlaczego? Znajdź przynajmniej jeden z jej dzielników. Znajdź też w podobny sposób dzielnik liczby \(\displaystyle{ 2^9+3^{12}}\).

[Ridos]

Po dłuższym przeanalizowaniu wydaje mi się szw1710, że kerajs zrobił to samo co Premislav. kerajs pokazał że \(\displaystyle{ (2^4+1)}\) wynosi 17 i to co jest w nawiasie kwadratowym jest po prostu wielokrotnością 17, więc to samo co pokazał Premislav z kongruencją. Tylko w jakiś magiczny sposób trzeba wpaść na to jak to rozłożyć, żeby akurat znaleźć dzielnik danej ogromnej liczby. Niestety szw1710 nie mam pojęcia do czego odnosi się twoja wskazówka z rozłożeniem sumy na czynniki Szczególnie, że ja tam nigdzie nie widzę sumy postaci \(\displaystyle{ x^{2n+1}+y^{2n+1}}\) i do czego ma się wzór na sumę sześcianów? Przepraszam, ale ja po prostu tego nie widzę. Nie ma jakiegoś schematu postępowania jak na przykład w kongruencji czy Twierdzeniu phi Eulera czy małym twierdzeniu Fermata?

[Cytryn]

Podobna zależność: \(\displaystyle{ 2^p - 1}\) jest dzielnikiem \(\displaystyle{ 2^{pq}-1}\), więc liczby takiej postaci nie mogą być pierwsze (\(\displaystyle{ p, q > 1}\)).

[Jan Kraszewski]

Niestety szw1710 nie mam pojęcia do czego odnosi się twoja wskazówka z rozłożeniem sumy na czynniki

Jeśli umiesz rozłożyć liczbę (będącą w tym wypadku sumą) na czynniki, to nie jest ona pierwsza.

Szczególnie, że ja tam nigdzie nie widzę sumy postaci \(\displaystyle{ x^{2n+1}+y^{2n+1}}\)

Przecież kerajs Ci napisał:

\(\displaystyle{ 2^{20}+1=16^5+1^5.}\)

A tę sumę, zgodnie z uwagą szw1710, możesz rozłożyć na czynniki.

i do czego ma się wzór na sumę sześcianów?

To jest szczególny przypadek wzoru, o którym mówi szw1710 - dla \(\displaystyle{ n=1}\). Chodzi o to, że możesz go znać i przez analogię spróbować znaleźć/wyprowadzić ogólny wzór.

Dla naszych potrzeb wystarcza wiedza, że

\(\displaystyle{ x^{2n+1}+y^{2n+1}=(x+y)\cdot \mbox{cośtamcośtam}.}\)

JK

[szw1710]

Może powinienem pisać na zupełnie niskim poziomie. Mój wpis wymagał jakiejś tam kultury matematycznej (nie mylić z ogładą). Czy można jakąś kulturę matematyczną zakładać? A jeśli nie, to może przynajmniej aktywne podejście do dawanych wskazówek.