My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree3Thanks
  • 1 Post By agentredlum
  • 2 Post By skipjack
Reply
 
LinkBack Thread Tools Display Modes
January 5th, 2017, 09:03 PM   #1
Newbie
 
Joined: Dec 2016
From: Dhaka, Bangladesh

Posts: 9
Thanks: 0

multiple of a number

Divide 1000 into two portions in such a way that one part or one portion will be multiple of 47 and other number will be multiple of 19.

I cannot understand how this problem can be solved. The source from which I have collected this problem has given the following solution of this problem. But still now the solution seems very hard and awkward to be understood. I would be grateful if anyone of this group/forum will show me alternative ways to solve the problem stated above or make me understand the solution I have given below.

47+19=66×15=990
Rest 10+47=57 is divisible by 19.

∴47×14=658

and 19×(15+3)=342.

∴ 1000 can be divided into 658 and 342.
Nousher Ahmed is offline  
 
January 6th, 2017, 04:47 AM   #2
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

I can offer an alternative solution. We are looking for positive integers $x$ , $y$ which satisfy

$47 x + 19y = 1000 $

$ 19y = 1000 - 47x $

$ y = (\frac{1000}{19}) - (\frac{47x}{19}) $

$y = (52 + \frac{12}{19} ) - (2x + \frac{9x}{19})$

Now ... throw away $52$ and $2x$ because they are integers already
Forget $y$ for now , we need

$\frac{12 - 9x}{19}$

to be an integer , soooo....

$\frac{12 - 9x}{19} = k $

for integer k , re-arrange ,

$9x = 12 - 19k$ $ \ \ \ \ \ \ $ <--- (we will come back to this later) ***

$x = (\frac{12}{9}) -(\frac{19k}{9})$

$x =(1 + \frac{3}{9} )- (2k + \frac{k}{9})$

guess what? Throw away $1$ and $2k$ because they are integers already and forget about $x$ for now

we need

$\frac{3- k}{9}$

to be an integer , now it's easy to choose $k = 3$ but that will make $x$ negative. Choose $k = -6$ and substitute into the equation I labeled *** above

$9x = 12 - 19(-6)$

$9x = 126$

$x= 14$

next

$47(14) + 19y= 1000$

$y = \frac{1000 - 658}{19}$

$y = 18 $

Not the fastest way to get the answer but I hope it's logical

Thanks from greg1313
agentredlum is offline  
January 6th, 2017, 05:24 AM   #3
Global Moderator
 
Joined: Dec 2006

Posts: 18,232
Thanks: 1437

The given solution starts with 990 = 15(47 + 19) = 15*47 + 15*19.
Conveniently, 10 + 47 = 57 = 3*19, so 10 = -47 + 3*19.
Adding gives 1000 = 14*47 + 18*19 = 658 + 342.
Thanks from greg1313 and agentredlum
skipjack is offline  
January 6th, 2017, 10:14 AM   #4
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 1,650
Thanks: 837

Quote:
Originally Posted by agentredlum View Post
I can offer an alternative solution. We are looking for positive integers $x$ , $y$ which satisfy
it looks like what you've done is apply the Euclidean algorithm in disguise.
romsek is online now  
January 6th, 2017, 09:45 PM   #5
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

We are looking for positive integer solutions to

$47x + 19y = 1000$

The Euclidean Algorithm would find $ \ \ \ $ $gcd(47 , 19) = 1$ $ \ \ \ $ then reversing the steps would give a way to express that $gcd$ , namely $1$ , as an integer combination of $47$ and $19$. We would get a solution pair $(a , b)$ to

$47a + 19b = 1$ $ \ \ \ \ \ \ $ <-- (Obviously one of $a$ , $b$ is going to be negative)

Then we would need to multiply through by $1000$ and do considerably more work to reduce the answer to the one they want.

It is interesting to note that if you get a solution that is close to the one they want you can easily get to the solution they want. For example:

$47(-5)+ 19(65) = 1000$

is true but doesn't satisfy the requirement that both numbers be positive

but, $-5 +19 = 14$ and $65- 47 = 18$ $ \ \ \ \ \ $ <-- (note the use of $19$ and $47$)

$x = 14$ and $y = 18$

satisfy the requirement

So ... did I use the Euclidean Algorithm in disguise? I would say no.


Last edited by skipjack; January 7th, 2017 at 07:28 PM.
agentredlum is offline  
January 10th, 2017, 07:09 AM   #6
Newbie
 
Joined: Dec 2016
From: Dhaka, Bangladesh

Posts: 9
Thanks: 0

I was really unlucky since I missed this beautiful discussion due to disconnection of internet. Really this explanation was very much helpful.
Nousher Ahmed is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
multiple, number



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Multiple Django Math 7 January 24th, 2016 02:29 PM
natural number multiple of another number if its digit sum equal to that number Shen Elementary Math 2 June 5th, 2014 08:50 AM
Every natural number has multiple with digits 7 or 0 international Number Theory 24 July 11th, 2013 11:43 PM
probability of multiple events with multiple trials prwells32 Advanced Statistics 4 January 30th, 2010 03:42 PM
multiple of 11 4011 Number Theory 7 May 29th, 2007 11:29 AM





Copyright © 2017 My Math Forum. All rights reserved.