Kezdőlap


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 \| MathML
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

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 $p^{2}$ -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

\begin{matrix} (\binom{(k + 1) p}{p}) \equiv k + 1 (mod p) . \end{matrix}

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

p^{2}

-tel osztva ugyanannyi maradékot ad, a hányadosuk pedig egész szám, akkor az

p^{2}

-tel osztva 1-et ad maradékul. Vagyis, ha a

p

-vel nem osztható

a

b

x

egész számokra

a x \equiv b (mod p^{2})

és

a \equiv b (mod p^{2})

, akkor

x \equiv 1 (mod p^{2})

. Valóban, ha

a (x - 1) = a x - a

osztható

p^{2}

-tel, akkor

x - 1

is osztható

p^{2}

-tel. Ugyanígy látható, hogy ha

a

nem osztható

p

-vel, akkor

c_{1} ≢ c_{2} (mod p^{2})

esetén

a c_{1} ≢ a c_{2} (mod p^{2})

.
Legyen most

k

tetszőleges nemnegatív egész szám. Ekkor a

\begin{matrix} (k p + 1) (k p + 2) ... (k p + p - 1) \end{matrix}

szorzatot teljesen kibontva, abban ,,majdnem minden'' tag osztható lesz

p^{2}

-tel, azaz

\begin{matrix} (k p + 1) ... (k p + p - 1) \equiv (p - 1)! + k p (p - 1)! (\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{p - 1}) (mod p^{2}) . \end{matrix}

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ó

\begin{matrix} \frac{(p - 1)!}{1}, \frac{(p - 1)!}{2}, ..., \frac{(p - 1)!}{p - 1} \end{matrix}

számok is mind különböző maradékot adnak

p

-vel osztva, így

p > 2

miatt

\begin{matrix} (p - 1)! (\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{p - 1}) \equiv 1 + 2 + ... + (p - 1) = \frac{p (p - 1)}{2} \equiv 0 (mod p) . \end{matrix}

Ezért

\begin{matrix} (k p + 1) (k p + 2) ... (k p + p - 1) \equiv (p - 1)! (mod p^{2}), \end{matrix}

ahonnan az előbb látottak szerint:

\begin{matrix} (\binom{(k + 1) p}{p}) = \frac{(k + 1) p}{p} \cdot \frac{(k p + 1) (k p + 2) ... (k p + p - 1)}{(p - 1)!} \equiv (k + 1) \cdot 1 (mod p^{2}) . \end{matrix}

A bizonyított összefüggés szerint:

\begin{matrix} \sum_{i = 1}^{p} (\binom{i \cdot p}{p}) \cdot (\binom{(p - i + 1) p}{p}) \equiv \sum_{i = 1}^{p} i \cdot (p - i + 1) (mod p^{2}) . \end{matrix}

A kapott összeget a számtani sorozatok és a négyzetszámok összegképletének felhasználásával tovább alakítva:

\begin{matrix} \sum_{i = 1}^{p} i \cdot (p - i + 1) & = (p + 1) \sum_{i = 1}^{p} i - \sum_{i = 1}^{p} i^{2} = (p + 1) \frac{p (p + 1)}{2} - \frac{p (p + 1) (2 p + 1)}{6} = \\ = (p + 1) \frac{(3 p^{2} + 3 p) - (2 p^{2} + p)}{6} = \frac{p (p + 1) (p + 2)}{6} . \end{matrix}

\frac{p (p + 1) (p + 2)}{6}

hányados

p^{2}

-tel való osztási maradékát keresve elegendő

\frac{(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 = 6 k + 1

\begin{matrix} \frac{(p + 1) (p + 2)}{6} = \frac{(6 k + 2) (6 k + 3)}{6} = 6 k^{2} + 5 k + 1. \end{matrix}

Ezt

p = 6 k + 1

-gyel maradékosan osztva:

6 k^{2} + 5 k + 1 = k (6 k + 1) + 4 k + 1

, vagyis a maradék

4 k + 1

.
A második esetben, amikor

p = 6 k + 5

\begin{matrix} \frac{(p + 1) (p + 2)}{6} = \frac{(6 k + 6) (6 k + 7)}{6} = 6 k^{2} + 13 k + 7. \end{matrix}

Maradékosan osztva

p = 6 k + 5

-tel:

6 k^{2} + 13 k + 7 = (k + 1) (6 k + 5) + 2 k + 2

, a maradék

2 k + 2

.
Így

\frac{p (p + 1) (p + 2)}{6}

-nak a

p^{2}

-tel való osztási maradéka az első esetben

p (4 k + 1)

, a másodikban pedig

p (2 k + 2)

.
Tehát ha

p = 6 k + 1

alakú, akkor a

p

alapú számrendszerben az utolsó két számjegy

(4 k + 1)

és 0, ha pedig

p = 6 k + 5

alakú, akkor az utolsó két számjegy

(2 k + 2)

és 0.