Mennyi 3880131^11114449 : 38417 osztás maradéka?

a ^ b ≡ a(mond n), vagyis a^b osztási maradéka n-el egyenlő a osztási maradékával n-el.

Vagyis:

Csak annyit kell csinálnod, hogy kiszámold:

3880131: 38417 osztás maradékát

Van egy számunk, aminek a maradékát keressük. a:b = n és maradt az m. (Jelen esetben 3880131:38417 = 101 és maradt 14). (Hagyományos jelöléssel: a mod b = m)

Ugye a számot fel lehet írni így: a=(n*b+m). Ennek a négyzete:

a^2 = (n*b + m)^2 = (n*b)^2 + 2(n*b)*m + m^2

A köbe:

a^3 = (n*b + m)^3 = (n*b)^3 + 3(n*b)^2*m + 3(n*b)*m^2 + m^3

Az utolsó tag kivételével minden tag (n*b) egész számú többszöröse, hiszen n is és m is egész, így b egész számú többszöröse. Ezen tagok b-vel való osztásának maradéka tehát nulla. Az egész összeg maradéka tehát az utolsó tag maradéka.

3880131^11114449 mod 38417 = (101*38417 + 14)^11114449 mod 38417 = 14^11114449 mod 38417

Innen kicsit elakadt a tudományom, fogtam hát, felírtam 14 első pár hatványát és megnéztem a 38417-el képzett maradékot:

14^0 mod 38417 = 1

14^1 mod 38417 = 14

14^2 mod 38417 = 196

14^3 mod 38417 = 2744

14^4 mod 38417 = 38416

14^5 mod 38417 = 38403

14^6 mod 38417 = 38221

14^7 mod 38417 = 35673

14^8 mod 38417 = 1

14^9 mod 38417 = 14

14^10 mod 38417 = 196

Aham, tehát ciklikusság van a maradékokban. 14^11114449 mod 38417 = 14^(11114449 mod 8) mod 38417 = 14^1 mod 38417 = 14

Tehát 3880131^11114449 mod 38417 = (3880131 mod 38417)^(11114449 mod 8) mod 38417 = 14^1 mod 38417 = 14

Tévedtem.

a^p = a(mod p)

> És az "Aham, tehát ciklikusság van" az tudományosan korrekt momentum a levezetésben, vagy ezt egyelőre nevezzük csak Süsü-féle sejtésnek, amelyet jövő órára kis ötösért lehet bizonyítani?

Nem korrekt, mint ahogy a hangnemed sem. A kritikát tehát elfogadom, de a hangnemet viszont már nem annyira. A korrekt levezetés hiánya igaz, de az összefüggés igazságtartamáról ez nem mond el semmit. Az összefüggés, a ciklikusság fennáll, attól függetlenül, hogy korrekten levezettem-e vagy sem. Az feladat megoldásában az adott pontig használt módszer megértése esetén szerintem ez az összefüggés minimum intuitív módon triviális kell, hogy legyen, de álljon itt egy korrekt levezetés.

Legyen a = (x*n + k) alakban, ahol x és k egész szám, valamint k<n.

( Ebből k = a mod n )

Legyen b = (y*n + l) alakban, ahol y és l egész szám, valamint l<n.

( Ebből l = b mod n )

Ekkor a*b = (x*n + k) * (y*n + l) = x*n*y*n + x*n*l + y*n*k + l*k = n*(x*y*n + x*l + y*k) + l*k

A kifejezés első része n-el osztható, hiszen minden változó egész szám. Tehát n*(x*y*n + x*l + y*k) mod n = 0. A maradékot tehát l*k adja. Ebből:

a*b mod n = l*k mod n = ((a mod n) * (b mod n)) mod n.

Jó, most nézzünk egy olyan esetet, ahol a^s mod n = 1.

Ekkor

a^(2*s) mod n = (a^s * a^s) mod n = ((a^s mod n) * (a^s mod n)) mod n = (1*1) mod n= 1

a^(3*s) mod n = (a^s * a^(2*s)) mod n = ((a^s mod n) * (a^(2*s) mod n)) mod n = (1*1) mod n = 1

Ebből rekurzív módon következik, hogy ha a^s mod n = 1, akkor a^(g*s) mod n = 1, ahol g egész szám.

Jó, akkor nézzük meg a^(p+s*g) mod n-t:

a^(p+s*g) mod n = (a^p * a^(s*g) mod n = ((a^p mod n) * (a^(s*g) mod n)) mod n = ((a^p mod n) * 1) mod n = a^p mod n

Márpedig (p+s*g) mod s = p

Ilyen módon igazoltuk, hogy ha a^s mod n = 1, akkor

a^p mod n = a^(p mod s) mod n

Tehát a firtatott ciklikusság igazolva van. (Jelen példánkra vetítve s=8, azaz 14^8 mod 38417 = 1. Ebből fakadóan pl. 14^23 mod 38417 = 14^(23 mod 8) mod 38417 = 14^7 mod 38417.)

a^p = a mod p?

Tehát azt akarod mondani, hogy

2^3 = 2 mod 3

8 = 2

?

Sőt az összefüggésből adódóan bármelyik szám második hatványa kisebb, mint kettő?

Hiszen ha a^2 = a mod 2, akkor a kifejezés jobb oldala a maradék definíciójából fakadóan vagy 0 vagy 1…