Kezdőlap


Cím:	Egy számelméleti feladat
Szerző(k):	Bíró András , Sustik Mátyás
Füzet:	1988/május, 197 - 201. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Dolgozatunk előzménye a következő feladat volt: bizonyítandó, hogy ha $p$ prím, akkor $[(\binom{3 p}{p}) - 3]$ osztható $p^{2}$ -tel. Ennél kicsit többet és némileg általánosabb összefüggést sikerült megmutatnunk, ezt ismertetjük a továbbiakban.

Tétel: Ha p 3-nál nagyobb prímszám, akkor

[(\binom{a p}{b p}) - (\binom{a}{b})]

osztható

p^{3}

-nal.
A bizonyítás első részét kombinatorikus úton végezzük. Tekintsük az

1

2

...

a p

számokat. Osszuk ezeket

a

darab "blokkra''; az első álljon az

1,2, ..., p;

a második a

(p + 1)

(p + 2)

...

2 p

;

...

a

-adik az

(a - 1) p + 1

(a - 1) p + 2

...

a p

számokból. Vegyünk a fenti

a p

darab szám közül

b p

-t úgy, hogy ne

b

teljes blokkot válasszunk ki. Az ilyen "telítetlen'' kiválasztások száma éppen

[(\binom{a p}{b p}) - (\binom{a}{b})]

, mivel

b p

darab szám kiválasztása

(\binom{a p}{b p})

- féleképpen történhet, és ezek között

(\binom{a}{b})

kiválasztás áll

b

darab teljes blokkból. A telítetlen kiválasztásokat most olyan osztályokba soroljuk, melyeknek elemszáma ‐ vagy több ilyen osztály elemszámának az összege ‐

p^{3}

-nal osztható, amiből a bizonyítandó állítás nyilván következik.
Nevezzük forgatásnak a következő műveletet: ha egy blokkban a kiválasztott számok

c_{1} < c_{2} < ... < c_{k} (0 < k < p)

, akkor ebből a blokkból a művelet után

(c_{1} + 1)

(c_{2} + 1)

...

(c_{k} + 1)

szerepeljen az új kiválasztásban, a további blokkokat, illetve az azokból kiválasztott számokat pedig hagyjuk változatlanul. (Ha

c_{k}

a blokk legnagyobb eleme, akkor helyette vegyük a legkisebbet.) Tartozzanak ezek után egy osztályba azok a kiválasztások, amelyek több-kevesebb ‐ nem szükségképpen ugyanazon a blokkon végrehajtott ‐ forgatással egymásba vihetők. A telítetlen kiválasztások így kapott osztályai közül nyilván semelyik kettőnek nincs közös eleme. (Így ekvivalenciarelációt definiálunk a telítetlen kiválasztások halmazán. A szerk.)
A fenti műveletet szemléletessé tehetjük, ha az

a p

darab számot

a

darab szabályos

p

-oldalú sokszög csúcsaihoz írjuk és a csúcsokban megjelöljük a

b p

darab kiválasztott számot. Egy forgatás így az egyik sokszögön levő jelek elforgatását jelenti

\frac{2 π}{p}

szöggel (ábra).

Azt állítjuk, hogy ha egy ‐ nem üres, nem teli ‐ blokk kivételével rögzítjük az összes többi elemet, akkor egy adott kiválasztásból az adott blokk forgatásaival éppen

p

darab különböző kiválasztás érhető el. Többet nem kaphatunk, hiszen egy blokkon belül

p

darab elforgatás önmagába viszi a blokkot és így az adott kiválasztást. Így csak azt kell megmutatnunk, hogy

p

-nél kevesebb elforgatás az eredetitől különböző állapotra vezet. Tegyük fel, hogy állításunkkal ellentétben egy nem üres, nem teli blokkot

r

számú elforgatás

(0 < r < p)

önmagába visz. Tekintsük a blokk egy kiválasztott

c_{1}

elemét. Az

r

darab elforgatás ezt olyan

c_{2}

számba viszi, amelyre

c_{2} - c_{1} \equiv r (mod p),

és

c_{2}

maga is kiválasztott. A fenti gondolatmenetet

c_{2}

-re, és tovább alkalmazva a kiválasztott számoknak olyan

c_{3}

c_{4}

...

c_{p}

sorozatához jutunk, amelyre

c_{k} - c_{1} \equiv (k - 1) r (mod p)

. Ezek a számok mind különbözők, hiszen

c_{i}

és

c_{j}

(i < j)

csak akkor lehet egyenlő, ha

(j - i) r

osztható

p

-vel

(0 = c_{i} - c_{j} \equiv (j - i) r (mod p)) .

Ez viszont nem fordulhat elő, hiszen

j, i < p

miatt

