1
  1. A shop sells pencils in boxes of 31 and 38. What’s the highest number of pencils a person cannot buy?

In general, if the shop is selling pencils in boxes of p and q, then what is the highest number of pencils one cannot buy when

2. p and q are relatively prime

3. p and q are not relatively prime ?

Hemant Agarwal
  • 2,912
  • 14
  • 31

1 Answers1

3

I would be surprised if this question hasn't appeared before so apologies in advance if answering a duplicate

We'll do question 2 first

Because $p$ and $q$ are coprime, each of $q, 2q,\ldots,(p-1)q$ will leave a different non-zero remainder when divided by $p$ and this set exhausts all possible remainders apart from zero. Hence, if we require a number of pencils, $x$ which is larger than $(p-1)q$ we can form that number by first identifying the appropriate remainder when $x$ is divided by $p$ and then adding an appropriate multiple of $p$ pencils to achieve $x$.

Since the remainder of $(p-1)q$ is the last to be picked up, the highest number of pencils which we cannot buy is $(p-1)q - p = pq-p-q$

This means the answer to question 1 is

$(38 \times 31) - 38 - 31 = 1109$

And question 3

If $p$ and $q$ are not relatively prime, then they share a common factor $d > 1$ so any number of pencils not divisible by $d$ cannot be bought and there is no highest number.

hexomino
  • 135,910
  • 10
  • 384
  • 563
  • Let's talk about the case where p and q are relatively prime . Let's talk about x > (p-1)q . Let's say that the remainder when x is divided by p is 3. You are saying that we should find aq such that aq/p gives remainder 3. Then, there will be some 'b' such that aq+bp = x. Am I right ? My question then is, what's the guarantee that there will be some 'b' such that aq+bp = x ? Secondly, when you say that the highest number of pencils that cannot be bought is (p-1)q - p ; then how did you figure out that it will be "-p" . Why can't it be any number y such that (p-1)q-p < y <= (p-1)q ? – Hemant Agarwal Apr 13 '21 at 16:00
  • Here are the answers to your questions: "Am I right ?" Yes "what's the guarantee that there will be some 'b' such that aq+bp = x" Consider x-aq, that leaves remainder zero when divided by p, hence it's divisible by p, hence equal to bp for some b. "Why can't it be any number y such that (p-1)q-p < y <= (p-1)q" Because all of these numbers leave a remainder that has already been covered by a smaller value. – hexomino Apr 13 '21 at 17:35
  • Please provide a proof for this line : "Because all of these numbers leave a remainder that has already been covered by a smaller value." I mean, what is the proof that ( "(p-1)q- p" is not covered but all the other numbers from "(p-1)q-p+1" to "(p-1)q" are covered by aq+bp. – Hemant Agarwal Apr 13 '21 at 18:20
  • Also, is it a mere coincidence that the answer is (p-1)q - p = (p-1)(q-1) -1? Or is there some logic behind the answer being ( p-1)(q-1) -1 ? – Hemant Agarwal Apr 13 '21 at 18:33
  • 1
    @HemantAgarwal Do you agree with the idea that the numbers $q, 2q, 3q,...(p-1)q$ all leave a different remainder when divided by $p$? – hexomino Apr 13 '21 at 21:33
  • yes ...that is clear ..It is also clear that all remainders apart from 0 are covered . – Hemant Agarwal Apr 13 '21 at 21:40
  • @HemantAgarwal Okay, so for each number $y$ with $(p-1)q-p <y \leq (p-1)q$ there is some $aq \leq y$ which has the same remainder as $y$ when divided by $p$, right? – hexomino Apr 13 '21 at 21:48
  • ok..let's call the remainder when (p-1)q is divided by p, "m" . I just realised that the remainder for (p-1)q -p when divided by p will also be "m". And therefore, there cannot be any aq < (p-1)q-p such that that the remainder for this aq and (p-1)q - p are the same . Can you now tell me how we can prove that there will be an aq < (p-1)q such that the remainder for this aq and for (p-1)q, when divided by p, are the same ? Because we just proved that (p-1)q gives a remainder m which no aq < (p-1)q can give. – Hemant Agarwal Apr 13 '21 at 23:06
  • Let us continue this discussion in chat. – hexomino Apr 13 '21 at 23:15