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

        riddles >> medium >> Number of (n choose r) prime to a prime p
        
(Message started by: ecoist on Feb 14th, 2008, 9:02pm)
Title: Number of (n choose r) prime to a prime p
Post by ecoist on Feb 14th, 2008, 9:02pm
Let n be a positive integer and let a1,...,ak be all the nonzero digits in the base p representation of n, where p is a prime.  Show that the number of binomial coefficients (n choose r), r=0,...,n, prime to p is (a1+1)*...*(ak+1).  Example: n=59, p=3.  Then 59 is 2012 in base 3.  Hence the number of (59 choose r) prime to 3 is (2+1)*(1+1)*(2+1)=18.
Title: Re: Number of (n choose r) prime to a prime p
Post by Barukh on Feb 22nd, 2008, 4:16am
This result follows from the this proposition (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1135363189;start=6#6).
Title: Re: Number of (n choose r) prime to a prime p
Post by Eigenray on Feb 22nd, 2008, 9:19am
Here is a nice proof: if n = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif aipi, what is (1+x)n mod p?


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board