15
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – marvinthemartian Feb 25 '15 at 18:42
  • $\begingroup$ 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$. $\endgroup$ – whacka Feb 26 '15 at 2:23
24
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wow, I am really impressed! Very nice proof. $\endgroup$ – Peter Feb 25 '15 at 19:03
  • $\begingroup$ 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{}$ $\endgroup$ – Michael Hardy Feb 25 '15 at 19:28
  • $\begingroup$ Next question: What's the combinatorial interpretation of the expression that is simplified here? ${}\qquad{}$ $\endgroup$ – Michael Hardy Feb 25 '15 at 19:30
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ See also this answer. $\endgroup$ – Bill Dubuque Feb 25 '15 at 20:14
  • $\begingroup$ Nice, that's a bit harder (in my opinion) to come up with, but very elegant. $\endgroup$ – user2520938 Feb 25 '15 at 21:01
  • $\begingroup$ @user2520938 See the edit which emphasizes the innate conceptual viewpoint. $\endgroup$ – Bill Dubuque Feb 25 '15 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.