от стария форум - биномни коефициенти

[martin123456]

Да се докаже, че [tex]{n \choose k}\equiv 0(mod p)[/tex] за [tex]\forall k=\{1,...,n-1\}[/tex], тогава и само тогава, когато [tex]n=p^{\alpha}[/tex], където [tex]\alpha \in\mathbb{N}[/tex].

[martin123456]

1) едната страна е очевидна
2) за к=1 се вижда, че [tex]p|n[/tex]. нека [tex]n[/tex] не е степен на [tex]p[/tex] и е [tex]n=p^at[/tex], [tex](p,t)=1[/tex].
разглеждаме [tex]{n \choose p^a}=\frac{n!}{p^a!(n-p^a)!}[/tex]
[tex]=\frac{(n-p^a+1)(n-p^a+2)\ldots n}{p^a!} = \frac{(p^at-p^a+1)(p^at-p^a+2)\ldots (p^at-p^a+p^a-1)(p^at-p^a+p^a)}{p^a!}[/tex]. всеки множител в числител е с вид [tex]p^at-p^a+s[/tex], [tex]s \in \{1,2,\ldots,p^a\}[/tex]. той се дели на [tex]p[/tex], ако [tex]p|s[/tex]. за произволен множител, който се дели на [tex]p[/tex], нека [tex]s=p^bk[/tex], [tex]b \in \{1,2,\ldots,a\}[/tex], [tex](k,p)=1[/tex]. значи степента на [tex]p[/tex] в него е степента на [tex]p[/tex] в [tex]p^b(p^{a-b}t-p^{a-b}+k)[/tex]. [tex]k[/tex] не се дели на [tex]p[/tex] и ако [tex]a \ne b[/tex], то изразът в скобите не се дели на [tex]p[/tex]. ако [tex]a=b[/tex], то [tex]k=1[/tex] и множителят е [tex]t-1+1[/tex], което знаем не се дели на [tex]p[/tex]. следователно степента на всеки множител е [tex]p^b[/tex]. в числителя степента на [tex]p[/tex] се дава от степента на [tex]1*2*\ldots(p^a-1)p^a=p^a![/tex]. в знаменателят тя също е толкова, значи [tex]p[/tex] не дели израза.

[flavia]

Хубаво решение, благодаря.

[Baronov]

Със същия аргумент, ако [tex]p^a<n<p^{a+1}[/tex], то [tex]n \choose p^a[/tex] не се дели на p.

[martin123456]

ще го видя

[martin123456]

само че имаме и други неща в условието