February 23rd, 2018, 01:41 AM  #1 
Member Joined: Jun 2017 From: Lima, Peru Posts: 46 Thanks: 1 Math Focus: Calculus  How do I find the number of elements in a problem involving least common multiples?
I'm not sure if least common multiples applies to this problem. Over a table there is a certain number of muffins. If we count them by multiples of four the remainder is three. If we count them by multiples of six the remainder is five. If we count them by multiples of ten the remainder is nine. What is the least number of muffins over the table? What I tried to do is to build up a series of equations which are shown below: $\textrm{I defined the number of muffins as n}$ $n=4k+3$ $n=6k+5$ $n=10k+9$ By equating the above I got this $4k+3=6k+5$ $2k=2$ $k=1$ $4k+3=10k+9$ $6k=6$ $k=1$ $10k+9=6k+5$ $4k=4$ $k=1$ However in all cases I got to $1$ which doesn't seem right. Can somebody help me to get to the answer in this situation?. I've been hinted that least common multiples applies in this problem but I don't know how to do use it here. I would appreciate if the method proposed is straightforward and easy to follow. Since there are "remainders" in this problem maybe $mod$ can appear but its not the kind of answer that I'm looking for as I have no experience with it. 
February 23rd, 2018, 05:44 AM  #2 
Senior Member Joined: May 2016 From: USA Posts: 1,084 Thanks: 446 
Your equations SHOULD BE $n = 4a + 3$ $n= 6b + 5.$ $n = 10c + 9.$ Do you see why? You have three equations in four unknowns. What is the additional information that you are IMPLICITLY given that determines a unique solution. Last edited by JeffM1; February 23rd, 2018 at 05:53 AM. 
February 23rd, 2018, 07:45 AM  #3  
Member Joined: Jun 2017 From: Lima, Peru Posts: 46 Thanks: 1 Math Focus: Calculus  Quote:
For example: $4a+3=6b+5$ $4a=6b+2$ $6b+5=10c+9$ $6b=10c+4$ $4a+3=10c+9$ $4a=10c+6$ As mentioned I'm left with a bunch of equations and nowhere to go from here. What is the part i'm missing?.  
February 23rd, 2018, 08:34 AM  #4  
Senior Member Joined: Feb 2010 Posts: 683 Thanks: 129  Quote:
$\displaystyle n+1=4a+4$ $\displaystyle n+1=6b+6$ $\displaystyle n+1=10c+10$ and divide so the equations look like this: $\displaystyle \dfrac{n+1}{4}=a+1$ $\displaystyle \dfrac{n+1}{6}=b+1$ $\displaystyle \dfrac{n+1}{10}=c+1$ We know the right side consists of whole numbers, so the left side fractions must be whole numbers. The smallest (positive) whole number that is evenly divisible by 4, 6, and 10 is the least common multiple 60. So $\displaystyle n+1=60$ and the solution is 59 muffins. You can now go back and check that: $\displaystyle 59=4 \cdot 14+3$ $\displaystyle 59=6 \cdot 9+5$ $\displaystyle 59=10 \cdot 5+9$ You may wish to google "chinese remainder theorem" for a more general way of solving problems like this.  
February 23rd, 2018, 08:59 AM  #5 
Senior Member Joined: May 2016 From: USA Posts: 1,084 Thanks: 446 
mrtwhs has finished, in very elegant fashion, the process that I was trying to get you to follow. The only thing that I would add is this. Some problems that have an infinite number of solutions in real numbers may have solutions in integer numbers, and in that case there will always be a smallest positive integer that is a solution. In this case, we had four integer unknowns and only three equations, giving an infinitude of possible real solutions, but we wanted the solution where n was the smallest possible integer solution. That gave us the crucial fourth piece of information needed. 
February 23rd, 2018, 11:06 AM  #6 
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 12,921 Thanks: 883  
February 23rd, 2018, 01:12 PM  #7  
Member Joined: Jun 2017 From: Lima, Peru Posts: 46 Thanks: 1 Math Focus: Calculus  Quote:
But I ponder, what if we cannot do that? Let's say e.g. $\displaystyle n= 3a+2$ $\displaystyle n= 7b+5$ $\displaystyle n= 8c+9$ I doubt that there can exist a value which summed to the right side can render the expression into something which can be factorized. Does that mean that such situation cannot exist? I'm trying to get the bigger picture. Can you explain this? Can the "new problem" be solved? As mentioned, the second part which links fractions to lcm and then to the numerators are easy to understand. Following your suggestion, I read the article in Wikipedia regarding the Chinese remainder theorem, but I think it cannot be applied in this situation as the condition is that divisors are pairwise coprimes and here is not the case. Maybe it could be applied if there is some modification or adjustment for this problem in particular and that is outside of my expertise. Last edited by skipjack; February 23rd, 2018 at 05:56 PM. Reason: added questions  
February 23rd, 2018, 01:31 PM  #8  
Senior Member Joined: May 2016 From: USA Posts: 1,084 Thanks: 446  Quote:
$n = 4a + 3 = 4a + 4  1 \implies n + 1 = 4a + 4 \implies \dfrac{n + 1}{4} = a + 1.$ Similarly $n = 6b + 5 = 6b + 6  1 \implies \dfrac{n + 1}{6} = b + 1.$ And $n = 10c + 9 = 10c + 10  1 \implies \dfrac{n + 1}{10} = c + 1.$ You wanted to get the right hand sides to be evenly divisible by 4, 6, and 10 respectively and to do that you need to add 1 to both sides of each equation.  
February 23rd, 2018, 01:37 PM  #9  
Member Joined: Jun 2017 From: Lima, Peru Posts: 46 Thanks: 1 Math Focus: Calculus  Quote:
 
February 23rd, 2018, 02:24 PM  #10  
Senior Member Joined: May 2016 From: USA Posts: 1,084 Thanks: 446  Quote:
When you have a system of equations with fewer equations than unknowns but restrictions on the set of numbers permitted for the solution, I am not aware of a general method for proceeding. If there is one, it is beyond my mathematical knowledge. What I do think can be drawn from this case as a general conclusion is that when a solution set must include the smallest possible positive integer, then there may be sufficient information to compensate for a missing equation.  

Tags 
common, elements, find, involving, multiples, number, problem 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to find the sum of the multiples  popoder  Algebra  5  March 6th, 2016 05:20 AM 
Group Theory Proofs, least common multiples, and group operations HELP!  msv  Abstract Algebra  1  February 19th, 2015 11:19 AM 
Find number of elements combinations covered by a given set  grigor  Applied Math  0  March 25th, 2014 11:25 PM 
Common multiples of two numbers  md9  Abstract Algebra  1  May 10th, 2013 01:26 PM 
Common elements  dajaka  Number Theory  3  October 30th, 2008 01:25 PM 