Neat Number Theory/Discrete Math Problem (Pt. II)
Point of post: This is a continuation of this post.
We now prove a much more generalized theorem. Namely:
Theorem: Let with prime factorization be fixed and define
From this define
Proof: We first note thta
so that if
we see that
(where the notation was discussed in the last post). Thus,
Thus, to find it suffices to find
To do this we recall that the Generalized Inclusion-Exclusion Principle states that if then
So, note that since each is relatively prime that
from where our first claim follows. The second claim follows immediately since in general
where denotes asymptotic equivalence. Thus,
References: For more information see:
1. Rosen, Kenneth H. Discrete Mathematics and Its Applications. Boston: McGraw-Hill Higher Education, 2007. Print.