Sencilla y (por tanto) elegante demostración, José Hdz. Pero, una manera alternativa, y muy sencilla también, que es la idea que yo tuve, es la siguiente, donde así como tú, también uso el llamado "Lema de Euclides" :
Tenemos que $\binom{p}{n}=\frac{p(p-1)!}{(p-n)!n!}$. Claramente, el producto $p(p-1)!$ es divisible entre $(p-n)!n!$, pues $\frac{p(p-1)!}{(p-n)!n!}$ es un entero positivo. Pero $p$ y $(p-n)!n!$ son coprimos, porque ni $(p-n)!$ ni $n!$ contienen a $p$ como factor, pues todos los factores de $(p-n)!$ y de $n!$ son menores que $p$, por lo cual, ni $(p-n)!n!$ contiene a $p$ como factor. Pero, siendo coprimos, $p$ podría ser divisible entre $(p-n)!n!$, si y sólo si $(p-n)!n!=p$, o bien, $(p-n)!n!=1$. Pero ya que $(p-n)!n!$ no contiene a $p$ como factor, $(p-n)!n! \neq p$ °. Entonces, en este caso, $p$ es divisible entre $(p-n)!n!$ si y sólo si $(p-n)!n!=1$ *. Notamos que, si $(p-n)!n!=1$, $p$ y $(p-n)!n!$ son coprimos. De hecho, el único caso en que un número entero $a$ es coprimo con otro entero $c$ y $a$ es divisible entre $c$, es cuando $c$ es igual a $1$.
Así que entonces, como $p$ y $(p-n)!n!$ son coprimos, necesariamente, el otro factor del numerador, es decir, $(p-1)!$, es divisible entre $(p-n)!n!$ ("Lema de Euclides"). Por tanto, tenemos que $\binom{p}{n}=p\ \cdot\ \frac{(p-1)!}{(p-n)!n!}=p\ \cdot\ k$, donde $k$ es el entero positivo $\frac{(p-1)!}{(p-n)!n!}$ .