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, 06:16 PM   #11
Senior Member

Joined: Feb 2010

Posts: 702
Thanks: 137

Quote:
 Originally Posted by Chemist116 $\displaystyle n= 3a+2$ $\displaystyle n= 7b+5$ $\displaystyle n= 8c+9$
$\displaystyle n=929$

$\displaystyle 929 = 3 \cdot 309 + 2$
$\displaystyle 929 = 7 \cdot 132 + 5$
$\displaystyle 929 = 8 \cdot 115 + 9$

As I said, go look up Chinese Remainder Theorem.

February 24th, 2018, 11:02 AM   #12
Senior Member

Joined: May 2016
From: USA

Posts: 1,306
Thanks: 549

Quote:
 Originally Posted by mrtwhs $\displaystyle n=929$ $\displaystyle 929 = 3 \cdot 309 + 2$ $\displaystyle 929 = 7 \cdot 132 + 5$ $\displaystyle 929 = 8 \cdot 115 + 9$ As I said, go look up Chinese Remainder Theorem.
I have never consciously worked with the Chinese Remainder Theorem so perhaps the following method of solution depends on it. Anyway, I get a different answer from mrtwhs. (My method is a brute force method because I really do not know much math.) My answer is

$n =89.$

$a = 29 \implies 3 * 29 = 87 = 89 - 2.$

$b = 12 \implies 7 * 12 = 84 = 89 - 5.$

$c = 10 \implies 8 * 10 = 80 = 89 - 9.$

Here is how I did it.

Problem find the smallest possible n subject to the following conditions:

$a,\ b,\ c,\ n \in \mathbb N+$

$n = 3a + 2.$

$n = 7b + 5.$

$n = 8c + 9.$

Solution.

We have three equations and four unknowns, but have extra information in that we are looking for the smallest integer solution for n.

It is obvious that to minimize n, we must minimize c.

$3a + 2 = n = 8c + 9 \implies 3a = 8c + 7 = 9c + 9 - (c + 2) \implies a = 3c + 3 - \dfrac{c + 2}{3}.$

For a to be an integer, c + 2 must be divisible by 3. In other words, we need an integer p such that c = 3p - 2.

$7b + 5 = n = 8c + 9 \implies b = \dfrac{8c + 4}{7} = c + \dfrac{c + 4}{7}.$

For b to be an integer, c + 4 must be divisible by 7. In other words, we need an integer q such that c = 7q - 4.

And we want the smallest such values of p and q that give an integer value to c.

$7q - 4 = 3p - 2 \implies 7q = 3p + 2 \implies q = \dfrac{3p + 2}{7}.$

We now have 1 equation in two unknowns. There may be fancy ways to solve it in positive integers, but enumeration works.

$p = 1 \implies \dfrac{3p + 2}{7} = \dfrac{5}{7} \implies q \not \in \mathbb Z.$

$p = 2 \implies \dfrac{3p + 2}{7} = \dfrac{8}{7} \implies q \not \in \mathbb Z.$

$p = 3 \implies \dfrac{3p + 2}{7} = \dfrac{11}{7} \implies q \not \in \mathbb Z.$

$p = 4 \implies \dfrac{3p + 2}{7} = \dfrac{14}{7} \implies q \in \mathbb Z.$

Now here we go.

$c = 3p - 2 = 10 \implies$

$n = 8 * 10 + 9 = 89 \implies$

$7b + 5 = 89 \implies 7b = 84 \implies b = 12.$

$3a + 2 = 89 \implies 3a = 87 \implies a = 29.$

 February 24th, 2018, 12:25 PM #13 Senior Member     Joined: Feb 2010 Posts: 702 Thanks: 137 Jeff ... I'm no expert in number theory! I just followed the algorithm in an old book I have. The algorithm gave an answer of 929 mod 168. This reduces to 89 mod 168. So in fact all possible answers are $\displaystyle 89+168t$ for any integer value of $\displaystyle t$. Some day when my brain is working, I'll try to read the background on this to see why it works. I actually tried to do it the way you did but I got tangled up so I fell back on the algorithm.
February 24th, 2018, 12:37 PM   #14
Math Team

Joined: Oct 2011

Posts: 13,986
Thanks: 995

Quote:
 Originally Posted by JeffM1 $n =89.$ Sa = 29 \implies 3 * 29 = 87 = 89 - 2.S (replaced dollar sign with S : so it doesn't turn yellow!!) $n =89.$ $a = 29 \implies 3 * 29 = 87 = 89 - 2.$
$n =89.$

$a = 29 \implies 3 * 29 = 87 = 89 - 2.$

Jeff, I keep getting these "yellow weirdoes" when you guys use
the $in order to format: not just from you, others also... Is there something I need to change from my end? Last edited by Denis; February 24th, 2018 at 12:51 PM.  February 24th, 2018, 01:03 PM #15 Senior Member Joined: May 2016 From: USA Posts: 1,306 Thanks: 549 You are asking ME about how things get parsed? February 24th, 2018, 01:12 PM #16 Member Joined: Jun 2017 From: Lima, Peru Posts: 65 Thanks: 1 Math Focus: Calculus Quote:  Originally Posted by mrtwhs$\displaystyle n=929\displaystyle 929 = 3 \cdot 309 + 2\displaystyle 929 = 7 \cdot 132 + 5\displaystyle 929 = 8 \cdot 115 + 9$As I said, go look up Chinese Remainder Theorem. First I must make a proper review of linear congruence equations, which at this moment is outside of my knowledge but in the problem I put as an example you could use it as 3, 7 and 8 are coprimes however in the "original problem" it was not the case. Quote:  Originally Posted by JeffM1 I have never consciously worked with the Chinese Remainder Theorem so perhaps the following method of solution depends on it. Anyway, I get a different answer from mrtwhs. (My method is a brute force method because I really do not know much math.) My answer is$n =89.a = 29 \implies 3 * 29 = 87 = 89 - 2.b = 12 \implies 7 * 12 = 84 = 89 - 5.c = 10 \implies 8 * 10 = 80 = 89 - 9.\$ Here is how I did it. ...
This method is rather more "heuristic" and intuitive but somebody must be careful when working with the right side of the equation so it becomes divisible by the left side. But it depends on how much practice somebody has with numerical manipulations. Thanks both!

February 24th, 2018, 02:05 PM   #17
Senior Member

Joined: May 2016
From: USA

Posts: 1,306
Thanks: 549

Quote:
 Originally Posted by Chemist116 This method is rather more "heuristic" and intuitive but somebody must be careful when working with the right side of the equation so it becomes divisible by the left side. But it depends on how much practice somebody has with numerical manipulations. Thanks both!
Actually there is nothing heuristic or intuitive up until the enumeration part. I am analyzing inside the realm of non-negative integers so it merely LOOKS weird if you are used to the realm of real numbers. But in actuality, it is pure reasoning.

Once I have reduced the problem to one equation with two integer unknowns, I admit that my method s just guess and check. But because we are looking for a minimum integer, the chances are that finding it will be relatively efficient.

 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