# ${\gcd(n,m)\over n}{n\choose m}$ is an integer

Prove that for every $n\geq m \geq1$ natural numbers, the following number is an integer:

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

Where $\gcd$ is the greatest common divisor.

I tried to make it simpler by cancelling the $n$ from the left side, and making it $(n-1)!$ on the right: $\gcd(n, m) \cdot \frac{(n-1)!}{m!(n-m)!}$, but can't really go further.

This was problem B-2 on the 2000 Putnam exam.

• Try to use this: "Bézout's identity (also called Bézout's lemma) is a theorem in the elementary theory of numbers: let a and b be nonzero integers and let d be their greatest common divisor. Then there exist integers x and y such that ax+by=d" en.wikipedia.org/wiki/B%C3%A9zout%27s_identity – marvinthemartian Feb 25 '15 at 18:42
• I tried considering group actions but it didn't pan out. In particular, $\Bbb Z/n\Bbb Z$ acts on $\{1,2,\cdots,n\}$ which induces an action on $\binom{n}{m}$ (the collection of $m$-subsets of $\{1,\cdots,n\}$). If the subgroup $\langle\bar{m}\rangle$ acts freely on $\binom{n}{m}$ then the claim would follow from orbit-stabilizer. Unfortunately the action needn't be free - the smallest counterexample is $m=2$, $n=4$. – whacka Feb 26 '15 at 2:23

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

Then:

$$\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}$$

• Wow, I am really impressed! Very nice proof. – Peter Feb 25 '15 at 19:03
• I changed \text{gcd} to \gcd. With \text{gcd} you don't automatically get proper spacing in expressions like $3\gcd(m,n)$. Instead you see $3\text{gcd}(m,n)$. ${}\qquad{}$ – Michael Hardy Feb 25 '15 at 19:28
• Next question: What's the combinatorial interpretation of the expression that is simplified here? ${}\qquad{}$ – Michael Hardy Feb 25 '15 at 19:30

Here is a conceptual way to derive this. We will show that it is a special case of the well-known fact that if a fraction $$q\,$$ can be written with denominators $$\,n\,$$ and $$\,m,\,$$ then it can also be written with a denominator being their gcd $$\,(n,m),\,$$ i.e. $$\, nq,\,mq\in\Bbb Z\,\Rightarrow\, (n,m)q\in\Bbb Z.\,$$ Applied to $$\ \color{#c00}q = \frac{1}{n}{n\choose m}\,$$

$$n\color{#c00}q = {n\choose m}^{\vphantom{|^{|^|}}}\in\Bbb Z,\,\ m\color{#c00}q= {n\!-\!1\choose m\!-\!1}\in\Bbb Z\,\ \Rightarrow\ (n,m)q = \dfrac{(n,m)}n\smash{\overbrace{{n\choose m}}^{\Large n\color{#c00}q}}\in \Bbb Z\quad$$

Remark $$\$$ Below are a few proofs of the Lemma on fractions. Recall $$\,(x,y):=\gcd(x,y)$$

$$(1)\$$ Recall that a fraction can be written with denominator $$\,n\,$$ iff its least denominator $$\,d\mid n.\,$$ Therefore $$\,m,n\,$$ are denoms $$\iff d\mid m,n\iff d\mid (m,n)\iff (m,n)\:$$ is a 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\$$ by $$\rm\color{#c00}{Bezout}$$