21
$\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$
    – marvinthemartian
    Commented 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$
    – anon
    Commented Feb 26, 2015 at 2:23

2 Answers 2

Reset to default
41
$\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
    Commented Feb 25, 2015 at 19:03
  • 2
    $\begingroup$ Next question: What's the combinatorial interpretation of the expression that is simplified here? ${}\qquad{}$ $\endgroup$
    – Michael Hardy
    Commented Feb 25, 2015 at 19:30
10
$\begingroup$

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

$$\begin{align} \color{#0a0}nQ,\ \color{#0a0}mQ\in\Bbb Z\,\ &\Rightarrow\, \color{#0a0}{(n,m)}Q \in\Bbb Z,\ \text{ so for }\ \color{c00}Q = \frac{1}{n}{n\choose m}\\ \color{#0a0}n\color{c00}Q = {n\choose m},\,\ \color{#0a0}m\color{c00}Q= {n\!-\!1\choose m\!-\!1}\in\Bbb Z\,\ &\Rightarrow\ \color{#0a0}{(n,m)}\color{c00}Q = \dfrac{(n,m)}n{{{n\choose m}}}\in \Bbb Z.\ \ \ \small\bf QED\end{align}\qquad\qquad$$

$\rm\color{#0af}{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 four proofs of this basic result, since doing so proves instructive (the proof in the other answer is essentially $(3)$ below, but here we highlight the innate conceptual structure).

$(1)\ $ Recall that a fraction can be written with denominator $\,n\,$ iff its least denominator $\,d\mid n.\,$ Hence $\,m,n\,$ are denoms $\!\iff\! d\mid m,n\!\iff\! d\mid (m,n)\!\iff\! (m,n)\,$ is a denom, by here.

$(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)\ \ \,\bbox[5px,border:1px solid #c00]{q = \dfrac{C}{D} = \dfrac{c}d\,\Rightarrow\, q= \dfrac{(C,c)}{(D,d)}}\,\ $ by $\ d(C,c) = (dC,dc) = (cD,dc) = c(D,d)$

$(4)\,$ can be viewed as special case of an extension of gcd to rationals.. $(3)$ is a special case of $(2)$ arising by recplacing gcds by their linear Bezout rep (it is less general because Bezout fails in many common gcd domains, e.g. polynomial UFDs like $\,\Bbb Z[x],$ and $\,\Bbb Q[x,y])$.

Remark $ $ The $\rm\color{#90f}{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 and here.

$\endgroup$
6
  • $\begingroup$ See also this answer. $\endgroup$
    – Bill Dubuque
    Commented Feb 25, 2015 at 20:14
  • $\begingroup$ Nice, that's a bit harder (in my opinion) to come up with, but very elegant. $\endgroup$
    – user2520938
    Commented Feb 25, 2015 at 21:01
  • $\begingroup$ @user2520938 See the edit which emphasizes the innate conceptual viewpoint. $\endgroup$
    – Bill Dubuque
    Commented Feb 25, 2015 at 21:05
  • 2
    $\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$
    – Bill Dubuque
    Commented 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$
    – user2520938
    Commented Nov 5, 2021 at 13:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .