9
$\begingroup$

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?

  • 2
    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?2012-05-12
  • 1
    Apparently the desired meaning is "not divisible by 2 and not divisible by 5". But the question could have been worded better.2012-05-12
  • 1
    @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.2012-05-12

3 Answers 3

6

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

  • 0
    You are presuming $p$ and $q$ are prime (or at least co-prime)2012-05-12
  • 0
    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.2012-05-12
  • 0
    Whilst a perfectly valid answer, Siklos doesn't assume knowledge of the inclusion-exclusion principle (the booklet is intended for pre-undergraduates)2012-05-12
  • 0
    @Milosz Re: your [suggested edit](http://math.stackexchange.com/suggested-edits/6394) 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.2012-05-12
  • 0
    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!2012-05-12
  • 0
    @Milosz: Thanks! I've included TonyK's answer.2012-05-12
4

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

  • 0
    Interesting. Can you explain _why_ this is the case?2012-05-12
  • 1
    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}$.2012-05-12
4

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

  • 0
    Could you elaborate on why n is divisible by $p$ or $q$ if and only if $(pq)^3−n$ is?2012-05-12
  • 1
    @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.2012-05-12
  • 1
    @Milosz: anon has it wrong, using 'and' instead of 'or'. But you just have to do the same thing for $p$ and $q$ separately.2012-05-12
  • 0
    (Oh, oops. Derp.)2012-05-12
  • 0
    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$.2012-05-13