My Math Forum  

Go Back   My Math Forum > High School Math Forum > Pre-Calculus

Pre-Calculus Pre-Calculus Math Forum


Thanks Tree4Thanks
Reply
 
LinkBack Thread Tools Display Modes
February 23rd, 2018, 05:16 PM   #11
Senior Member
 
mrtwhs's Avatar
 
Joined: Feb 2010

Posts: 679
Thanks: 127

Quote:
Originally Posted by Chemist116 View Post

$\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.
mrtwhs is offline  
 
February 24th, 2018, 10:02 AM   #12
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,038
Thanks: 423

Quote:
Originally Posted by mrtwhs View Post
$\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.$
JeffM1 is offline  
February 24th, 2018, 11:25 AM   #13
Senior Member
 
mrtwhs's Avatar
 
Joined: Feb 2010

Posts: 679
Thanks: 127

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.
mrtwhs is offline  
February 24th, 2018, 11:37 AM   #14
Math Team
 
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 12,608
Thanks: 845

Quote:
Originally Posted by JeffM1 View Post

$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 11:51 AM.
Denis is online now  
February 24th, 2018, 12:03 PM   #15
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,038
Thanks: 423

You are asking ME about how things get parsed?
JeffM1 is offline  
February 24th, 2018, 12:12 PM   #16
Member
 
Chemist116's Avatar
 
Joined: Jun 2017
From: Lima, Peru

Posts: 40
Thanks: 1

Math Focus: Calculus
Quote:
Originally Posted by mrtwhs View Post
$\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 View Post
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!
Chemist116 is offline  
February 24th, 2018, 01:05 PM   #17
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,038
Thanks: 423

Quote:
Originally Posted by Chemist116 View Post
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.
JeffM1 is offline  
Reply

  My Math Forum > High School Math Forum > Pre-Calculus

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





Copyright © 2018 My Math Forum. All rights reserved.