Putnam 2000 B2

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

2 users

TOPICS

No tags match your search

M

No tags match your search

M

Putnam 2000 B2

G H J

Reveal topic tags

greatest common divisor

college contests

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6294 posts

#1 h Sep 6, 2011, 10:24 PM • 6 Y

Y by Tawan, bobjoe123, Adventure10, Mango247, Rounak_iitr, Tastymooncake2

Prove that the expression $\dfrac {\text {gcd}(m, n)}{n} \dbinom {n}{m}$ is an integer for all pairs of integers $n \ge m \ge 1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#2 h Sep 7, 2011, 5:26 AM • 17 Y

Y by Binomial-theorem, esi, Tawan, bobjoe123, myh2910, mathleticguyyy, fungarwai, ehuseyinyigit, Adventure10, Sagnik123Biswas, Sedro, Tastymooncake2, panche, aidan0626, kiyoras_2001, MS_asdfgzxcvb, and 1 other user

By an important theorem of number theory, $\gcd(m,n)=an+bm,$ where $a$ and $b$ are integers. Thus
$\begin{align*}\frac{\gcd(m,n)}n\binom nm&=a\binom nm +\frac{bm}n\binom nm\\ &=a\binom nm+\frac{bmn!}{nm!(n-m)!}\\ &=a\binom nm+\frac{b(n-1)!}{(m-1)!(n-m)!}=a\binom nm+b\binom{n-1}{m-1}\end{align*}$
Since $1\le m\le n,$ $\binom{n-1}{m-1}$ is an integer, as is also $\binom nm,$ so we are done.

This post has been edited 1 time. Last edited by darij grinberg, Sep 7, 2011, 8:49 AM
Reason: gcd(m,n)=am+bn replaced by gcd(m,n)=an+bm to match with rest of the solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5850 posts

#3 h Sep 9, 2011, 10:08 AM • 11 Y

Y by Ankoganit, WizardMath, Tawan, bobjoe123, myh2910, GreenKeeper, Adventure10, Sagnik123Biswas, Tastymooncake2, jason02, and 1 other user

A combinatorial way is to consider equivalence classes of ways to select $m$ objects out of $n$ total, where two configurations are equivalent if they are a cyclic shift away from each other. Each equivalence class has $d$ elements where $d$ is the period of the configuration, and for this period $d$ , the integer $\frac{n}{d}$ must be a divisor of $\gcd(m,n)$ . Hence the number of elements in each equivalence class is divisible by $\frac{n}{\gcd(m,n)}$ , and so that also divides the total number of elements in general. Namely, $\frac{n}{\gcd(m,n)}$ divides ${n \choose m}$ as desired.

This post has been edited 1 time. Last edited by darij grinberg, Sep 12, 2011, 11:40 AM
Reason: fixed a mistake of exposition (an equivalence class of period d has d elements, not n/d elements)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#4 h Sep 9, 2011, 10:24 AM • 3 Y

Y by Tawan, Adventure10, Mango247

See http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1428715&sid=ade222a91e95ff2391d2d4ba33ab2e5a#p1428715 for a generalization.
At the time I came up with that, used at the second RMofM, I was unaware of the Putnam one.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2083 posts

#5 h Aug 13, 2014, 9:49 PM • 3 Y

Y by gethd, Tawan, Adventure10

This is equivalent to showing that $\frac{n}{gcd(n,m)} \mid \binom{n}{m}$ .

We have that $\frac{m}{n}\binom{n}{m} = \binom{n-1}{m-1}$ .

Dividing out we get $\frac{m/gcd(n,m)}{n/gcd(n,m)}\binom{n}{m} = \binom{n-1}{m-1}$ .

Since $\binom{n-1}{m-1}$ is an integer and the numerator and the denominator of the fraction share no common factors, this implies that $\frac{n}{gcd(n,m)} \mid \binom{n}{m}$
and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

695 posts

#6 h Jun 8, 2017, 5:30 PM • 5 Y

