The smallest number divisible by 2,3,4,5, or 6 with a remainder of 1 is their LCM + 1.
Find the LCM by Step 1: Finding the prime factors of each number:
2 is a prime, 3 is a prime, 4 factors to 2*2, 5 is prime, 6 factors to 2*3
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:
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.
The LCM is 2*2*3*5 = 60. LCM + 1 is 61. But 61 isn't divisible by 7.
Now increase by 60 (add 1 to multiples of 60) until you find one divisible by 7.
61 NO
121 NO
181 NO
241 NO
301 Yes. This is the answer.
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.
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.
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.
x = 1 mod 3
x = 1 mod 4
x = 1 mod 5
x = 1 mod 6
x = 0 mod 7
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.
Step 1: Multiply the co-prime numbers: 3*4*5*7 = 420 (the co-prime LCM)
Step 2: Divide 420 by each number. Divide that result by the number to find the remainder.
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.
420/4 = 105 and 105 = 1 mod 4
420/5 = 84 and 84 = 4 mod 5
420/7 = 60 and 60 = 4 mod 7
Step 3: Add together (for each number): (desired remainder) * (factor number) * (mod number) =
1*140*2 + 1*105*1 + 1*84*4 + 0*60*4 = 280 + 105 + 336 + 0 = 721
Step 4: Find the remainder of Step 3 result divided by the co-prime LCM.
721 / 420 = 1 remainder 301.
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
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.)
(