1
$\begingroup$
  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 ?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ Unfrotunately this is a duplicate of this earlier question: A man possesses a large quantity of stamps $\endgroup$
    – Jaap Scherphuis
    Apr 12, 2021 at 12:55
  • $\begingroup$ @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 . $\endgroup$
    – Hemant Agarwal
    Apr 12, 2021 at 13:28
  • 1
    $\begingroup$ The earlier question has an answer that covers the general case - see puzzling.stackexchange.com/questions/28490/… $\endgroup$
    – Steve
    Apr 12, 2021 at 13:38

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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 ? $\endgroup$
    – Hemant Agarwal
    Apr 13, 2021 at 16:00
  • $\begingroup$ 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. $\endgroup$
    – hexomino
    Apr 13, 2021 at 17:35
  • $\begingroup$ 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. $\endgroup$
    – Hemant Agarwal
    Apr 13, 2021 at 18:20
  • $\begingroup$ 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 ? $\endgroup$
    – Hemant Agarwal
    Apr 13, 2021 at 18:33
  • 1
    $\begingroup$ @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$? $\endgroup$
    – hexomino
    Apr 13, 2021 at 21:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.