![\"\"](\"/images/stars/stars-12.gif\")
You can put this solution on YOUR website!
The smallest number divisible by 2,3,4,5, or 6 with a remainder of 1 is their LCM + 1.
\n" );
document.write( "Find the LCM by Step 1: Finding the prime factors of each number:
\n" );
document.write( "2 is a prime, 3 is a prime, 4 factors to 2*2, 5 is prime, 6 factors to 2*3
\n" );
document.write( "Step 2: Look at each prime number represented. Whichever factor group has the most of that number, use that many of that prime number in a product that will be the LCM:
\n" );
document.write( "The most 2's are in the factorization of 4, so use 2*2. There are at most one 3 (in the prime factorization of 3 or 6). There are at most one 5.
\n" );
document.write( "The LCM is 2*2*3*5 = 60. LCM + 1 is 61. But 61 isn't divisible by 7.
\n" );
document.write( "Now increase by 60 (add 1 to multiples of 60) until you find one divisible by 7.
\n" );
document.write( "61 NO
\n" );
document.write( "121 NO
\n" );
document.write( "181 NO
\n" );
document.write( "241 NO
\n" );
document.write( "301 Yes. This is the answer.
\n" );
document.write( "The other way to calculate this is using the Chinese Remainder Theorem. This theorem only holds true for co-prime numbers. That is numbers that only have 1 as a common factor.
\n" );
document.write( "The list of numbers in this problem is 2,3,4,5,6, and 7. They aren't co-prime. But any odd number will have a remainder (mod) 1 when divided by 2, so we can keep that in mind but forget about 2 for the calculation.
\n" );
document.write( "We need to find some x such that x = 1 mod 2 (meaning there is a remainder of 1 when x is divided by 2.) That's any odd number.
\n" );
document.write( "x = 1 mod 3
\n" );
document.write( "x = 1 mod 4
\n" );
document.write( "x = 1 mod 5
\n" );
document.write( "x = 1 mod 6
\n" );
document.write( "x = 0 mod 7
\n" );
document.write( "Drop 6, because 6 isn't co-prime with 3. That leaves 3,4,5,and 7 as the co-prime numbers. Our answer has to be 1 mod 6, but we won't use 6 in the calculation.
\n" );
document.write( "Step 1: Multiply the co-prime numbers: 3*4*5*7 = 420 (the co-prime LCM)
\n" );
document.write( "Step 2: Divide 420 by each number. Divide that result by the number to find the remainder.
\n" );
document.write( "420/3 = 140 (call this the factor number) and 140/3 has a remainder of 2 (call this the mod number): 140=2 mod 3.
\n" );
document.write( "420/4 = 105 and 105 = 1 mod 4
\n" );
document.write( "420/5 = 84 and 84 = 4 mod 5
\n" );
document.write( "420/7 = 60 and 60 = 4 mod 7
\n" );
document.write( "Step 3: Add together (for each number): (desired remainder) * (factor number) * (mod number) =
\n" );
document.write( "1*140*2 + 1*105*1 + 1*84*4 + 0*60*4 = 280 + 105 + 336 + 0 = 721
\n" );
document.write( "Step 4: Find the remainder of Step 3 result divided by the co-prime LCM.
\n" );
document.write( "721 / 420 = 1 remainder 301.
\n" );
document.write( "This number (301, the remainder) satisfies the condition that it must be odd (remainder 1 when divided by 2.) It also satisfies the remainder of 1 when divided by 6. 301 is the answer
\n" );
document.write( "
Hope the solution helped. Sometimes you need more than a solution. Contact fcabanski@hotmail.com for online, private tutoring, or personalized problem solving (quick for groups of problems.)\r
\n" );
document.write( "\n" );
document.write( "