# Number of integers not divisible by $p$ and $q$

Here's a part of question from Siklos' "Advanced Problems in Core Mathematics":

How many integers greater than or equal to zero and less than 1000 are not divisible by 2 or 5? What is the average value of these integers?

The solution is enclosed in the booklet (Question 11.), and might be worth taking a look at before attempting my actual question which is posed by Siklos at the end of his solution to the aforementioned question, but left to the reader to figure out.

The question is about what the general result is, i.e.:

How many integers greater than or equal to zero and less than $(pq)^3$ are not divisible by $p$ or $q$? What is the average value of these integers?

I had a look at a couple of cases, and some patterns do emerge, but I had no luck forming a general conjecture.

Added: As the first part of the question has been answered by Zev Chonoles, I thought I'll update the question with a interesting pattern that emerges when dealing with the second part, i.e. finding the average value of the integers.

First off, note that the number of integers becomes an arithmetic progression if we think in blocks of $pq$ numbers. So for $p=2$ and $q=5$ the number of integers not divisible by 2 or 5 is $4,8,12,16,\ldots$ for integers greater than or equal to zero and less than $10,20,30,40,\ldots$.

Then if we consider the integers in each such block, we notice that they can be paired to give the same sum, equal to the block size (a multiple of $pq$). Taking yet again $p=2$ and $q=5$ as an example, given $S_x=\{0,1,\ldots,x-1\}$:

$$\{n\in S_{20}: 2\nmid n\text{ or }5\nmid n\}=\{\color{red}{1},\color{green}{3},\color{blue}{7},\color{orange}{9},\color{orange}{11},\color{blue}{13},\color{green}{17},\color{red}{19}\}$$

Now I wonder, how can we explain this pattern and how can we use it to answer the second part of the question?

-
Note that the original says "not divisible by 2 or 5". Unfortunately, both with "and" and with "or", English is ambiguous due to lack of parentheses: does it mean "not (divisible by 2 or 5)", i.e. "not divisible by 2 and not divisible by 5", or does it mean "(not divisible) by 2 or 5" i.e. not divisible by 2 or not divisible by 5? –  Robert Israel May 12 '12 at 0:57
Apparently the desired meaning is "not divisible by 2 and not divisible by 5". But the question could have been worded better. –  Robert Israel May 12 '12 at 0:59
@Robert: I consider 'divisible by neither 2 nor 5' to be the only reasonable interpretation of 'not divisible by 2 or 5'; I don't consider it at all ambiguous. –  Brian M. Scott May 12 '12 at 4:35

Here's an answer to your first question (I assume $p$ and $q$ are prime numbers, though the following argument works just as well for any relatively prime integers $p$ and $q$): let $S=\{0,1,\ldots,(pq)^3-1\}$. Then by the inclusion-exclusion principle,

$$\#\{n\in S: p\nmid n\text{ and }q\nmid n\}=$$ $$\#S\;\;-\;\;\#\{n\in S: p\mid n\}\;\;-\;\;\#\{n\in S: q\mid n\}\;\; + \;\;\#\{n\in S: p\mid n\text{ and }q\mid n\}$$

which is just $$p^3q^3-p^2q^3-p^3q^2+p^2q^2=p^2q^2(pq-q-p+1)=p^2q^2(p-1)(q-1).$$

TonyK has answered the second question (be sure to vote up his answer too!):

Write out the numbers from 1 (not 0!) to $(pq)^3 - 1$ that are not divisible by $p$ or $q$. Now write the same sequence backwards underneath the first one. Each column will sum to $(pq)^3$, because $n$ is divisible by $p$ or $q$ if and only if $(pq)^3 - n$ is. So the average value is $(pq)^3/2$.

-
You are presuming $p$ and $q$ are prime (or at least co-prime) –  Henry May 12 '12 at 0:59
That's true, I guess I'd assumed that was the case as those are the letters traditionally used for primes, but I should edit my answer to state that explicitly. –  Zev Chonoles May 12 '12 at 1:00
Whilst a perfectly valid answer, Siklos doesn't assume knowledge of the inclusion-exclusion principle (the booklet is intended for pre-undergraduates) –  Daniel Freedman May 12 '12 at 12:49
@Milosz Re: your suggested edit to this answer. The phrase (not X) or (not Y) is not logically equivalent to the plain-English phrase neither X nor Y. It is clear you mean the latter in your question, but you wanted to edit the former into this answer. The logical phrasing of the latter is actually (not X) and (not Y), which is what Zev already has. No worries, I just wanted you to know why the edit wasn't accepted. –  anon May 12 '12 at 13:00
Zev, if you can incorporate TonyK's answer to the second part of the question (crediting Tony, of course), I'll be happy to accept your answer. @anon my mistake, thanks for pointing that out! –  Milosz Wielondek May 12 '12 at 15:35
show 1 more comment

Just to add to Zev Chonoles's answer, if $p$ and $q$ have a highest common factor of $h$ then the calculation becomes

$$p^3q^3-\frac{p^3q^3}{p}-\frac{p^3q^3}{q}+\frac{\frac{p^3q^3}{h}}{\frac{p}{h}\times \frac{q}{h}} = p^2 q^2 (pq-p-q+h)$$

-
Interesting. Can you explain why this is the case? –  Milosz Wielondek May 12 '12 at 15:30
Because the number of the first $p^3 q^3$ numbers divisible by both $p$ and $q$ is the same as the number of first $\frac{p^3 q^3}{h}$ numbers divisible by both $\frac{p}{h}$ and $\frac{q}{h}$, and $\frac{p}{h}$ and $\frac{q}{h}$ are coprime while $\frac{p}{h} \times \frac{q}{h}$ divides $\frac{p^3 q^3}{h}$. –  Henry May 12 '12 at 18:06
Write out the numbers from 1 (not 0!) to $(pq)^3 - 1$ that are not divisible by $p$ or $q$. Now write the same sequence backwards underneath the first one. Each column will sum to $(pq)^3$, because $n$ is divisible by $p$ or $q$ if and only if $(pq)^3 - n$ is. So the average value is $(pq)^3/2$.
Could you elaborate on why n is divisible by $p$ or $q$ if and only if $(pq)^3−n$ is? –  Milosz Wielondek May 12 '12 at 15:29
@Milosz: Without using modular arithmetic, we can say this: If $p|n$ and $q|n$ then $n=ap$ and $n=bq$ for some integers $a,b$. Then $$p\big(p^2q^3-a\big)=(pq)^3-n=q\big(p^3q^2-b\big),$$ hence $p,q|(pq)^3-n$. The same idea can be used in the other direction for the converse. –  anon May 12 '12 at 15:59
@Milosz: anon has it wrong, using 'and' instead of 'or'. But you just have to do the same thing for $p$ and $q$ separately. –  TonyK May 12 '12 at 20:03
It doesn't matter whether you start at $0$ or $1$ or whether you finish at $p^3q^3$ or as the question does at $p^3q^3-1$, since both $0$ and $p^3q^3$ are divisible by $p$ and $q$. –  Henry May 13 '12 at 10:11