Kezdőlap


Feladat:	F.3034	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Ehreth Imre , Lovász Zoltán , Puskás Zsolt , Solymos Róbert , Valkó Benedek
Füzet:	1995/március, 156 - 158. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Maradékos osztás, kongruenciák, Feladat
Hivatkozás(ok):	Feladatok: 1994/november: F.3034

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.

Mivel

\begin{matrix} \begin{matrix} (\binom{p^{m}}{p}) - p^{m - 1} = \frac{p^{m} (p^{m} - 1) ... (p^{m} - p + 1)}{p (p - 1) ... 2 \cdot 1} - p^{m - 1} = \\ = p^{m - 1} (\frac{(p^{m} - 1) ... (p^{m} - p + 1)}{(p - 1) ... 2 \cdot 1} - 1) = p^{m - 1} ((\binom{p^{m} - 1}{p - 1}) - 1), \end{matrix} \end{matrix}

az állítás azzal ekvivalens, hogy

(\binom{p^{m} - 1}{p - 1}) - 1 = \frac{(p^{m} - 1) ... (p^{m} - p + 1)}{(p - 1) ... 2 \cdot 1} - 1

osztható

p

-vel, azaz

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

Ezt a kongruenciát megszorozhatjuk a

p

-hez relatív prím

(p - 1)!

-sal:

\begin{matrix} (p^{m} - 1) ... (p^{m} - p + 1) \equiv (p - 1) ... 2 \cdot 1 (mod p) . \end{matrix}

A bal oldalon minden tényezőt

(p^{m} - p)

-vel (ami többszöröse

p

-nek) csökkentve, a kongruencia ekvivalens a

\begin{matrix} (p - 1) (p - 2) ... 2 \cdot 1 \equiv (p - 1) (p - 2) ... 2 \cdot 1 (mod p) \end{matrix}

azonossággal, vagyis igaz.

Megjegyzések. 1. Ha

p

páratlan, akkor

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

ezért

(\binom{p^{m} - 1}{p - 1}) - 1 = \frac{(p^{m} - 1) ... (p^{m} - p + 1)}{(p - 1) ... 2 \cdot 1} - 1

osztható

p^{m}

-mel. Ebből pedig az is következik, hogy

(\binom{p^{m}}{p}) - p^{m - 1}

osztható

p^{2 m - 1}

-nel.

Puskás Zsolt (Budapest, ELTE Apáczai Csere J. Gyak. Gimn., IV. o.t.)

2. Ha

p

páratlan, akkor az is igaz, hogy

(\binom{p^{m}}{p}) - p^{m - 1}

osztható

p^{2 m}

-nel.
A zárójelek felbontásával

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

A zárójelben levő törtek értékei egész számok, nem oszthatók

p

-vel és különböző maradékot adnak

p

-vel osztva, mert ha

\begin{matrix} \frac{(p - 1)!}{i} \equiv \frac{(p - 1)!}{j} (mod p), \end{matrix}

akkor

\begin{matrix} (p - 1)! \cdot j \equiv (p - 1)! \cdot i (mod p) \end{matrix}

és

j \equiv i

(mod p)

. Ezért

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

és így

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

Ebből pedig következik, hogy

(\binom{p^{m} - 1}{p - 1}) - 1

osztható

p^{m + 1}

-nel,

(\binom{p^{m}}{p}) - p^{m - 1}

pedig osztható

p^{2 m}

-nel.

Ehreth Imre (Bonyhád, Petőfi S. Gimn., IV. o.t.)