Is the expression $\frac{\gcd(m,n)}{n}\binom{n}{m}$ always an integer?

  • MHB
  • Thread starter Ackbach
  • Start date
  • Tags
    2017
In summary, the expression $\frac{\gcd(m,n)}{n}\binom{n}{m}$ represents the number of ways to choose a subset of size $m$ from a set of size $n$, where the greatest common divisor of $m$ and $n$ is divided by $n$. It is always an integer due to the properties of the greatest common divisor and the binomial coefficient. The division by $n$ accounts for repeated elements in the subset. The expression can be simplified using an identity and has applications in fields such as genetics, statistics, and computer science.
  • #1
Ackbach
Gold Member
MHB
4,155
93
Here is this week's POTW:

-----

Prove that the expression
\[ \frac{\gcd(m,n)}{n}\binom{n}{m} \]
is an integer for all pairs of integers $n\geq m\geq 1$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!
 
Physics news on Phys.org
  • #2
Re: Problem Of The Week # 266 - Jun 05, 2017

This was Problem B-2 in the 2000 William Lowell Putnam Mathematical Competition.

Congratulations to joypav for his correct solution, which follows:

16j4fvk.jpg
 

FAQ: Is the expression $\frac{\gcd(m,n)}{n}\binom{n}{m}$ always an integer?

What does the expression $\frac{\gcd(m,n)}{n}\binom{n}{m}$ mean?

The expression represents the number of ways to choose a subset of size $m$ from a set of size $n$, where the greatest common divisor of $m$ and $n$ is divided by $n$. In other words, it represents the probability of choosing a subset of size $m$ from a set of size $n$ when the elements are selected randomly and with replacement.

Is the expression always an integer?

Yes, the expression is always an integer. This is because the greatest common divisor of any two integers will always divide the larger integer, and the binomial coefficient $\binom{n}{m}$ is defined to be an integer for all non-negative integers $n$ and $m$.

Why is the greatest common divisor divided by $n$ in the expression?

The division by $n$ in the expression is necessary to account for cases where the subset of size $m$ may contain repeated elements. This way, the expression takes into consideration the probability of selecting the same element multiple times in the subset.

Can the expression be simplified?

Yes, the expression can be simplified using the identity $\gcd(m,n)\binom{n}{m} = \binom{n}{m}\binom{\frac{n}{\gcd(m,n)}}{\frac{m}{\gcd(m,n)}}$. This simplification can be useful in certain applications, such as in calculating probabilities in genetics.

What are some real-life applications of this expression?

The expression can be used in various fields such as genetics, statistics, and computer science. For example, in genetics, it can be used to calculate the probability of inheriting a certain combination of genes from parents. In statistics, it can be used to model the probability of selecting a certain number of items from a larger set. In computer science, it can be used in algorithms that involve random selection and repetition.

Similar threads

MHB Problem of the Week # 275 - Aug 07, 2017
Replies
1
Views
1K
MHB When Is \( (k+1)^n+(k+2)^n+(k+3)^n+(k+4)^n+(k+5)^n \) Divisible by 5?
Replies
1
Views
2K
MHB Problem Of The Week # 288 - Nov 09, 2017
Replies
1
Views
2K
MHB Can you prove the power series expansion for (1-2x-x^2) has a specific pattern?
Replies
1
Views
1K
MHB Is there a way to guarantee that the sequence will eventually reach 0?
Replies
1
Views
1K
MHB Problem Of The Week # 286 - Oct 24, 2017
Replies
1
Views
2K
MHB How Does Grouping Terms Simplify the Infinite Series in This Week's POTW?
Replies
1
Views
2K
MHB Problem of the Week # 247 - Jan 02, 2017
Replies
1
Views
1K
MHB Which values of $m$ make $P_m(x)$ factorable?
Replies
1
Views
1K
MHB Odd Prime Factor of \( a_{2015} \)?
Replies
1
Views
2K

Recent Insights

Back
Top