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

  • 1
    $\begingroup$ There is nothing deep there. Every 4. number is divisible by $4$, so the other $3/4$ of all numbers are not. $\endgroup$ – Simon Nov 10 '16 at 22:42
  • $\begingroup$ ok, but under condition " it's stated that" for large n not for every integer n $\endgroup$ – zeraoulia rafik Nov 10 '16 at 22:43
  • $\begingroup$ We're only looking at positive integers: "${3\over 4}$ of the positive integers less than $n$". So e.g. if $n=53.67$, the positive integers less than $n$ are $1, 2, 3, . . . , 51, 52, 53$; and all but $13$ of these (that is, very close to ${3\over 4}$) are not divisible by $4$. $\endgroup$ – Noah Schweber Nov 10 '16 at 22:45
  • $\begingroup$ sorry i'm still don't understanding it , I ask if there is any theory in number theory show that event if i'm true that is always true , for example how do i can know that the number of integers less than :10 ^5 only 1/4 of them are divisible by 4 ? $\endgroup$ – zeraoulia rafik Nov 10 '16 at 22:53
  • $\begingroup$ Well, if you look at small $n$, say $n < 12$ to have something concrete, the fraction can differ significantly from $3/4$. But if $n$ is large, then $1 - \frac{1}{n}\bigl\lfloor \frac{n}{4}\bigr\rfloor$ is always very close to $3/4$. $\endgroup$ – Daniel Fischer Nov 10 '16 at 23:00

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$.

  • $\begingroup$ Nice answer , then "Squeeze theorem show that " $\endgroup$ – zeraoulia rafik Nov 10 '16 at 23:09

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.