Author |
Topic: integer = GCD(n,m)C(n,m)/n (Read 1161 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
integer = GCD(n,m)C(n,m)/n
« on: Aug 29th, 2003, 9:17pm » |
 Quote  Modify
|
Prove the following statement:
[forall]n,m[in][bbz], n[ge]m[ge]1: gcd(n,m)C(n,m)/n [in][bbz]
where gcd(n,m) is the greatest common divisor of the integers n and m, and C(n,m) is "n choose m" = n! / (m!(n-m)!).
|
| « Last Edit: Aug 29th, 2003, 9:18pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: integer = GCD(n,m)C(n,m)/n
« Reply #1 on: Nov 3rd, 2003, 3:48am » |
Quote Modify
|
First solution:
Say d=gcd(n,m), n=da, m=db. Now, C(n,m) = n/m C(n-1,m-1) = a/b C(n-1,m-1) is certainly an integer.
Since gcd(a,b)=1, and b | aC(n-1,m-1), we must have b | C(n-1,m-1), so that k = C(n-1,m-1)/b is an integer.
Then d/n C(n,m) = 1/a (a/b) kb = k is an integer.
Second solution:
It's a standard result (since the integers are a principal ideal domain) that there are integers x,y such that gcd(m,n) = mx+ny.
Then gcd(m,n) C(n,m)/n = (mx+ny)C(n,m)/n = mx(n/m)C(n-1,m-1)/n + yC(n,m) = xC(n-1,m-1) + yC(n,m) is an integer.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print