My Math Forum HCF and LCM related

 Elementary Math Fractions, Percentages, Word Problems, Equations, Inequations, Factorization, Expansion

 May 9th, 2016, 11:34 PM #1 Newbie   Joined: Mar 2016 From: India Posts: 14 Thanks: 0 HCF and LCM related when a number is successively divided by 7,5 and 4 it leaves remainders of 4,2 and 3 respectively what will be the respective remainders when the smallest such number is successively divided by 8,5,6? Can you please help me out?
 May 10th, 2016, 12:29 AM #2 Senior Member   Joined: Apr 2014 From: UK Posts: 892 Thanks: 328 I get 3, 2 and 1 for the remainders. I did this by brute force. To speed up the brute force, I can see that because: 1) dividing by 5 gives remainder 2, the last digit of the number must be a 2 or 7 2) dividing by 4 gives remainder 3, the number must be odd The last digit must be a 7 Now, if we take the remaining piece of information: 3) dividing by 7 gives remainder 4 If we start with a 4 and keep adding 7's until we get a number ending in 7, that is our answer.
May 10th, 2016, 08:07 AM   #3
Senior Member

Joined: Feb 2010

Posts: 697
Thanks: 135

Quote:
 Originally Posted by Prudhvi raj k when a number is successively divided by 7,5 and 4 it leaves remainders of 4,2 and 3 respectively what will be the respective remainders when the smallest such number is successively divided by 8,5,6? Can you please help me out?
The three conditions translate to

$\displaystyle x \equiv 4$ mod 7
$\displaystyle x \equiv 2$ mod 5
$\displaystyle x \equiv 3$ mod 4

This can be solved by the Chinese Remainder Theorem.

The solution is $\displaystyle x \equiv 67$ mod 140

May 14th, 2016, 02:42 PM   #4
Math Team

Joined: Jan 2015
From: Alabama

Posts: 3,261
Thanks: 894

Quote:
 Originally Posted by Prudhvi raj k when a number is successively divided by 7,5 and 4 it leaves remainders of 4,2 and 3 respectively what will be the respective remainders when the smallest such number is successively divided by 8,5,6? Can you please help me out?
Call the "number" x. As mrtwhs said, the conditions are equivalent to
x= 4 (mod 7), x= 2 (mod 5), and x= 3 (mod 4)

x= 4 (mod 7) is the same as x= 7i+ 4 for some integer i. Taking that equation "mod 5", x= 2i+ 4= 2 (mod 5) or 2i= -2 and then i= -1= 4 (mod 5). So i= 5j+ 4 for some integer j and then x= 7(5j+ 4)+ 4= 35j+ 28+ 4= 35j+ 32. Taking that equation "mod 4", since 32 is a multiple of 4 and 35= 32+ 3, we have 3j= 3 (mod 4). So j= 1 (mod 4), j= 4k+ 1 for some integer k and x= 35j+ 32= 35(4k+ 1)+ 32= 140k+ 35+ 32= 140k+ 67.

Since we were asked to use "the smallest such number", take k= 0 and x= 67. 67 divided by 8 has remainder 3, divided by 5 has remainder 2, and divided by 6 has remainder 1.

 Tags hcf, lcm, related

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post jamjam19 Calculus 2 May 8th, 2013 04:30 PM Aurica Calculus 1 May 6th, 2009 02:37 PM Aurica Calculus 1 May 5th, 2009 04:25 PM Rorschach Calculus 2 April 1st, 2009 06:39 AM ilsj6 Calculus 1 March 22nd, 2009 05:07 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top