Los coeficientes binomiales: cómo probar una desigualdad en la $p$-ádico de valoración?

Question

En la sección 4 del artículo por Afred van der Poorten es Una Prueba de Que Euler Perder ... la siguiente desigualdad se utiliza:

$$\nu_{p}\displaystyle\binom{n}{m}\leq\left\lfloor\dfrac{\ln n}{\ln p}\right\rfloor-\nu_{p}(m)\qquad(\ast)$$

(En el original denota $\text{ord}$ $_{p}(\cdot)$ en lugar de $\nu_p(\cdot)$).

donde $\nu_{p}(k)$ $p$- ádico de valoración de $k\in\mathbb{Q}$, yo. e. el exponente del primer $p$ en la factorización prima de $k$. Sé que algunas propiedades de la celebrar la función y que

$$\nu_{p}(a/b)=\nu_{p}(a)-\nu_{p}(b),$$

$$\nu_{p}(a\cdot b)=\nu_{p}(a)\cdot \nu_{p}(b)$$

y

$$\nu_{p}(n!)=\displaystyle\sum_{i\geq 1}\left\lfloor \dfrac{n}{p^{i}}\right\rfloor$$

pero yo no convencer a mí mismo en la correcta argumento que debo utilizar para probar $(\ast )$.

Pregunta: ¿Cómo puede esta desigualdad ser probada?

Answer 1

Desde $\nu_p(n!)=\sum_i\lfloor n/p^i\rfloor$, $\nu_p\binom nm=\sum_i(\lfloor n/p^i\rfloor-\lfloor m/p^i\rfloor-\lfloor (n-m)/p^i\rfloor)$. Observar que cada sumando es $\le 1$, y para $i>\left\lfloor\frac{\ln n}{\ln p}\right\rfloor$ es $0$. Que da $v_{p}\binom{n}{m}\le \left\lfloor\frac{\ln n}{\ln p}\right\rfloor$.

Finalmente, observe que para $i\le\nu_p(m)$ $\lfloor m/p^i\rfloor=m/p^i$, así ($\lfloor m/p^i\rfloor+\lfloor x/p^i\rfloor=\lfloor(m+x)/p^i\rfloor$ e) las correspondientes sumando también es $0$. Que da la desigualdad en cuestión.

Answer 2

Teorema (Kummer): $\nu_p {n \choose m}$ es el número de carreras que se necesita para agregar $m$ $n-m$ base $p$.

Ahora tenga en cuenta que $\lfloor \frac{\ln n}{\ln p} \rfloor$ es el máximo número posible de acarreos y la última $\nu_p(m)$ dígitos de $m$ no puede ser asociada a ningún lleva.

Kummer del teorema en sí no es difícil de probar; es más o menos de la siguiente manera a partir de la última de identidad de la lista.