Counting integers $n$ such that $1\leq n \leq 200$ and $n$ is not divisible by $2$ nor $5$

Question

How many integers $n$ are there such that $1\leq n \leq 200$ and $n$ is not divisible by 2 nor 5?

Here is just my trying. By the hypothesis I just let by contradiction. It means that I find the integers $n$ that is divisible by $2$ or $5$.

$n=2k_1$ and $n=5k_2$ for $k_1,k_2\in\mathbb{N}$.So that I can write

$$0\leq n\leq 200$$ $$0\leq 2k_1\leq200$$ $$0\leq k_1\leq 100$$ So there are $100$ integers of $k_1$ that satisfies that n is divisible by $2$.

By the same way I get $$0 \leq k_2 \leq 40$$ So there are $40$ integers of $k_1$ that satisfies that n is divisible by $5$. But I find the n that is divisible by $2$ and $5$. Since $LCM(2,5)=10$. Let $n=10k_3$

By the Same way I get $$0\leq k_3 \leq 20$$ So there are 20 integers of $k_3$ that satisfies $n$ is divisible by 2 and 5.

Hence there are 120 integers of n that is divisible by $2$ nor $5$. By contradiction there are 80 integers of n that is being find.

---

So please help to tell me ! That is right or wrong. If you have other hints help to tell me.

Answer 1

I wouldn't call this approach "by contradiction;" rather, if anything, it is typically referred to as the complementary approach. Want to find a quantity satisfying a condition? The complementary approach is to find the overall quantity disregarding such a condition, and then subtract off the ones not satisfying that condition.

Your reasoning is also okay, but it could be a bit more succinct. Here's how I would do it ...

---

Define

$$A_n := \{ k \in \Bbb Z \mid k \in [1,200] \text{ and } n \text{ divides } k \}$$

Thus, for instance, $A_2 = \{2,4,6,\cdots,200\}$.

In your problem, you want to find those integers $n \in [1,200]$ where neither $2$ nor $5$ divide $n$. The complementary approach, then, is to note that you have $200$ possible numbers, and then subtract off the invalid ones. Thus, you would subtract off $|A_2|$ and $|A_5|$. But beware! This "double subtracts" the members of $|A_{10}|$ since all multiples of ten are in both sets. (This is a particular instance of the principle of inclusion and exclusion.) Thus you have to add back $|A_{10}|$.

Thus, the quantity you seek is

$$200 - |A_2| - |A_5| + |A_{10}|$$

The benefit of this framing is that, if $n$ divides $200$, then $|A_n| = 200/n$, making this calculation satisfyingly easily. We see that it is, for you,

$$200 - 100 - 40 + 20 = 80$$

as you proposed!

---

Your method is not invalid, but I feel like this framing of the problem makes everything a lot easier to follow, personally. For instance, you don't have to go through every series of inequalities; the definition of the $A_n$ makes those results almost obvious, and generalizes all three cases you check. But on the other hand, if you prefer your method and framing, feel free to use it - probably a matter of preference in the end.

Answer 2

I think that is much easier to think in terms of the euler function. We know that when n=200, this function give us the value 80, so there are 80 numbers between 1 and 200 that do not have a 2 or 5 in its factorisation, and the problem is over.

Answer 3

I agree with the other responses but offer an informal [i.e. intuitive rather than proven] alternative approach.

Consider the numbers $1, 2, \cdots, 10.$ Of these 10 numbers, exactly 4 are not divisible by either 2 or 5. Further, $10$ is a common multiple of $2$ and $5$. Therefore, I would intuitively (that is informally) expect the pattern to repeat for the numbers 11 through 20, 21 through 30, ...

Since there are 4 such numbers in the set $\{1,2, \cdots, 10\}$ and since $\frac{200}{10} = 20$, I would expect the computation to be
$4 \times 20 = 80.$

Edit
In hindsight, it occurs to me that since 10 is a common multiple of both 2 and 5, then given that $k$ is not divisible by either 2 or 5, it seems immediate that any number of the form $k + 10r$ [where $r$ is a positive or negative integer] must also not be divisible by either 2 or 5.

Edit-2
I'm not sure if what I am about to write has been covered by what others are referring to as the Euler function. Anyway...
With $2$ and $5$ relatively prime, you can intuitively regard divisibility by 2 (chance = 1/2) and divisibility by 5 (chance = 1/5) as independent events.

This means that the desired computation can be informally regarded as
$200 \times [1 - (1/2)] \times [1 - (1/5)].$
This approach obviously requires that if the range contains $n$ consecutive numbers, then $n$ must be a common multiple of $2$ and $5.$

Answer 4

Not a 'real' answer, but it was too big for a comment.

I wrote and ran some Mathematica code:

In[1]:=Length[ParallelTable[
  If[TrueQ[If[IntegerQ[n/2] \[Or] IntegerQ[n/5], True, False]], 
   Nothing, n], {n, 1, 200}]]

Running the code gives:

Out[1]=80

So, when we look at your question there are $80$ numbers in the range $1\le\text{n}\le200$ such that $\text{n}$ does not divide $2$ and $5$.

---

Using Mathematica we can look at more complicated versions of this statement:

In the range $1\le\text{n}\le10^9$ there are $400000000$ numbers that does not divide $2$ and $5$:

In[2]:=Length[ParallelTable[
  If[TrueQ[If[IntegerQ[n/2] \[Or] IntegerQ[n/5], True, False]], 
   Nothing, n], {n, 1, 10^9}]]

Out[2]=400000000

In the range $1\le\text{n}\le200$ there are $80$ numbers that does not divide $2$ and $5$ and $8$:

In[3]:=Length[ParallelTable[
  If[TrueQ[If[IntegerQ[n/2] \[Or] IntegerQ[n/5] \[Or] IntegerQ[n/8], True, False]], 
   Nothing, n], {n, 1, 200}]]

Out[3]=80

In the range $1\le\text{n}\le10^9$ there are $400000000$ numbers that does not divide $2$ and $5$ and $8$:

In[4]:=Length[ParallelTable[
  If[TrueQ[If[IntegerQ[n/2] \[Or] IntegerQ[n/5] \[Or] IntegerQ[n/8], True, False]], 
   Nothing, n], {n, 1, 10^9}]]

Out[4]=400000000

In the range $1\le\text{n}\le10^9$ there are $285714286$ numbers that does not divide $2$ and $3$ and $4$ and $7$ and $9$:

In[5]:=Length[ParallelTable[
  If[TrueQ[If[
     IntegerQ[n/2] \[Or] IntegerQ[n/3] \[Or] IntegerQ[n/4] \[Or] 
      IntegerQ[n/7] \[Or] IntegerQ[n/9], True, False]], Nothing, 
   n], {n, 1, 10^9}]]

Out[5]=285714286