Feladat: B.4251 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Ágoston Tamás ,  Cséke Balázs ,  Damásdi Gábor ,  Éles András ,  Janzer Olivér ,  Kovács Gergely ,  Márkus Bence ,  Mester Márton ,  Perjési Gábor ,  Somogyi Ákos ,  Strenner Péter ,  Szabó Attila ,  Weisz Ágoston ,  Weisz Gellért ,  Zsakó András 
Füzet: 2011/január, 19 - 21. oldal  PDF file
Témakör(ök): Feladat, Számjegyekkel kapcsolatos feladatok, Maradékos osztás, kongruenciák, Oszthatóság, "a" alapú számrendszer (a >1, egész szám)
Hivatkozás(ok):Feladatok: 2010/február: B.4251

Legyen p>3 prímszám. Határozzuk meg a
i=1p(ipp)((p-i+1)pp)
szám utolsó két számjegyét a p alapú számrendszerben.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. A szám utolsó két számjegye p alapú számrendszerben a szám p2-es maradéka. Ennek meghatározásához először megmutatjuk, hogy ha p prímszám, k pedig tetszőleges nemnegatív egész, akkor

((k+1)pp)k+1(modp).

Ennek belátásához szükségünk lesz a következő észrevételre: ha két p-vel nem osztható egész szám p2-tel osztva ugyanannyi maradékot ad, a hányadosuk pedig egész szám, akkor az p2-tel osztva 1-et ad maradékul. Vagyis, ha a p-vel nem osztható a, b, x egész számokra axb(modp2) és ab(modp2), akkor x1(modp2). Valóban, ha a(x-1)=ax-a osztható p2-tel, akkor x-1 is osztható p2-tel. Ugyanígy látható, hogy ha a nem osztható p-vel, akkor c1c2(modp2) esetén ac1ac2(modp2).
Legyen most k tetszőleges nemnegatív egész szám. Ekkor a
(kp+1)(kp+2)...(kp+p-1)
szorzatot teljesen kibontva, abban ,,majdnem minden'' tag osztható lesz p2-tel, azaz
(kp+1)...(kp+p-1)(p-1)!+kp(p-1)!(11+12+...+1p-1)(modp2).

Mivel (p-1)! nem osztható p-vel, és az 1,2,...,p-1 számok p-vel osztva mind különböző (nemnulla) maradékot adnak, azért a p-vel nem osztható
(p-1)!1,(p-1)!2,...,(p-1)!p-1
számok is mind különböző maradékot adnak p-vel osztva, így p>2 miatt
(p-1)!(11+12+...+1p-1)1+2+...+(p-1)=p(p-1)20(modp).
Ezért
(kp+1)(kp+2)...(kp+p-1)(p-1)!(modp2),
ahonnan az előbb látottak szerint:
((k+1)pp)=(k+1)pp(kp+1)(kp+2)...(kp+p-1)(p-1)!(k+1)1(modp2).

A bizonyított összefüggés szerint:
i=1p(ipp)((p-i+1)pp)i=1pi(p-i+1)(modp2).
A kapott összeget a számtani sorozatok és a négyzetszámok összegképletének felhasználásával tovább alakítva:
i=1pi(p-i+1)=(p+1)i=1pi-i=1pi2=(p+1)p(p+1)2-p(p+1)(2p+1)6==(p+1)(3p2+3p)-(2p2+p)6=p(p+1)(p+2)6.

A p(p+1)(p+2)6 hányados p2-tel való osztási maradékát keresve elegendő (p+1)(p+2)6-nak a p-vel vett maradékát meghatározni. Mivel p>3 prím, a 6-tal való osztási maradéka 1 vagy 5 lehet.
Az első esetben, amikor p=6k+1,
(p+1)(p+2)6=(6k+2)(6k+3)6=6k2+5k+1.
Ezt p=6k+1-gyel maradékosan osztva: 6k2+5k+1=k(6k+1)+4k+1, vagyis a maradék 4k+1.
A második esetben, amikor p=6k+5,
(p+1)(p+2)6=(6k+6)(6k+7)6=6k2+13k+7.
Maradékosan osztva p=6k+5-tel: 6k2+13k+7=(k+1)(6k+5)+2k+2, a maradék 2k+2.
Így p(p+1)(p+2)6-nak a p2-tel való osztási maradéka az első esetben p(4k+1), a másodikban pedig p(2k+2).
Tehát ha p=6k+1 alakú, akkor a p alapú számrendszerben az utolsó két számjegy (4k+1) és 0, ha pedig p=6k+5 alakú, akkor az utolsó két számjegy (2k+2) és 0.