Kezdőlap


Feladat:	N.133	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bérczi Gergely , Braun Gábor , Frenkel Péter , Gerbicz Róbert , Gyenes Zoltán , Hegedűs Péter , Juhász András , Kun Gábor , Kutalik Zoltán , Lázár Zsófia , Lippner Gábor , Lukács László , Mátrai Tamás , Méder Áron , Megyeri Csaba , Pap Gyula , Pataki Péter , Prause István , Terpai Tamás
Füzet:	1997/október, 420 - 421. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Polinomok, Maradékos osztás, kongruenciák, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1997/március: N.133

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

\begin{matrix} f (x) = (x + 1) (x + 2) ... (x + p - 1) = x^{p - 1} + a_{p - 2} x^{p - 2} + ... + a_{1} x + a_{0} . \end{matrix}

Ezzel a jelöléssel

\begin{matrix} (\binom{2 p - 1}{p - 1}) - 1 = \frac{(p + 1) ... (2 p - 1) - 1 \cdot 2 \cdot ... \cdot (p - 1)}{(p - 1)!} = \frac{f (p) - f (- p)}{(p - 1)!} . \end{matrix}

Mivel

p

prím,

(p - 1)!

és

p^{3}

relatív prímek, ezért azt kell igazolnunk, hogy

\begin{matrix} f (p) - f (- p) = 2 (a_{1} p + a_{3} p^{3} + ... + a_{p - 2} p^{p - 2}) \end{matrix}

osztható

p^{3}

-nel, vagyis

a_{1}

osztható

p^{2}

-tel.
Az

f

polinom definíciója alapján

\begin{matrix} a_{1} = \sum_{k = 1}^{p - 1} \frac{(p - 1)!}{k} = \sum_{k = 1}^{\frac{p - 1}{2}} (\frac{(p - 1)!}{k} + \frac{(p - 1)!}{p - k}) = p \sum_{k = 1}^{\frac{p - 1}{2}} \frac{(p - 1)!}{k (p - k)} . \end{matrix}

Mivel

p

prím, minden

1 \leq k \leq p - 1

egészhez egyértelműen létezik egy olyan

1 \leq k' \leq p - 1

egész, amelyre

k' k \equiv 1 (mod p)

. (A

k'

számot

k

modulo

p

multiplikatív inverzének is nevezik.) A

k'

lehetséges értékei között az

1,2, ..., p - 1

számok mindegyike pontosan egyszer fordul elő. Ezért

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

és

\begin{matrix} \begin{matrix} 2 \sum_{k = 1}^{\frac{p - 1}{2}} \frac{(p - 1)!}{k (p - k)} = \sum_{k = 1}^{p - 1} \frac{(p - 1)!}{k (p - k)} \equiv - (p - 1)! \sum_{k' = 1}^{p - 1} k'^{2} = \\ = - (p - 1)! \frac{p (p - 1) (2 p - 1)}{6} \equiv 0 (mod p) . \end{matrix} \end{matrix}

Megjegyzések. 1. Wilson tétele szerint

(p - 1)! \equiv - 1 (mod p)

. Erre a tényre a megoldáshoz nincs szükség, de néhány kifejezés egyszerűbb alakba írható a segítségével.
2. Hasonló megoldás nyerhető a

\begin{matrix} 2 ((\binom{2 p - 1}{p - 1}) - 1) = (\binom{2 p}{p}) - 2 = \sum_{k = 1}^{p - 1} {(\binom{p}{k})}^{2} = p^{2} \sum_{k = 1}^{p - 1} {(\binom{p - 1}{k - 1})}^{2} \frac{1}{k^{2}} \end{matrix}

azonosságból is, felhasználva hogy

(\binom{p - 1}{k - 1}) \equiv {(- 1)}^{k - 1} (mod p)