2014

Giugno 2014 - Problema 5

Si provi che per ogni numero primo \(p\geq 3\), il resto della divisione intera tra il coefficiente binomiale \(\binom{n}{p}\) e \(p\) è pari alla parte intera inferiore di \(\frac{n}{p}\), ossia:
\[\binom{n}{p}\equiv\left\lfloor\frac{n}{p}\right\rfloor\pmod{p}.\]

Livello di difficoltà: Tigrotto da passeggio
Punteggio difficoltà: 30



Tutti i risolutori hanno utilizzato essenzialmente le medesime considerazioni. Scrivendo:
\[\binom{n}{p}=\frac{n(n-1)\cdot\ldots\cdot(n-p+1)}{p(p-1)\cdot\ldots\cdot 1}\]
abbiamo che a numeratore del membro destro compare un solo fattore multiplo di \(p\), diciamo \(m=kp\). Deve valere \(m=\left\lfloor\frac{n}{p}\right\rfloor\) in quanto in quanto il numeratore è prodotto di \(p\) interi consecutivi, il più grande dei quali è \(n\). A denominatore, abbiamo \(p\cdot(p-1)!\).  Poiché, per il Teorema di Wilson, \[(p-1)!\equiv -1\pmod{p},\] il coefficiente binomiale \(\binom{n}{p}\) è dato dal prodotto tra \(m\) e il rapporto (intero) di due numeri interi della forma \(kp-1\). Quest'ultimo rapporto è necessariamente della forma \(kp+1\), e la tesi segue immediatamente.