j - i < p

, továbbá

r < p

, és

p

prímszám. Így viszont a blokk minden eleme kiválasztott, amit pedig kizártunk. Ezzel a kimondott állítást igazoltuk.
Vegyük most szemügyre az olyan osztályokat, amelyek kiválasztásai legalább három nem üres, nem teli blokkot tartalmaznak. Az ilyen osztályok elemszáma ‐ figyelembe véve, hogy a nem üres, nem teli blokkokat egymástól függetlenül forgathatjuk

p

helyzetbe ‐

p

-nek legalább a harmadik hatványával osztható.
Olyan kiválasztás, melyben a nem üres, nem teli blokkok száma 1, nem létezik, hiszen a kiválasztott elemek száma

p

-vel osztható.
Az eddig figyelembe nem vett osztályok mindegyike tehát pontosan két nem üres, nem teli blokkot tartalmaz. Egyesítsük most azon osztályokat, amelyekre ez a két blokk ugyanaz, továbbá a teli blokkok is azonosak. Ha az egyik blokkban

k

, akkor a másikban

(p - k)

kiválasztott elem van, így ebben az egyesítésben

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

darab kiválasztás szerepel.
Tételünk bizonyításához most már elegendő megmutatnunk, hogy ez az összeg is osztható

p^{3}

-nal. (Maga az összeg egyébként

(\binom{2 p}{p}) - (\binom{2}{1}),

hiszen a rögzített két blokkban

2 p

darab szám közül választunk ki

p

darabot úgy, hogy a kiválasztott számok nem alkotnak teljes blokkot. Így tételünk speciális esetével állunk szemben:

a = 2 és b = 1.)

(\binom{p}{k}) = \frac{p!}{k! (p - k)!}

osztható

p

-vel, hiszen a számláló osztható vele, a nevező nem. Ezért összegünk minden tagja osztható

p^{2}

-tel. A továbbiakban tehát annak bizonyítására szorítkozhatunk, hogy

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

osztható

p

-vel.
Ha megmutatjuk, hogy

\begin{matrix} \frac{(\binom{p}{k})}{p} \equiv \frac{(\binom{p}{m})}{p} (mod p), (1 ≦ k, m ≦ p - 1) \end{matrix}

(1)

akkor és csak akkor teljesül, ha

k = m,

vagy

k + m = p;

‐ tehát ha a számlálók egyenlők ‐ továbbá, hogy

\begin{matrix} \frac{(\binom{p}{k})}{p} \equiv - \frac{(\binom{p}{m})}{p} (mod p) \end{matrix}

(2)

sosem állhat, akkor a

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

számok

p

-vel osztva az

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

maradék párok mindegyikének pontosan az egyik tagját állítják elő, s azt kétszer. Ez esetben pedig

\begin{matrix} \sum_{k = 1}^{p - 1} {[\frac{(\binom{p}{k})}{p}]}^{2} \equiv 2 [1^{2} + 2^{2} + ... + {(\frac{p - 1}{2})}^{2}] = 2 \frac{\frac{p - 1}{2} \cdot \frac{p + 1}{2} \cdot p}{6} (mod p), \end{matrix}

s ez utóbbi

p > 3

miatt valóban osztható

p

-vel.

Az (1), (2) kongruenciák vizsgálatához először egy segédtételt igazolunk:
ha

p

prím, és

k < p

nemnegatív egész, akkor

\begin{matrix} k! (p - k - 1)! + {(- 1)}^{k} \end{matrix}

osztható

p

-vel.
A bizonyítás a

k

-ra vonatkozó teljes indukcióval történik.

k = 0

-ra Wilson tételét kapjuk.^{$^{*}$} Tegyük fel, hogy

k

-ra már beláttuk az állítást, azaz :

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

Most

p - k - 1 \equiv - (k + 1) (mod p)

felhasználásával:

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

ahonnan

(- 1)

-gyel szorozva

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

Ez pedig éppen a

(k + 1)

-re vonatkozó állításunk, így a segédtételt beláttuk.
Lássuk tehát, hogy

\frac{(\binom{p}{k})}{p} \equiv \frac{(\binom{p}{m})}{p}

(mod

p

) mikor állhat fönn.

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

k! (p - k)! m! (p - m)!

-sal szorozva és

(p - 1)

!-sal osztva (ezek relatív prímek

p

-hez, így ekvivalens átalakításokat végeztünk):

\begin{matrix} m! (p - m)! \equiv k! (p - k)! (mod p) . \end{matrix}

Segédtételünket felhasználva ez akkor és csak akkor igaz, ha

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

m

és

k

azonos paritásúak, akkor innen

k = m

, ha pedig különböző paritásúak, akkor

k + m = p

adódik.

(0 < k, m < p;