Kezdőlap


Feladat:	F.3174	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Barát Anna , Bérczi Gergely , Gyenes Zoltán , Györkei Györgyi , Hangya Balázs , Jakabfy Tamás , Juhász András , Klausz Zoltán , Léka Zoltán , Lippner Gábor , Méder Áron , Megyeri Csaba , Pintér Dömötör , Prause István , Szalai-Dobos András , Székelyhidi Gábor , Szita István , Terék Zsolt , Terpai Tamás , Vaik Zsuzsanna , Várkonyi Péter , Zawadowski Ádám
Füzet:	1998/március, 157. oldal		PDF \| MathML
Témakör(ök):	Binomiális együtthatók, Legnagyobb közös osztó, Prímtényezős felbontás, Feladat
Hivatkozás(ok):	Feladatok: 1997/április: F.3174

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.

Legyen az $n$ prímtényezős felbontása $n = p_{1}^{α_{1}} p_{2}^{α_{2}} ... p_{t}^{α_{t}}$ . Tetszőleges $k \leq α_{j}$ és $1 \leq j \leq t$ -re

\begin{matrix} (\binom{n}{p_{j}^{k}}) = \frac{n}{p_{j}^{k}} \cdot \frac{n - 1}{1} \cdot \frac{n - 2}{2} \cdot ... \cdot \frac{n - (p_{j}^{k} - 1)}{p_{j}^{k} - 1} . \end{matrix}

Megmutatjuk, hogy

(\binom{n}{p_{j}^{k}})

nem osztható

p_{j}^{α_{j} + 1 - k}

-nal. Tegyük fel, hogy az egyik

\frac{n - i}{i}

tényező számlálója osztható

p_{j}^{v}

-vel. A

v

értéke nem lehet

α_{j}

vagy annál nagyobb, hiszen akkor

p_{j}^{α_{j}}

osztaná

(n - i)

-t és

n

-et, ezért

i

-t is, ami

1 \leq i \leq p_{j}^{k} - 1 \leq p_{j}^{α_{j}} - 1

miatt lehetetlen. Így

p_{j}^{v}

osztója

n

-nek is, emiatt pedig

i = n - (n - i)

-nek, a tört nevezőjének is. Ezért, ha az

\frac{n - 1}{1} \cdot \frac{n - 2}{2} \cdot ... \cdot \frac{n - (p_{j}^{k} - 1)}{p_{j}^{k} - 1}

törtet egyszerűsítjük, a kapott tört számlálója nem lesz

p_{j}

-vel osztható. Mivel

\frac{n}{p_{j}^{k}}

nem osztható

p_{j}^{α_{j} + 1 - k}

-nal, állításunkat igazoltuk. Speciálisan kapjuk, hogy

(\binom{n}{p_{j}^{α_{j}}})

nem osztható

p_{j}

-vel.
Jelölje az

(\binom{n}{1})

...

(\binom{n}{n - 1})

számok legnagyobb közös osztóját

m

. A fentiekből látható, hogy ha

n

nem prímhatvány, akkor

m

p_{1}

p_{2}

...

p_{t}

prímek egyikével sem osztható. Így, mivel

m

osztója

(\binom{n}{1}) = n

-nek,

m

értéke 1.
Legyen ezután

n = p^{α}

prímhatvány; nyilván ekkor

m = p^{β} \leq p^{α}

lehet csak. Az előbbi észrevételt

k = α - 1

-re alkalmazva kapjuk, hogy

β < α + 1 - (α - 1) = 2

, azaz

β \leq 1

. Másrészt tetszőleges

1 \leq l \leq p^{α} - 1

esetén

l = p^{w} \cdot l_{1}

, ahol

l_{1}

nem osztható

p

-vel és

w \leq α - 1

. Így

\begin{matrix} (\binom{n}{l}) = (\binom{p^{α}}{l}) = p \cdot p^{α - 1 - w} \cdot \frac{\frac{p^{α} - 1}{l - 1}}{l_{1}} . \end{matrix}

mivel

l_{1}

p

-hez relatív prím, a

\frac{\frac{p^{α} - 1}{l - 1}}{l_{1}}

hányados egész, ezért

(\binom{n}{l})

osztható

p

-vel. Tehát:

m = 1

, ha

n

nem prímhatvány, és

m = p

, ha

n

p

prímnek hatványa.

Megyeri Csaba (Nagykanizsa, Batthyány Lajos Gimn., IV. o.t.)