Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm not sure of the best way to ask this question but I will try with an example of my problem:

I have three numbers, 3 and 5 and x.

x always starts as zero.

There are two possible events that can occur:

  • Someone buys an apple -> I add 3 to x
  • Someone buys a banana -> I add 5 to x

If someone makes a purchase then I can use mod3, mod5 and mod8 to determine if they bought an apple, a banana or both.

This is fine for any number lower than 15. Once we get to 15 and above we do not know whether someone only bought apples, only bought bananas or bought a combination of both.

So my question is, are there any three numbers I can always use to determine if they bought just apples, just bananas or both?

Or is there a better way of doing this all together?

share|cite|improve this question
Why not just maintain two variables, one for each fruit? – J. M. Apr 20 '12 at 15:07
@J.M. When I tried to answer to that comment with a "why I can't" response I realised I have completely over complicated my problem. I am going to delete the question, but thank you for making me re-think the steps that I am taking! – My Head Hurts Apr 20 '12 at 15:13
up vote 2 down vote accepted

Short answer: No, there are no such numbers. Not if you are adding. Take any $p,q \in \mathbb{N}$. Then, at one point you may have $x = pq$ and can't decide whether that is because someone bought $q$ apples or $p$ bananas.

You can, however, do this by using multiplication. Initialize $x := 1$ and choose $p := 2$, $q := 3$ (or any other distinct primes). Multiply $x$ by $p$ or $q$ accordingly. To get the information about how much was bought, factorise $x$. I do not recommend this for practical purposes, but in theory it works fine.

share|cite|improve this answer
After rethinking through my problem, I have decided I am over-complicating the entire issue. Thanks for the answer and since you offered an alternative solution then I will mark it as accepted. – My Head Hurts Apr 20 '12 at 15:19

If a,b,c are the numbers you want, a|LCM(a,b) and b|LCM(a,b), that means when c>=LCM(a,b), you will never know c whether someone only bought apples, only bought bananas or bought a combination of both.

share|cite|improve this answer
+1 thanks :) However I am accepting the answer from @m_l as they offered an alternative solution. – My Head Hurts Apr 20 '12 at 15:19

This is the coin problem. If the two values are a,b and gcd(a,b)=1, you can represent all numbers above ab-a-b-1. Once you get to ab you can't tell whether you have a b's or b a's.

share|cite|improve this answer
+1 thanks for the link and the almost layman explanation. It always makes me feel better when they have a name for my problem :) – My Head Hurts Apr 20 '12 at 15:23
@MyHeadHurts: not only does it make you feel better to know the name of the problem, but it gives you something to search on. I have received the same as 18 point problem for… and found some interesting articles that way. – Ross Millikan Apr 20 '12 at 15:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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