# What is the greatest number of pencils that you cannot buy? [duplicate]

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 ?

• Unfrotunately this is a duplicate of this earlier question: A man possesses a large quantity of stamps – Jaap Scherphuis Apr 12 at 12:55
• @JaapScherphuis , but the question posted by you, does not address the general cases ..it addresses only 2 specific values of p and q . Having said this, if you feel that this question is a duplicate, then we can close it . – Hemant Agarwal Apr 12 at 13:28
• The earlier question has an answer that covers the general case - see puzzling.stackexchange.com/questions/28490/… – Steve Apr 12 at 13:38

## 1 Answer

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.

• 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 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 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 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 at 18:33
• @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 at 21:33