${\gcd(n,m)\over n}{n\choose m}$ es un entero

Question

Demostrar que para cada $n\geq m \geq1$ los números naturales, el siguiente número es un entero:

$${\gcd(n,m)\over n}\cdot{n\choose m}$$

Donde $\gcd$ es el máximo común divisor.

He intentado simplificarlo por cancelar el $n$ del lado izquierdo y lo que $(n-1)!$ a la derecha: $\gcd(n, m) \cdot \frac{(n-1)!}{m!(n-m)!}$, pero realmente no puede ir más lejos.

Esto era problema B-2 en el examen Putnam 2000.

Answer 1

Escriba $nx+my=\gcd(n,m)$, $x,y\in\mathbb{Z}$

A continuación:

$$\frac{\gcd(n,m)}{n}\binom{n}{m}=\frac{nx+my}{n}\binom{n}{m}=x\binom{n}{m}+y\,\frac{m}{n}\binom{n}{m}=x\binom{n}{m}+y\binom{n-1}{m-1}\in\mathbb{Z}$$

Answer 2

Aquí está una manera conceptual para obtener esa que hace que sea clara. Vamos a demostrar que es un caso especial de que el hecho bien conocido de que si una fracción $q\,$ puede ser escrito con denominadores $\,a\,$$\,b,\,$, entonces también puede escribirse con denominador $\,\gcd(a,b), $ es decir $\, aq,\,bq\in\Bbb Z\,\Rightarrow\, \gcd(a,b)q\in\Bbb Z.$ Aplicando esto a la fracción $\ \color{#c00}q = \frac{1}{n}{n\choose m}\, $ nosotros de inmediato obtener el resultado buscado

$$\displaystyle n\color{#c00}q = {n\choose m}\in\Bbb Z,\,\ m\color{#c00}q = {n\!-\!1\choose m\!-\!1}\in\Bbb Z\,\ \Rightarrow\ \gcd(n,m)q\, =\, \dfrac{\gcd(n,m)}n{n\choose m}\in \Bbb Z$$

---

Comentario $\ $ a Continuación se presentan algunas de las pruebas de la Lema en las fracciones. Escribimos $\,(x,y):=\gcd(x,y)$

$(1)\ $ Recordar que una fracción puede ser escrito con denominador $\,n\,$ iff su mínimo denominador $\,d\mid n.\,$ por lo Tanto $\,m,n\,$ son denoms $\iff d\mid m,n\iff d\mid (m,n)\iff (m,n)\:$ es un denom.

$(2)\ \ \dfrac{mc}d,\dfrac{nc}d\in\Bbb Z\iff d\mid mc,nc\iff d\mid (mc,nc)=(m,n)c\iff\! \dfrac{(m,n)c}d\in\Bbb Z$

$(3)\ \ \dfrac{mc}d, \dfrac{nc}d\in\Bbb Z\,\Rightarrow \dfrac{jmc}d,\, \dfrac{knc}d\in\Bbb Z\,\Rightarrow\,\dfrac{(jm\!+\!kn)c}d\,\overset{\large \color{#c00}{\exists\, j,k}_{\phantom{1^{1^{1}}\!\!\!\!\!}}} = \dfrac{(m,n)c}d\in\Bbb Z\ $ $\rm\color{#c00}{Bezout}$