Sprawdzić czy dana liczba jest liczbą pierwszą.
-
- Użytkownik
- Posty: 9
- Rejestracja: 2 sty 2017, o 15:25
- Płeć: Mężczyzna
- Lokalizacja: Elbląg
- Podziękował: 6 razy
Sprawdzić czy dana liczba jest liczbą pierwszą.
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?
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?
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Sprawdzić czy dana liczba jest liczbą pierwszą.
\(\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.
czyli ta liczba dzieli się przez \(\displaystyle{ 17}\) (i jest oczywiście większa niż \(\displaystyle{ 17}\)), a więc nie jest pierwsza.
Re: Sprawdzić czy dana liczba jest liczbą pierwszą.
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.
-
- Użytkownik
- Posty: 9
- Rejestracja: 2 sty 2017, o 15:25
- Płeć: Mężczyzna
- Lokalizacja: Elbląg
- Podziękował: 6 razy
Re: Sprawdzić czy dana liczba jest liczbą pierwszą.
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ć?
Re: Sprawdzić czy dana liczba jest liczbą pierwszą.
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}}\).
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}}\).
Ostatnio zmieniony 6 cze 2017, o 08:58 przez szw1710, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 9
- Rejestracja: 2 sty 2017, o 15:25
- Płeć: Mężczyzna
- Lokalizacja: Elbląg
- Podziękował: 6 razy
Re: Sprawdzić czy dana liczba jest liczbą pierwszą.
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
- Użytkownik
- Posty: 405
- Rejestracja: 17 wrz 2016, o 17:04
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
- Pomógł: 46 razy
Re: Sprawdzić czy dana liczba jest liczbą pierwszą.
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}\)).
-
- Administrator
- Posty: 34281
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Sprawdzić czy dana liczba jest liczbą pierwszą.
Jeśli umiesz rozłożyć liczbę (będącą w tym wypadku sumą) na czynniki, to nie jest ona pierwsza.Ridos pisze:Niestety szw1710 nie mam pojęcia do czego odnosi się twoja wskazówka z rozłożeniem sumy na czynniki
Przecież kerajs Ci napisał:Ridos pisze:Szczególnie, że ja tam nigdzie nie widzę sumy postaci \(\displaystyle{ x^{2n+1}+y^{2n+1}}\)
\(\displaystyle{ 2^{20}+1=16^5+1^5.}\)
A tę sumę, zgodnie z uwagą szw1710, możesz rozłożyć na czynniki.
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.Ridos pisze: i do czego ma się wzór na sumę sześcianów?
Dla naszych potrzeb wystarcza wiedza, że
\(\displaystyle{ x^{2n+1}+y^{2n+1}=(x+y)\cdot \mbox{cośtamcośtam}.}\)
JK
Re: Sprawdzić czy dana liczba jest liczbą pierwszą.
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.