Y by Tawan, Adventure10, Mango247, Sagnik123Biswas, Tastymooncake2

It is enough to show that for any prime $p$ , $\nu_p \binom{n}{m} \ge \nu_p(n) - \nu_p(\gcd(m, n)).$ Set $a = \nu_p(n), b = \nu_p(m)$ , and note that $\nu_p(\gcd(m, n)) = \min(a, b).$ Therefore, the above rewrites as $\nu_p \binom{n}{m} \ge a - \min(a, b).$ If $a \le b$ this inequality is trivial. If $a > b$ , then using the identity $\binom{n}{m} = \frac{n}{m}\binom{n - 1}{m - 1},$ we obtain $\nu_p \binom{n}{m} \ge \nu_p(n) - \nu_p(m) = a - b = a - \min(a, b).$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

128 posts

#7 h Jun 28, 2020, 4:55 AM • 1 Y

Y by Mango247

Using Bezout's Lemma, we get that there exists a, b such that gcd(man) = am+bn. Plugging this in, it remains to prove that am(nCm)/m is an integer. but this is equivalent to a(n-1 C n-m) and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

17020 posts

#8 h Aug 14, 2021, 2:26 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1080 posts

#9 h Nov 30, 2021, 4:49 AM • 1 Y

Y by centslordm

By Bezout's lemma, let $\gcd(m,n)=am+bn$ where $a,b\in\mathbb{Z}.$ Then, $\begin{align*}\frac{\gcd(m,n)}{n}\binom{n}{m}&=\frac{am+bn}{n}\binom{n}{m}\\&=\frac{am}{n}\binom{n}{m}+b\binom{n}{m}\\&=\frac{am}{n}\cdot\frac{n!}{m!(n-m)!}+b\binom{n}{m}\\&=\frac{a(n-1)!}{(m-1)!(n-m)!}+b\binom{n}{m}\\&=a\binom{n-1}{m-1}+b\binom{n}{m}\\&\in\mathbb{Z}.\end{align*}$ $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2908 posts

Arr0w

#10 h Dec 1, 2021, 9:32 PM

Y by

Posting this solution for storage. The critical observation here is to use Bézout's Lemma so that $\gcd(m,n)=am+bn$ for some integers $a$ and $b$ . From this we have
$\begin{align*} \frac {\gcd(m, n)}{n} \dbinom {n}{m}&=\frac {am+bn}{n} \dbinom {n}{m}\\ &=\frac{am}{n}\dbinom {n}{m}+b\dbinom {n}{m}\\ &=\left(\frac{am}{n}\right)\left(\frac{n!}{m!(n-m)!}\right)+b\dbinom {n}{m}\\ &=\frac{a(n-1)!}{(m-1)!(n-m)!}+b\dbinom {n}{m}\\ &=a\binom{n-1}{m-1}+b\dbinom {n}{m}.\\ \end{align*}$ We were given that $n \ge m \ge 1$ so both $\binom{n-1}{m-1}$ and $\dbinom {n}{m}$ are integers, which ultimately means that $\dfrac {\text {gcd}(m, n)}{n} \dbinom {n}{m}$ is an integer. This completes the proof $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5611 posts

#11 h Mar 8, 2022, 9:59 PM • 1 Y

Y by Muhammadqodir

Let $\gcd(m,n)=mx+ny$ for integers $x$ and $y$ .

We have $\begin{align*} \frac{\gcd(m,n)}{n}\binom{n}{m} \\ =\frac{mx+ny}{n}\binom{n}{m} \\ =\frac{mx}{n}\binom{n}{m}+y\binom{n}{m} \\ \end{align*}$
Since the second term is an integer, we only have to show $\frac{mx}{n}\binom{n}{m}$ is an integer.

