wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> integer = GCD(n,m)C(n,m)/n
        
(Message started by: william wu on Aug 29^th, 2003, 9:17pm)

Title: integer = GCD(n,m)C(n,m)/n
Post by william wu on Aug 29^th, 2003, 9:17pm

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)!).

Title: Re: integer = GCD(n,m)C(n,m)/n
Post by Eigenray on Nov 3^rd, 2003, 3:48am

First solution:
[hide]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[/hide].

Second solution:
[hide]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[/hide].