## Neat Number Theory/Discrete Math Problem (Pt. II)

**Point of post: **This is a continuation of this post.

**Generalization**

We now prove a much more generalized theorem. Namely:

**Theorem: **Let with prime factorization be fixed and define

From this define

then

and thus

**Proof:** We first note thta

so that if

we see that

(where the notation was discussed in the last post). Thus,

so that

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

thus

Thus,

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.

[…] of post: Since I found this problem enjoyable, for some odd reason, I thought I’d also generalize the methodology in the first […]

Pingback by Neat Number Theory/Discrete Math Problem (Pt. III) « Abstract Nonsense | November 6, 2010 |