We have $\begin{align*} \frac{mx}{n}\binom{n}{m} \\ =\frac{mx}{n}\frac{n!}{m!(n-m)!} \\ =\frac{mx\cdot (n-1)!}{m!(n-m)!} \\ =\frac{x\cdot (n-1)!}{(m-1)!(n-m)!} \\ =x\cdot \binom{n-1}{m-1} \\ \end{align*}$ which is an integer $\blacksquare$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1757 posts

Taco12

#15 h Jul 15, 2022, 7:29 PM • 3 Y

Y by Mango247, Mango247, Mango247

First Putnam solve!

Bézout gives $\gcd(m,n)=mx+ny$ , so we need $\frac{mx+ny}{n}\binom{n}{m}$ to be an integer.
$\frac{mx+ny}{n}\binom{n}{m}=x\cdot\frac{m}{n}\binom{n}{m}+y\cdot\binom{n}{m}$ The problem reduces to showing $x\cdot\frac{m}{n}\binom{n}{m}$ is an integer. But we have $x\cdot\frac{m}{n}\binom{n}{m}=x\cdot\binom{n-1}{m-1},$ which is clearly an integer. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6290 posts

#16 h Aug 1, 2023, 7:27 AM

Y by

From Bezout's Theorem, $\text{gcd}(m,n) = am + bn$ for some $a, b \in \mathbb Z.$ Then,
$\begin{align*} \frac{\text {gcd}(m, n)}{n} \binom {n}{m} &= \frac{am + bn}{n} \binom {n}{m} \\ &= \frac{am}{n} \binom{n}{m} + b \binom{n}{m} \\ &= \frac{am n!}{n m! (n-m)!} + b \binom{n}{m} \\ &= a \binom{n-1}{m-1} + b \binom{n}{m}. \end{align*}$ Since both of the terms are integers, we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chakrabortyahan

385 posts

chakrabortyahan

#17 h Apr 22, 2024, 5:29 PM

Y by

