Abstract Nonsense

Crushing one theorem at a time

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 n_0\in\mathbb{N} with prime factorization p_1^{\alpha_1}\cdots p_{k}^{\alpha_k} be fixed and define

E_n=\left\{m\leqslant n:(m,n_0)=1\right\}

From this define



\displaystyle a_n=n-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor

and thus

\displaystyle \lim_{n\to\infty}\frac{a_n}{n}=1-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left(\prod_{s\in S}p_s\right)^{-1}

Proof: We first note thta

(m,n_0)=1\Leftrightarrow p_1\nmid m\text{ and }\cdots\text{ and }p_k\nmid m

so that if

A_{j,n}=\left\{m\leqslant: p_j\mid m\right\},\quad j=1,\cdots,k

we see that

[n]=E_n\sqcup\left(A_{1,n}\cup\cdots\cup A_{k,n}\right)

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

\begin{aligned}n=\left|[n]\right|& =\left|E_n\sqcup\left(A_{1,n}\cup\cdots\cup A_{k,n}\right)\right|\\ &=\left|E_n\right|+\left|A_{1,n}\cup\cdots\cup A_{k,n}\right|\\ &=a_n+\left|A_{1,n}\cup\cdots\cup A_{k,n}\right|\end{aligned}

so that

a_n=n-\left|A_{1,n}\cup\cdots\cup A_{k,n}\right|

Thus, to find a_n it suffices to find

\left|A_{1,n}\cup\cdots\cup A_{k,n}\right|

To do this we recall that the Generalized Inclusion-Exclusion Principle states that if S_j\overset{\text{def.}}{=}\left\{S\subseteq\{:|S|=j\right\} then

\displaystyle \left|A_{1,k}\cup\cdots\cup A_{k,n}\right|=\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left|\bigcap_{s\in S}A_{s,n}\right|

So, note that  since each p_\ell,\quad \ell=1,\cdots,k is relatively prime that

\displaystyle \bigcap_{s\in S}A_{s,n}=\left\{m\leqslant n:p_s\mid m\text{ for all }s\in S\right\}=\left\{m\leqslant n:\prod_{s\in S}p_s\mid m\right\}


\displaystyle \left|\bigcap_{s\in S}A_{s,n}\right|=\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor


\displaystyle \left|A_{1,n}\cup\cdots\cup A_{k,n}\right|=\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left|\bigcap_{s\in S}A_{s,k}\right|=\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor

from where our first claim follows. The second claim follows immediately since in general

\displaystyle \lfloor x\rfloor\sim x

where \sim denotes asymptotic equivalence. Thus,

\displaystyle \lim_{n\to\infty}\frac{a_n}{n}=\lim_{n\to\infty}\left(1-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\frac{1}{n}\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor\right)=1-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left(\prod_{s\in S}p_s\right)^{-1}


References: For more information see:

1. Rosen, Kenneth H. Discrete Mathematics and Its Applications. Boston: McGraw-Hill Higher Education, 2007. Print.


November 4, 2010 - Posted by | Fun Problems | , , ,

1 Comment »

  1. […] 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 | Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: