kongruencja dla liczb pierwszych

[patryk00714]

Wykazać, że dla \(\displaystyle{ p \in \mathbb{P}}\) oraz \(\displaystyle{ n \in \mathbb{N}}\)

prawdziwa jest kongruencja:

\(\displaystyle{ {pn \choose p} \equiv n (\text{mod} p^2)}\).


Zacząłem tak:

\(\displaystyle{ {pn \choose p}=\frac{(pn)!}{p!(pn-p)!}=\frac{(pn-p)!(pn-p+1)(pn-p+2)...(pn-p+p)}{p!(pn-p)!}=\\=\frac{[p(n-1)+1][p(n-1)+2]...[p(n-1)+p]}{p!}}\)

teraz w liczniku pojawia się iloczyn: \(\displaystyle{ (x+1)(x+2)...(x+p) \quad x=p(n-1)}\)

zapewne, jakoś trzeba go przekształcić tak, aby przy każdym składniku po wymnożeniu było co najmniej \(\displaystyle{ np^2}\), bo wówczas teza będzie ok.

Pomożecie?

[Zordon]

\(\displaystyle{ x+p=np}\)
Można teraz skrócić:

\(\displaystyle{ n\frac{(x+1)(x+2)...(x+p-1)}{(p-1)!}}\)

Pozostaje udowodnić, że:
\(\displaystyle{ (x+1)(x+2)...(x+p-1)\equiv (p-1)! \pmod{p^2}}\)

edit: może jeszcze jedna wskazówka, to po lewej można sobie wyobrażać jako wielomian zmiennej \(\displaystyle{ x}\), interesuje nas tylko wyraz liniowy \(\displaystyle{ ax+b}\), gdyż \(\displaystyle{ x^2\equiv 0\pmod{p^2}}\)

[Zahion]

Dodam, że indukcyjnie też powinno się udać.

[patryk00714]

Dowód indukcyjny przeprowadziłem ze względu na \(\displaystyle{ p}\) przy ustalonym \(\displaystyle{ n}\).

Bardziej interesują mnie dowody nieindukcyjne, są ciekawsze

[Zordon]

nie da się udowodnić indukcyjnie wzgledem \(\displaystyle{ p}\)

[patryk00714]

Odwrotnie miało być

[Zordon]

Ok, no to tam wyżej podałem jak należy podchodzić nieindukcyjnie Powinno się udać.

[patryk00714]

Mam problem z wyrażeniem \(\displaystyle{ ax}\), bo wykazałem, ze problem jest rownowazny temu, ze \(\displaystyle{ p|a}\) bo

\(\displaystyle{ { pn \choose p}\equiv n (\text{mod} p^2) \leftrightarrow (x+1)(x+2)...(x+p-1) \equiv (p-1)!(\text{mod} p^2) \leftrightarrow \\(ax+b)\equiv (p-1)!(\text{mod} p^2)\leftrightarrow ax \equiv 0(\text{mod} p^2)}\) bo \(\displaystyle{ b=(p-1)!}\) a \(\displaystyle{ ax=ap(n-1)}\)

Jak wyglada ten wspolczynnik stojacy przy x?

[Zordon]

\(\displaystyle{ a=\sum_{k=1}^{p-1}\frac{(p-1)!}{k}}\)

Trzeba udowodnić, że to przystaje do \(\displaystyle{ 0\pmod{p}}\)

[patryk00714]

próbowałem właśnie, jakoś te współczynniki scharakteryzować, ale ciężko było na to wpaść
jest jakiś wzór pozwalający wyliczyć współczynnik przy danej potędze x w wielomianie:

\(\displaystyle{ \prod_{i=1}^{k} (x+i)}\)? (tak z ciekawości)

[bakala12]

Są wzory Viete'a, ale czy konkretne sumy się ładnie liczą to nie wiem i chyba trzeba samemu kombinować.

[Zordon]

Współczynnik przy \(\displaystyle{ x^n}\) można wyrazić pewnym wzorem, natomiast będzie on stosunkowo skomplikowany. Najmniej skomplikowane wyrażenia są dla niskich potęg: wyraz wolny, wyraz przy \(\displaystyle{ x}\) itp. oraz dla wysokich potęg (czyli u Ciebie przy \(\displaystyle{ x^k}\) i \(\displaystyle{ x^{k-1}}\)).

[patryk00714]

Hmm próbuje na przeróżne sposoby to a przedstawić ale nie mohe dowieść tej podzielności przez p. Jakas podpowiedź?

[Zordon]

Najłatwiej jest pracować w ciele liczb modulo \(\displaystyle{ p}\), wtedy:

\(\displaystyle{ \sum_{k=1}^{p-1} k^{-1}=\sum_{k=1}^{p-1}k}\), gdyż funkcja \(\displaystyle{ x\mapsto x^{-1}}\) jest bijekcją na zbiorze \(\displaystyle{ \{1,2,...,p-1\}}\). Dalej:
\(\displaystyle{ \sum_{k=1}^{p-1}k=\frac{p(p+1)}{2}\equiv 0\pmod{p}}\)

edit:
przypadek \(\displaystyle{ p=2}\) trzeba rozważyć osobno