Saturday, 31 August 2013

elementary number theory - Prove that NlfloorN/prfloor=lfloorfracp1pleft(N+1right)rfloor for positive N and prime p



I am counting the number of positive integers less than or equal to some positive integer N and not divisible by some prime p. This gets generalized for k primes where I use the principle of inclusion-exclusion for this result. The simple result for a single prime is NNp. However, I have noticed by experiment that this is also equal to p1p(N+1). I am looking for a proof of this relation if true.



Answer



Consider that N may be expressed as N=ap+b for an integer a and integer 0bp1. Using this, the left side of your equation becomes



NN/p=ap+ba



Consider the numerator of the right side of your equation, i.e.,



(p1)(N+1)=(p1)(ap+b+1)=ap2+(b+1a)p(b+1)



Since 0bp1, then 1b+1p. As such, for any integer M, including M=0, we have that




Mp(b+1)p=M1



Using (2) and (3) in the right side of your equation gives



(p1)(N+1)p=ap+(b+1a)+(b+1)p=ap+ba



As such, the LHS (from (1)) is always equal to the RHS (from (4) above), so your equation always holds. Note, this is true not only for primes p, but for all positive integers p, as I didn't use any particular properties of primes anywhere in the proof above.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...