Why the problems Arnab is posting are looking so cool and those I am finding and posting look so boring...Arnab saar pilij geev teeps yabaut hau tu phaind gud poroblams
Classic $p-\text{adic}$ problem...(I won't use Bezout as almost all the solutions above are by bezout)
We want to show that every prime (of sufficient size) has non-negative power in the prime factorization of $\dfrac {\text {gcd}(m, n)}{n} \dbinom {n}{m}$ .
Say , $p$ is any prime less than $n$ that divides $n$ .( Note that if a prime $q$ does not divide $n$ then it has non-negative power in $\binom{n}{m}$ as it is an integer. hence we are not concerned about such $q$ )Take $v_p(m) = a , v_p(n) = b$ Now note that if $a\geq b$ as $v_p(\text{gcd} (a,b)) = b$ and so $v_p(\frac{\text{gcd}(m,n)}{n}) = 0$ and as $\binom{n}{m}$ is an integer so we have $v_p(\binom{n}{m}) \ge 0$ and we are done .
Now if $a<b$ then $v_p(\frac{\text{gcd(m,n)}}{n}) = a-b <0$ . Now note that $m\binom{n}{m} = n \binom{n-1}{m-1}$ Considering the maximum exponent of $p$ both sides we write $a+v_p(\binom{n}{m}) = b +v_p(\binom{n-1}{m-1})\ge b \implies v_p(\binom{n}{m})\ge b-a$ . hence we are done

$\blacksquare\smiley$

This post has been edited 3 times. Last edited by chakrabortyahan, Apr 23, 2024, 4:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

947 posts

#18 h Apr 23, 2024, 4:00 PM

Y by

By Bezout's Theorem, there exists $x,y \in \mathbb{Z}$ such that $\gcd(m,n)=mx+ny$ .
Then,
$\frac{\gcd(m,n)}{n} \binom{n}{m} = y\binom{n}{m} + \frac{xm}{n}\binom{n}{m} = y\binom{n}{m} + x\binom{n-1}{m-1} \in \mathbb{Z}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

34 posts

#19 h May 19, 2024, 8:00 AM

Y by

nothing fancy just use Bezout's lemma $\gcd(m,n) = mx_0 + ny_0$
the given expression converts into $\frac{m}{n} \cdot x_0 \cdot \binom{n}{m} + y_0\cdot\binom{n}{m}$
the second part is clearly integer so it is sufficient to prove that the first part is integer.

$\implies \frac{n!}{(n-m)!m!} \cdot \frac{x_0 m}{n}$ $=\frac{x_0 (n-1)!}{(n-m)!(m-1)!}$ $=x_0 \binom{n-1}{m-1} \in \mathbb{Z}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4243 posts

#20 h Jun 3, 2024, 2:12 AM

Y by

We just need to show that $v_p(\binom{n}{m})-v_p(n)+\min(v_p(m),v_p(n))\ge 0$ .

When $v_p(n)\le v_p(m)$ , this is obviously true since $\binom{n}{m}$ is an integer.

Otherwise, we need to show that $v_p(\binom{n}{m})-v_p(n)+v_p(m)=v_p(\binom{n}{m}\frac{m}{n})\ge 0$ . This is true because $\binom{n}{m}\frac{m}{n}=\binom{n-1}{m-1}$ is an integer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

110 posts

#21 h Feb 20, 2025, 6:10 AM

Y by

From Bezouts Lemma, $\gcd(m,n) = mx + ny$ , where $x$ and $y$ are integers. So $\frac{\gcd(m,n)}{n}\binom{n}{m} = \frac{mx+ny}{n}\binom{n}{m} = \frac{mx}{n}\binom{n}{m}+y\binom{n}{m}$ . Clearly, $y\binom{n}{m}$ is an integer. $\frac{mx}{n}\binom{n}{m} = \frac{x(n-1)!}{(m-1)!(n-m)!} = x\cdot \binom{n-1}{m-1}$ is also an integer which solves the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

244 posts

#22 h Apr 5, 2025, 10:44 PM

Y by

$\text{We use bezouts lemma}$
it states that $\exists a,b$ s.t $gcd(m,n)=an+bm$
$\begin{align*}\frac{\gcd(m,n)}n\binom nm&=a\binom nm +\frac{bm}n\binom nm\\ &=a\binom nm+\frac{bmn!}{nm!(n-m)!}\\ &=a\binom nm+\frac{b(n-1)!}{(m-1)!(n-m)!}=a\binom nm+b\binom{n-1}{m-1}\end{align*}$ $\mathbb{Q.E.D}$ $\blacksquare$
:icecream:

:icecream:

:pilot:

This post has been edited 1 time. Last edited by Levieee, Apr 5, 2025, 10:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1965 posts

#23 h Apr 5, 2025, 10:57 PM

Y by

Levieee wrote:

$\text{We use bezouts lemma}$
it states that $\exists a,b$ s.t $gcd(m,n)=an+bm$
$\begin{align*}\frac{\gcd(m,n)}n\binom nm&=a\binom nm +\frac{bm}n\binom nm\\ &=a\binom nm+\frac{bmn!}{nm!(n-m)!}\\ &=a\binom nm+\frac{b(n-1)!}{(m-1)!(n-m)!}=a\binom nm+b\binom{n-1}{m-1}\end{align*}$ $\mathbb{Q.E.D}$ $\blacksquare$
:icecream:

:icecream:

:pilot:

literally carbon copy of #2 lmao
the latex is exactly the same

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

63 posts

#25 h May 5, 2025, 5:05 PM

Y by

By Bezout's Identity, there exists integers $x,y$ such that $\gcd(m,n) = mx + ny$ . Hence,
$\begin{align*}\frac{\gcd(m,n)}n\binom nm &=\frac{mx + ny}{n} \cdot \frac{n!}{m!(n-m)!}\\ &=\frac{x(n-1)!}{(m-1)!(n-m)!} + \frac{yn!}{m!(n-m)!}\\ &=x\binom{n-1}{m-1} + y\binom{n}{m}\\ \end{align*}$ Which is obviously an integer.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a