My Math Forum How do I find the number of elements in a problem involving least common multiples?

 Pre-Calculus Pre-Calculus Math Forum

 February 23rd, 2018, 02:41 AM #1 Member     Joined: Jun 2017 From: Lima, Peru Posts: 52 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, 06:44 AM #2 Senior Member   Joined: May 2016 From: USA Posts: 1,210 Thanks: 498 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 06:53 AM.
February 23rd, 2018, 08:45 AM   #3
Member

Joined: Jun 2017
From: Lima, Peru

Posts: 52
Thanks: 1

Math Focus: Calculus
Quote:
 Originally Posted by JeffM1 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.
Okay but how to go from there as I'm stuck with those variables and more importantly what should I find?

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, 09:34 AM   #4
Senior Member

Joined: Feb 2010

Posts: 697
Thanks: 135

Quote:
 Originally Posted by JeffM1 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.
What Jeff is trying to get you to say is that, in addition to the three equations in four unknowns, we also know that $\displaystyle n,a,b,c$ are all whole numbers. With that in mind, add one to both sides of all three equations.

$\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, 09:59 AM #5 Senior Member   Joined: May 2016 From: USA Posts: 1,210 Thanks: 498 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, 12:06 PM   #6
Math Team

Joined: Oct 2011

Posts: 13,638
Thanks: 954

Quote:
 Originally Posted by Chemist116 If we count them by multiples of ten the remainder is nine.
Plus that told you the solution ends with digit 9; n = k*10+9

February 23rd, 2018, 02:12 PM   #7
Member

Joined: Jun 2017
From: Lima, Peru

Posts: 52
Thanks: 1

Math Focus: Calculus
Quote:
 Originally Posted by mrtwhs What Jeff is trying to get you to say is that, in addition to the three equations in four unknowns, we also know that $\displaystyle n,a,b,c$ are all whole numbers. With that in mind, add one to both sides of all three equations. $\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.
Initially I was confused at why you selected $1$ to be added into those equations, then I realized that by doing this transformed the whole equation into an expression which can be factorized and then divided in the left side of the equation. I must say that "luckily" adding one renders this effect into the others as well and by that I mean that we end up with the same divisor for the three equations. That was clever! But it took me time to catch the idea.

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 06:56 PM. Reason: added questions

February 23rd, 2018, 02:31 PM   #8
Senior Member

Joined: May 2016
From: USA

Posts: 1,210
Thanks: 498

Quote:
 Originally Posted by Chemist116 How do I know that one is needed to be added into the equations?. It seems like selecting a random number, why not let's say 2 or 3 or any other? The second part which links fractions to lcm and then to the numerators are easy to understand. But again it doesn't seem very obvious why the one at the beginning. Can you explain this part please? Following your suggestion I read the article in Wikipedia regarding 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.
Do you notice that the remainders are all exactly 1 less than the divisor?

$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, 02:37 PM   #9
Member

Joined: Jun 2017
From: Lima, Peru

Posts: 52
Thanks: 1

Math Focus: Calculus
Quote:
 Originally Posted by JeffM1 Do you notice that the remainders are all exactly 1 less than the divisor? $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.
I did noticed that, it took me some time that's why I rephrased my earlier reply, however as mentioned it is not possible to do the same in all situations.

February 23rd, 2018, 03:24 PM   #10
Senior Member

Joined: May 2016
From: USA

Posts: 1,210
Thanks: 498

Quote:
 Originally Posted by Chemist116 I did noticed that, it took me some time that's why I rephrased my earlier reply, however as mentioned it is not possible to do the same in all situations.
I replied to the first version of your post and did not see your revision. Sorry about that.

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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post popoder Algebra 5 March 6th, 2016 06:20 AM msv Abstract Algebra 1 February 19th, 2015 12:19 PM grigor Applied Math 0 March 26th, 2014 12:25 AM md9 Abstract Algebra 1 May 10th, 2013 02:26 PM dajaka Number Theory 3 October 30th, 2008 02:25 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top