Klasyczna kongruencja

[mol_ksiazkowy]

Udowodnć, że jeśli \(\displaystyle{ n \in N}\)
oraz \(\displaystyle{ p \in P}\), to
\(\displaystyle{ {np -1 \choose p-1} \ \equiv 1 \ (mod \ p)}\)

[Vax]

Wynika to z

[robertm19]

Niech \(\displaystyle{ v=(p-1)!}\) oraz \(\displaystyle{ u}\) będzie takie, że \(\displaystyle{ uv=1 (\mod p)}\).
Istnieje bo dla liczb pierwszych \(\displaystyle{ Z_p}\) jest ciałem.
Zauważmy, że \(\displaystyle{ (np-i)=-i \mod p}\).

Stąd \(\displaystyle{ \frac{(np-1)!}{(n-1)p!}=(np-1) \cdot (np-2) \cdot ... \cdot (np-(p-1))=(-1)^{p-1}(p-1)!\mod p}\).

Zatem \(\displaystyle{ {np-1 \choose p-1}= uv {np-1 \choose p-1}=u(-1)^{p-1}(p-1)!=uv(-1)^{p-1} \mod p}\),
a to z tw. Fermata równe jest \(\displaystyle{ 1 \mod p}\).