Биномни коефициенти и прости числа

[Гост]

Нека q и p са прости числа,такива че q[tex]\ge[/tex]p. Да се докаже, че pq дели [tex]{p+q \choose p}[/tex]-[tex]{q \choose p}[/tex]-1.

[pal702004]

В началото да докажем едно твърдение (сигурно е известно, но не и на мен): Ако $p$ е просто, то

${a \choose p} \equiv \left\lfloor \dfrac a p \right \rfloor \pmod p$

Доказателство:

${a \choose p}=\dfrac{a(a-1)(a-2)\ldots(a-p+1)}{1\cdot 2\ldots p}$

Както в числителя, така и в знаменателя се срещат всички остатъци по модул $p$, при това по веднъж, така че съществува точно еднно $i$ такова, че $p \mid (a-i)$ Или

${a \choose p}=\dfrac{a-i}{p}\cdot \dfrac{a(a-1)\ldots}{(p-1)!}$

Както в числителя, така и в знаменателя на втората дроб се срещат по веднъж всички остатъци от 1 до $p-1$, няма нули (всички множители са взаимнопрости с $p$), следователно числителя е равен на знаменателя и различен от нула по модул $p$ (По теоремата на Уилсън е $-1$, но това в случая не е от значение). Или

${a \choose p} \equiv \dfrac{a-i}{p}\cdot 1 \equiv \left\lfloor \dfrac a p \right \rfloor \pmod p$

Към задачата: При $p=q=2$ изразът е равен на $4$ и твърдението е вярно.

При нечетни $p=q$ се получава ${2p \choose p}-2=\dfrac{(2p)!}{p!\cdot p!}-2=\dfrac{(p+1)(p+2)\ldots 2p}{1\cdot 2\ldots p}-2=$

$=2\left(\dfrac{(p+1)(p+2)\ldots(2p-1)}{1\cdot 2\ldots(p-1)}-1\right)$

При дробта в скобките числителя е равен на знаменателя по модул $p^2$ - Броят на множителите е четен, групираме ги по двойки, на всяка двойка $i \cdot (p-i)$ от знаменателя съответства $(p+i)(2p-i)$ от числителя.

$(p+i)(2p-i)=2p^2+pi-i^2 \equiv i(p-i) \pmod {p^2}$

Така че изразът се дели на $p^2$

При $p<q$
1. По модул $p$: (От твърдението в началото)

${p+q \choose p}-{q \choose p}-1 \equiv \left\lfloor \dfrac {p+q}{p} \right \rfloor -\left\lfloor \dfrac {q}{p} \right \rfloor -1 \equiv 1+\left\lfloor \dfrac {q}{p} \right \rfloor -\left\lfloor \dfrac {q}{p} \right \rfloor -1 \equiv 0 \pmod p$

2. По модул $q$

${p+q \choose p}={p+q \choose q} \equiv 1 \pmod q$ (от твърдението)

${q \choose p}=\dfrac{q!}{p!(q-p)!} \equiv 0 \pmod q$ (числителя се дели на $q$, а знаменателя - не)

Така е изразът се дели и на $q$