Złożoność liczby

[wiku94]

Wykazać złożoność liczby \(\displaystyle{ 2^{51}+ 1}\) (czyli wykazać, że \(\displaystyle{ 2^{51}+ 1}\) nie jest liczbą pierwszą)

[Kartezjusz]

\(\displaystyle{ 51=3 \cdot 17}\)

[Kaf]

Ukryta treść:    

Zauważ, że \(\displaystyle{ 2 \equiv -1 \pmod 3}\) zatem \(\displaystyle{ 2^{51} +1 \equiv ... \pmod 3}\)

[Chewbacca97]

Liczba postaci \(\displaystyle{ 2 ^{n} +1}\) jest liczbą pierwszą, wtedy i tylko wtedy gdy \(\displaystyle{ n=2 ^{k}, k \in \NN ^{+}}\). Liczbę tej postaci nazywa się liczbą pierwszą Fermata.

Czy liczba \(\displaystyle{ 2 ^{51} +1}\) jest liczbą pierwszą? Oczywiście, że nie. Liczby \(\displaystyle{ 51}\) nie można zapisać w postaci \(\displaystyle{ 2 ^{k}}\).

[Kaf]

To twierdzenie jest fałszywe. Jeżeli liczba tej postaci jest pierwsza, to \(\displaystyle{ n}\) jest potęgą dwójki, ale twierdzenie odwrotne nie zachodzi (\(\displaystyle{ 2^{2^5}+1=641 \cdot 6700417}\))

[Chewbacca97]

Faktycznie, wtopa. To co napisałem działa dla \(\displaystyle{ k=\left\{ 0,1,2,3,4\right\}}\). A dalej jest zgrzyt.

[Zahion]

Skorzystaj ze wzoru \(\displaystyle{ a^{2n+1}+b^{2n+1}=(a+b)(a^{2n}-...+b^{2n})}\), żeby wykazać podzielność tej liczby przez \(\displaystyle{ 3}\), albo z modulo.