After deleting the multiples of $2$ and multiples of $3$ from list of integers from $1$ to $N$, why are a fifth of the numbers still multiples of 5?

Think of the pattern of numbers modulo $30$ (we choose $30$ because $30=2\times3\times5$).

After removing multiples of $2$ and $3$ you are left with

$30n+1$, $30n+5$, $30n+7$, $30n+11$, $30n+13$, $30n+17$, $30n+19$, $30n+23$, $30n+25$, $30n+29$

Of these $10$ numbers just $2$ are multiples of 5 - the second one $30n+5$ and the ninth one $30n+25$. Since this pattern repeats, one fifth of the remaining numbers are multiples of 5, even though they are not evenly spaced among the remaining numbers.

Tags:

Combinatorics

Prime Numbers

Elementary Number Theory

Related

How can I calculate $\lim_{n \rightarrow \infty} \frac {e^n(2n)!}{(4n)^nn!}$ Are there primes $p=47\cdot 2^n+1$? Trying to evaluate $\int_{0}^{\infty}\frac{\ln(1+x^3)}{1+x^3}\frac{dx}{1+x^3}$ Why is continuity characterized with open sets? Why is a manifold called a manifold? Are $1+p^3+p^6$ and $1+p^4+p^8$ coprime? $2\mathbb{Z}$ is not ring isomorphic to $3\mathbb{Z}$, But Why? (Verify Me) Why can a real number be defined as a Dedekind cut, that is, as a set of rational numbers? How can I tell if a matrix is diagonalizable knowing only the trace, one eigenvalue, and a result of the characteristic polynomial? How to prove there exists an uncountable well-ordered set without using axiom of replacement Morphism between thick fibers of schemes extends to a neighbourhood Absolute Galois group of $\Bbb Q_p$ while varying $p$

Recent Posts