# Abstract Nonsense

## Neat Number Theory/Discrete Math Problem

Point of post: In this post I will discuss  the following simple problem:

” Let $E_n=\left\{m\leqslant n:(m,15)=1\right\}$, then define $a_n=\left|E_n\right|$. Compute $\displaystyle \lim_{n\to\infty}\frac{a_n}{n}$

where $(\cdot,\cdot)$ stands for $\text{g.c.d.}$. We will solve this problem in two ways, the first of which is simple but the second of which generalizes to a much, much more general case which we will discuss in the next post.

Problem: Let $E_n=\left\{m\leqslant n:(m,15)=1\right\}$, then define $a_n=\left|E_n\right|$. Compute $\displaystyle \lim_{n\to\infty}\frac{a_n}{n}$.

Initial Proofs

Proof (1): Note first that $\displaystyle \lim_{n\to\infty}\frac{a_n}{n}$ converges. To see this we first note that $a_n$ is increasing since

$E_n\subseteq E_{n+1}$ Next we recall the well known fact that

$(k,15)=1\Leftrightarrow (15m+k,15)=1$

So, in particular thus $E_{15(n+1)}=E_{15n}\cup\left\{k+15n:k\in E_{15}\right\}$. So, $a_{15(n+1)}=a_{15n}+a_{15}$ and so by induction $a_{15n}=na_{15}$ and since $a_{15}=8$ we may conclude that $a_{15n}=8n$. Thus, if $\gamma_{15}(n)$ is defined as reduction $\text{mod }n$we can see that

$a_{n-\gamma_{15}(n)}\leqslant a_n\leqslant a_{n+15-\gamma_{15}(n)}$

note though that since $15\mid n-\gamma_{15}(n),n+15-\gamma_{15n}(n)$ we  see that

$\displaystyle \frac{n-\gamma_{15}(n)}{15}\quad \frac{n+15-\gamma_{15}(n)}{15}$

are integers and so applying our above observation about $a_{15m}$ we note that

$a\displaystyle _{n-\gamma_{15}(n)}=a_{15\left[\frac{n-\gamma_{15}(n)}{15}\right]}=8\left[\frac{n-\gamma_{15}(n)}{15}\right]$

and

$\displaystyle a_{n+15-\gamma_{15}(n)}=a_{15\left[\frac{n+15-\gamma_{15}(n)}{15}\right]}=8\left[\frac{n+15-\gamma_{15}(n)}{15}\right]$

so we may conclude that

$\displaystyle \frac{8}{15}\left[1-\frac{\gamma_{15}(n)}{n}\right]\leqslant\frac{a_n}{n}\leqslant \frac{8}{15}\left[1+\frac{15-\gamma_{15}(n)}{n}\right]$

and since $\displaystyle \frac{\gamma_{15}(n)}{n},\frac{15-\gamma_{15}(n)}{n}\leqslant \frac{15}{n}$. Thus, we may conclude by the Squeeze Theorem that

$\displaystyle \lim_{n\to\infty}\frac{a_n}{n}=\frac{8}{15}$

Proof (2): In this post we find explicitly the value of $a_n$ and from there conclude. We begin by noting that

$(m,15)\ne 1\Leftrightarrow 3\mid m\text{ or }3\mid n$

thus, it clearly follows that if

$A_n=\left\{m\leqslant n:3\mid m\right\}$

and

$B_n=\left\{m\leqslant n:5\mid n\right\}$

that

$[n]=E_n\sqcup\left(A_n\cup B_n\right)$

(where $\sqcup$ is merely notation for $[n]=E_n\cup \left(A_n\cup B_n\right)$ and $E_n\cap\left(A_n\cup B_n\right)=\varnothing$, i.e. that $\left\{E_n,A_n\cup B_n\right\}$ forms a partition of $[n]$). Thus,

$n=\left|[n]\right|=\left|E_n\sqcup \left(A_n\cup B_n\right)\right|=\left|E_n\right|+\left|A_n\cup B_n\right|=a_n+\left|A_n+B_n\right|$

so that

$a_n=n-\left|A_n\cup B_n\right|$

thus it suffices to compute $\left|A_n\cup B_n\right|$. To do this we recall the simple law that

$\left|A_n\cup B_n\right|=\left|A_n\right|+\left|B_n\right|-\left|A_n\cap B_n\right|$

Now, it is fairly obvious that

$\displaystyle \left|A_n\right|=\left\lfloor\frac{n}{3}\right\rfloor$

and

$\displaystyle \left|B_n\right|=\left\lfloor \frac{n}{5}\right\rfloor$

and since

$A_n\cap B_n=\left\{m\leqslant n:3\mid m\text{ and }5\mid m\right\}=\left\{m\leqslant n:15\mid m\right\}$

it follows that

$\displaystyle \left|A_n\cap B_n\right|=\left\lfloor\frac{n}{15}\right\rfloor$

Putting this all together we get that

$\displaystyle a_n=n-\left|A_n\cup B_n\right|=n-\left\lfloor\frac{n}{3}\right\rfloor-\left\lfloor\frac{n}{5}\right\rfloor+\left\lfloor\frac{n}{15}\right\rfloor$

so that

$\displaystyle \frac{a_n}{n}=1-\frac{1}{n}\left(\left\lfloor \frac{n}{3}\right\rfloor+\left\lfloor\frac{n}{5}\right\rfloor-\left\lfloor\frac{n}{15}\right\rfloor\right)$

But, evidently since in general $x-1\leqslant\lfloor x\rfloor\leqslant x$

$\displaystyle 1-\frac{1}{3}-\frac{1}{5}-\frac{1}{15}-\frac{1}{n}\leqslant \frac{1}{n}\left(\left\lfloor\frac{n}{3}\right\rfloor+\left\lfloor\frac{n}{5}\right\rfloor-\left\lfloor\frac{1}{15}\right\rfloor\right)\leqslant 1-\frac{1}{3}-\frac{1}{3}+\frac{1}{15}+\frac{2}{n}$

we may conclude by the Squeeze Theorem that

$\displaystyle \lim_{n\to\infty}\frac{a_n}{n}=1-\frac{1}{3}-\frac{1}{5}+\frac{1}{15}=\frac{8}{15}$.