Author |
Topic: Number of (n choose r) prime to a prime p (Read 1191 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Number of (n choose r) prime to a prime p
« on: Feb 14th, 2008, 9:02pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Number of (n choose r) prime to a prime p
« Reply #1 on: Feb 22nd, 2008, 4:16am » |
Quote Modify
|
This result follows from the this proposition.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number of (n choose r) prime to a prime p
« Reply #2 on: Feb 22nd, 2008, 9:19am » |
Quote Modify
|
Here is a nice proof: if n =  aipi, what is (1+x)n mod p?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print