17
$\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$
2
  • 2
    $\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$ Feb 25, 2015 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, 2015 at 2:23

2 Answers 2

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

Here is a conceptual way to derive this. Below we show that it is a special case of the well-known $\rm\color{#0a0}{Lemma}$ below that if a fraction $q\,$ can be written with denominators $\,n\,$ and $\,m,\,$ then it can also be written with denominator being their gcd $ = (n,m).\,$ This makes the proof obvious, viz.

$$\begin{align} nq,\ mq\in\Bbb Z\,\ &\Rightarrow\, (n,m)q \in\Bbb Z,\ \text{ so for }\ \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{{{n\choose m}}}\in \Bbb Z\end{align}\qquad$$


$\rm\color{#0a0}{Lemma}\ $ If a fraction $\,q = c/d\,$ can be written with denominators $\,n\,$ and $\,m,\,$ then it can also be written with denominator being their gcd $ =(n,m)$.

Proof $\ $ We give a few proofs of this basic result since that proves instructive.

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

$(4)\ \ \,q = \dfrac{C}{D} = \dfrac{c}d\Rightarrow d(C,c) = (dC,dc) = (cD,dc) = c(D,d),\,$ so $\ \dfrac{c}d = \dfrac{(C,c)}{(D,d)}$


Remark $ $ The $\rm\color{#0a0}{Lemma}$ is a denominator form of this ubiquitous group theory theorem:

$\qquad$ If $\,q^m\! = 1 = q^n\,$ then $\,q^{(m,n)}=1,\ $ by $\ {\rm ord}(q)\mid m,n\Rightarrow {\rm ord}(q)\mid (m,n)$

The least denominator of a fraction is its order in $\,\Bbb Q/\Bbb Z,\,$ so the Lemma is a special case of this result. For more on this viewpoint (denominator and order ideals) see here.

$\endgroup$
6
  • $\begingroup$ See also this answer. $\endgroup$ Feb 25, 2015 at 20:14
  • $\begingroup$ Nice, that's a bit harder (in my opinion) to come up with, but very elegant. $\endgroup$ Feb 25, 2015 at 21:01
  • $\begingroup$ @user2520938 See the edit which emphasizes the innate conceptual viewpoint. $\endgroup$ Feb 25, 2015 at 21:05
  • $\begingroup$ It's rather sad that answers that strive to emphasize conceptual viewpoints often get downvoted - whereas those that don't often get upvoted. This of course is one of the great challenges of mathematical pedagogy - how to coax students to comprehend something a bit more general when it seems easier to simply go with something less general (e.g. proofs pulled out of a hat like magic). $\endgroup$ Nov 3, 2021 at 22:13
  • $\begingroup$ Applying this lemma to $q=\frac{1}{n}\binom{n}{m}$ is just as much pulled out of a hand as the approaches of the other answers. At the end there is not much conceptually deep/interesting going on here, it is just in one way or another playing around with fundamental properties of the gcd. $\endgroup$ Nov 5, 2021 at 13:01

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.