Prímszám-e 1000 * googolplexplex + 3?

A legnagyobb ismert prímszám 22 millió számjegyből áll. Az általad leírt szám meg ugye googolplex+4 számjegyből áll. Az egyszerű oszthatósági szabályok (2,4,8,…; 3,9; 5,10) alapján ezekkel nem osztható. A 11-el, 13-al, 17-el, 19-el, 29-el, 31-el, 37-el való oszthatósághoz meg googolplex számú szorzást, összeadást kellene elvégezni, ami egy cseppet időigényes lenne.

Tehát amennyire tudom ez sem nem cáfolható, sem nem bizonyítható. Viszont a prímszámok eloszlása miatt erősen valószínű, hogy nem prímszám.

Nem, mert osztható 13-al.

(1000*10^k+3) mod 13 ahol k € {0,1,2,3, ...}

Ekkor az így konstruált S sorozat:

S=[2, 6, 7, 4, 0, 12, 2, 6, 7, 4, 0, 12, 2, 6, 7, 4, 0, 12, 2, 6 ...] periódikusan ismétlődő sorozat.

Ahol S(4+6*n)=0 minden n € {0,1,2,3 ...}-re

Vagyis ha a k mod 6 = 4 akkor (1000*10^k+3) mod 13 = 0.

ha k értékét a h={10,100,1000,10000, ...} halmazból veheti fel akkor minden k-ra igaz hogy k mod 6 = 4. Mivel 10^10^100 eleme h-nak az eddigiekből beláttuk, hogy 1000 * googolplexplex + 3 osztható 13-al.

Semmi, ok, felfogtam.

(Miért nem lehet törölni saját hozzászólást 10 percen belül, ha még nem írt rá senki újabbat...)

Egyébként a kérdés feltevés miatt biztos, hogy nem prímszám, hiszen azt bizonyítani egy ekkora számról, hogy prím az nagyon nehéz feladat, hiszen nincs jobb módszerünk, mint minden lehetséges osztót megvizsgálni, míg azt hogy nem prím egyszerű, hiszen csak egy osztót kell találni.

Így számolás nélkül biztosan tudhatjuk, hogy nem prím, különben a kiadott feladatot nem lehetne megoldani.

"Miért nem lehet törölni saját hozzászólást 10 percen belül"

Hogy mindenki láthassa a hibát és lehetőség legyen belekötni.

A titkárnő is mindig nyomtatás után a papíron fedezi fel hogy rossz a margó... :)

@11:37

Ez nem egészen igaz, mivel "míg azt hogy nem prím egyszerű, hiszen csak egy osztót kell találni", ez is nagyon nehéz feladat lehet. Az RSA titkosítás is ezen alapszik.

Eldönteni egy számról, hogy nem prím ahhoz nem feltétlen kell osztót találni. Vagyis a prímfaktorizáció nehezebb feladat mint a prímtesztelés. Vannak rá Monte Carlo algoritmusok (is).

"Így számolás nélkül biztosan tudhatjuk, hogy nem prím, különben a kiadott feladatot nem lehetne megoldani."

Ha iskolai feladat akkor elfogadom, hogy ez igaz. Viszont a számelméletben lehetnek olyan kérdések amit a legbriliánsabb matek zsenik sem tudják megoldani évszázadok alatt sem.

Mj.:

Többet ésszel mint erővel. Egy ekkora számon pl, ha elkezdenénk próbaosztás végrehajtani géppel, annyi memóriaigénye lenne, hogy bugába dőlne az egész.

"Az RSA titkosítás is ezen alapszik." - igen, de ott direkt marhanagy prímeket szoroznak össze. Ha megfogsz egy random 20-30 jegyű számot, szinte biztos, hogy 1000 alatt lesz prímtényezője, tehát egy számítógép egy szempillantás alatt megállapítja, hogy nem prím.

"Egy ekkora számon pl, ha elkezdenénk próbaosztás végrehajtani géppel, annyi memóriaigénye lenne, hogy bugába dőlne az egész." - a prímtényezők keresésének nincs memória-, csak processzorigénye.

"Ha megfogsz egy random 20-30 jegyű számot, szinte biztos, hogy 1000 alatt lesz prímtényezője"

Vagy nem, bár több esélye van annak hogy így legyen, de a nem-nek az esélye sem olyan kicsi, hogy ne tudnám reprodukálni bármikor néhány próbálkozással (csak hasamra ütött számokkal). Régen sok ilyen tesztet csináltam.

"a prímtényezők keresésének nincs memória-, csak processzorigénye"

Ez úgy szokott történni, hogy az osztót, az osztandót és a hányadost a memóriában tároljuk. Lehet okoskodni, hogy meg lehetne oldani, hogy ne tároljuk mivel úgy sem használjuk fel a konkrét értékét, de annyi a lényeg amit mondtam hogy többet ésszel mint erővel.