Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I read here in wikipedia for understanding distributions of square free , i find the following mathematical expression for large $n$ :" $ 3/4$ of the positive integers less than n are not divisible by $4$, $8/9$ of these numbers are not divisible by $9$ ? My question here is :
Really i'm confused how the titled approximation is true and what are the mathematical theories in number theory or in probability affirmed it's truthness ?
Thank you for any help
A statement of the form "for large $n$, fraction $p$ of the positive integers less than $n$ are in set $S$" is to be interpreted as meaning $$ \lim_{n \to \infty} \dfrac{| \{1,2,\ldots,n-1\} \cap S |}{n-1} = p $$
In this case with $S$ the set of integers not divisible by $4$, it's easy to prove (e.g. by induction) that $$|\{1,2,\ldots,n-1\} \cap S| = n - 1 - \lfloor (n-1)/4 \rfloor$$ so that $$ \frac{3}{4} = \frac{n-1 - (n-1)/4}{n-1} \le \frac{n-1 - \lfloor (n-1)/4 \rfloor}{n-1} \le \frac{n-1 - (n-1)/4 + 1}{n-1} = \frac{3}{4} + \frac{1}{n-1} $$ Then the Squeeze Theorem shows the limit is $3/4$.
Let us say $n = 5$.
The integers $1, 2, 3, 4$ are below it and $1, 2, 3$ are not divisible by 4. There are 4 numbers below $5$ and $3/4$ are not divisible by 5.
Now consider 9. The integers below it are $1, 2, 3, 4, 5, 6, 7, 8$ and again we see that $1, 2, 3, 5, 6, 7$ are not divisible by 4, which makes $6/8 = 3/4$ of them.
Now imagine a really large $n $: you have the integers $1, 2, 3, 4, 5, \cdots, n-1$. Now you group those number 4 by 4, like so: $(1, 2, 3, 4), (5, \cdots), \cdots, (\cdots, n-1) $. How many groups are there. Well, there are $n/4$ groups. Almost. For some $n $ it might not be exactly the case right? For small $n $, say 6, we could only form one complete group. Some $n $ do not allow only full groups, leaving 1, 2 or 3 numbers without a group. But for now let us assume there are $n/4$ complete groups.
Then 3 out of every 4 numbers of each group would not be divisible by 4 and hence $3\times n/4$ numbers would not be divisible by four. But $3\times n/4$ corresponds exactly to $3/4$ of the numbers.
If $n $ gets really large, $3n/4$ gets really large and you don't even bother with missing by 1 or 2 or 3 when $n $ is such that it doesn't allow you to only form full groups.
What you did for 4, you can do for any $k $, thus showing that for $n $ big enough, $\frac{k-1}{k} $ of the numbers are not divisible by $k $ (which is the same as saying that $1/k $ of them are.
It actually says "for large n", and is an approximation. Consider all our possibilities of integers k mod 4,
k $\equiv 0,1,2,3$ (mod 4), i.e. $\{1,2, ... , k\} \equiv \{1,2,3,0,1,2,3,0...j\}. (mod 4)$, where j \equiv k (mod 4)$ and each 0 corresponds to a multiple of 4. So suppose k is the closes positive integer to n.
If the closest integer to n is a multiple of 4, then , $\mathbb{P}$(Non multiple of 4) = $\frac{3k}{4k} = \frac{3}{4}$. And we are done. - Here, I've just scaled up by k, clearly there aren't k lots of multiples of 4, but effectively we're multiplying however many lots there are by $\frac{k}{\mathrm{actual\hspace{1mm}lots\hspace{1mm} of\hspace{1mm} multiples\hspace{1mm} of\hspace{1mm} 4.}}$ and we end up with an equivalent fraction. If you don't believe me, plug in some values for the formula and you'll see that it works.
But, if the closest integer to n is not a multiple of 4, then there will be extra non-multiples of 4 represented by j. Where at most, j = 3. i.e.
$\mathbb{P}$(Non multiple of 4) = $\frac{3k + j}{4k}$.
And clearly, $lim_{k} \to \infty = 3/4$ since j is a constant.
