El primer dividiendo los coeficientes binomiales

Question

Es muy fácil demostrar que para cada prime $p$ $0<i<p$ tenemos que $p$ divide el coeficiente binomial $\large p\choose i$; simplemente se observa que, en $\large \frac{p!}{i!(p-i)!}$ el numerador es divisible por $p$, mientras que el denominador no es (ya que es un producto de los números menores que $p$ $p$ es primo).

Mi problema es con la generalización de este argumento para $q=p^n$. Estoy buscando el más elegante y sencilla manera de probar que $p$ todavía divide $\large q\choose i$.

Answer 1

Deje $v_p(n)$ indica el exponente de la potencia más grande de $p$ que se divide $n$. Vamos a mostrar que $v_p\left({p^n \choose i}\right) = n-v_p(i)$. En particular, esto es positivo, a menos que $i=0$ o $i=p^n$.

Es fácil ver que para cualquier $n$, $$v_p(n!)=\sum_{k=1}^\infty \left\lfloor \frac{n}{p^k}\right\rfloor.$$

We need an expression for $v_p(p!)-v_p(yo!)-v_p((q-i)!)$, where $p=p^n$.

Notice that $v_p(p!) = \frac{p^n-1}{p-1}$ by the above formula (which just becomes a geometric series with finitely many terms).

Notice also that for any $x \in \mathbb{R}$, $\lfloor -x \rfloor + \lfloor x \rfloor =\begin{cases} 0 && \text{if } x \in \mathbb{Z} \\ -1 && \text{otherwise.}\end{casos}$

Therefore,

$$\begin{align}v_p((q-i)!)+v_p(i!) &= \sum_{k=1}^n \left\lfloor\frac{p^n-i}{p^k}\right\rfloor + \left\lfloor\frac{i}{p^k}\right\rfloor \\ &=\sum_{k=1}^n \left(p^{n-k} + \left\lfloor\frac{-i}{p^k}\right\rfloor + \left\lfloor\frac{i}{p^k}\right\rfloor\right) \\&=\frac{p^n-1}{p-1}-(n-v_p(i)).\end{align}$$

Hence we have $v_p\left({p^n \elegir i}\right) = n-v_p(i)$.

Edit (Dec. 6 2011): for fun, yesterday I asked myself how badly the equality $v_p\left({n \elegir m}\right) = v_p(n)-v_p(m)$ fails for general $n$ and $m$. So I used Mathematica to create the following image. The triangle consists of the first 256 rows of Pascal's triangle, colored using the following rule: the greener a points is, the bigger the difference $v_2\left({n \elegir m}\right) - v_2(n) +v_2(m)$. Un poco de experimentación muestra que cualquier otra elección de primer genera una imagen similar.

Para crear esta imagen, he utilizado el p-ádico aritmética paquete y el siguiente código:

p = 2; until = 256; t = Table[Table[{RGBColor[0, PadicOrder[Binomial[n, m]/(n/m), p]/Log[p, until], 0], Rectangle[{until/2 - 1/2 - n/2 + m, n}]}, {m, 1, n}], {n, 1, until}]; Graphics[t]

Answer 2

Cómo sobre el uso de el hecho de que $(x+y)^p = x^p + y^p$ en un campo de característica $p$? Esto se deduce del hecho de que usted acaba de decir. Ahora repite para demostrar que $(x+y)^q = x^q + y^q$ cualquier $q = p^n$.

Answer 3

$$\binom qi=\frac{\prod_{k=0}^{i-1}(q-k)}{\prod_{k=1}^i k}=\frac qi\prod_{k=1}^{i-1}\frac{q-k}k\;.$$

Hay al menos un factor de $p$$q/i$, y cada uno de los factores en el producto restante tiene el mismo número de factores de $p$ en el numerador y el denominador.

[Editar en respuesta al comentario:] Vamos a $j$ el número de factores de $p$$k$, lo $k=ap^j$$p\nmid a$. Entonces

$$\frac{q-k}k=\frac{p^n-ap^j}{ap^j}=\frac{(p^{n-j}-a)p^j}{ap^j}\;,$$

y $p\nmid p^{n-j}-a$, ya que el $j<n$.

Answer 4

Esto (y algunas generalizaciones) sigue muy bien de Lucas Teorema, que no es demasiado difícil de probar.

Para encontrar $\binom{m}{n}$ modulo $p$, sólo se necesita expandir $m$ $n$ base $p$ dígitos como $m=m_0 + m_1p + \ldots +m_dp^d$$n=n_0+n_1p+\ldots + n_c p^c$. Entonces $$ \binom{m}{n} \equiv \prod_i \binom{m_i}{n_i} \pmod{p}.$$

Si $m=p^r$$1<n<p^r$, $n_i \neq 0$ algunos $i<r$. Luego tenemos a $\binom{m_i}{n_i} = \binom{0}{n_i} = 0$, lo $\binom{m}{n} \equiv 0 \pmod{p}.$

---

EDIT: he Aquí una prueba de que $\binom{p^n}{i} \equiv 0 \pmod{p}$$0<i<p^n$, que se especializa la prueba de Lucas teorema se da en Wikipedia.

Tenemos un conjunto de $M$ del tamaño de la $p^n$, y queremos contar (mod $p$) el tamaño de la $i$ subconjuntos de a $M$. El grupo cíclico $C_{p^n}$ del tamaño de la $p^n$ actúa en $M$, y actúa también sobre el conjunto de todos los tamaño de $i$ subconjuntos de a $M$. Desde $0<i<p^n$, no el tamaño de la $i$ subconjunto es fijado por $C_{p^n}$; por lo que el conjunto de tamaño $i$ subconjuntos de a $M$ es repartido por $C_{p^n}$ en varios trivial de las órbitas. El tamaño de cada órbita debe ser divisible por $p$, lo $\binom{p^n}{i} \equiv 0$ modulo $p$.

Answer 5

Es una consecuencia inmediata de este elemental prueba de que los coeficientes binomiales son enteros. Que la prueba de algoritmos de los cambios de la bijection abajo entre los numeradores y denominadores

$$\rm {\:k\:\choose \:i\:}\ =\ \frac{k}{i}\ \frac{k-1}{i-1}\ \cdots \frac{k-i+1}{1} $$

para que el poder de la prime $\rm\:p\;$ en cada numerador es $\:\ge\:$ de su denominador. Pero cuando $\rm\: i < k = p^n\:$ uno de estas desigualdades deben ser estrictas. Es decir, la fracción de haber numerador $\rm\:p^n\:$ ha denominador $\rm\le i < p^n\:$, por lo que su poder de $\rm\:p\:$$\rm\: < n\:.\:$, con Lo que hay más factores de $\rm\:p\:$ en el numerador del producto que en el denominador del producto, por lo $\rm\:p\:$ divide su cociente $\rm\:\in \mathbb Z\:.$