LOGIN/REGISTER
Please Wait...
It is currently Sep 02, 2010, 11:46 am
Post new topic Reply to topic  Page 1 of 1
  [ 5 posts ]  Share: Facebook
Author Message
freemind
Riemann Hypothesis
User avatar

Posts: 337
Location: MIT or Moldova
Moldova, Republic of    United States
Post Posted: Mar 30, 2008, 6:41 am • # 1 


Let p be a prime number and k,n positive integers so that \gcd(p,n)=1. Prove that \binom{n\cdot p^k}{p^k} and p are coprime.

_________________
The fate of equilibrium is to end the eternity...
 
 
ZetaX
Birch & Swinnerton Dyer
User avatar

Posts: 6340
Location: München
Germany
Post Posted: Mar 30, 2008, 6:49 am • # 2 


Trivial by Lucas theorem.
Or write the binomial coefficient out and look how often each term is divisible by p.
You even have (for p > 3) the much stronger property \binom{n \cdot p^k}{p^k} \equiv n \mod p^{k + 3} for arbitrary n.

_________________
IMO Shortlist 2010 revealed!
 
 
Vrajitoarea Andrei
Hodge Conjecture
User avatar

Posts: 81
Location: Craiova,Romania
Post Posted: Jun 21, 2008, 9:06 am • # 3 


I see another approach.
Let us denote v_{p}(n) the exponent of p in the prime representation of the natural number n.It is trvial the fact that for a,b \in \mathbb{N} we have v_{p}(ab)=v_{p}(a)+v_{p}(b) and also v_{p}(\frac{a}{b})=v_{p}(a)-v_{p}(b).It is also known the fact that : v_{p}(n!)=\sum_{k=1}^{\infty} \left[ \frac{n}{p^{k}} \right]=\left[\frac{n}{p}\right]+\left[\frac{n}{p^{2}}\right]+...
In order to prove \dbinom {np^{k}}{p^{k}} and p are coprime , we must show that v_{p}(\dbinom{np^{k}}{p^{k}})=0.
But this is true because:v_{p}(\dbinom{np^{k}}{p^{k}})=v_{p}(\frac{(np^{k})!}{p^{k}!(np^{k}-p^{k})!})=v_{p}((np^{k})!)-\left(v_{p}(p^{k}!)+v_{p}((np^{...
=\sum_{i=1}^{\infty} \left[\frac{np^{k}}{p^{i}}\right]- \sum_{i=1}^{\infty} \left(\left[\frac{p^{k}}{p^{i}}\right]+\left[\fra...
=n(p^{k-1}+p^{k-2}+...+p+1)-(p^{k-1}+p^{k-2}+...+p+1)-(n-1)(p^{k-1}+p^{k-2}+...+p+1)+\sum_{i=1}^{\infty} \left[\frac{n}{p^{i}...
Because \gcd(n,p)=1 it follows that \sum_{i=1}^{\infty} \left[\frac{n}{p^{i}}\right]=\sum_{i=1}^{\infty} \left[\frac{n-1}{p^{i}}\right] so v_{p}(\dbinom{np^{k}}{p^{k}})=0 meaning \gcd(p,\dbinom{np^{k}}{p^{k}})=1.
 
 
Rust
Birch & Swinnerton Dyer

Posts: 3853
Post Posted: Jun 21, 2008, 10:54 am • # 4 


ZetaX wrote:
Trivial by Lucas theorem.
Or write the binomial coefficient out and look how often each term is divisible by p.
You even have (for p > 3) the much stronger property \binom{n \cdot p^k}{p^k} \equiv n \mod p^{k + 3} for arbitrary n.

It is true only for Wolstenholm's prime.
Exactly \binom{np^k}{p^k}\equiv n\mod p^{k+2}, p>3.
 
 
nguyenvuthanhha
Riemann Hypothesis
User avatar

Posts: 304
Location: Hồ Chí Minh city
Viet Nam    United Kingdom
Post Posted: May 24, 2009, 2:10 am • # 5 


A good solution , Vrajitoarea Andrei :)

_________________
Love the simplicity
 
 
Display posts from previous:  Sort by  
  Share on Facebook Previous topic | Next topic 

Community » Olympiad Section » Number Theory » Number Theory Proposed & Own Problems

All times are UTC - 8 hours [ DST ]
Share: Facebook

Moderators: MithsApprentice, N.T.TUAN, Peter, darij grinberg, orl, pbornsztein, freemind, Megus, amfulger, harazi, ZetaX, Arne, High School Olympiad Moderators

Post new topic Reply to topic  Page 1 of 1
  [ 5 posts ] 

Login
Username:   Password:   Log me on automatically each visit  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Calculus
NEW! A complete single-variable calculus course, with an emphasis on problem solving and rigorous thinking.
the Art of Problem Solving
Volume 1: the Basics
Used for over 16 years! Lots of MATHCOUNTS and AMC problems and topics!