If N is divisible by 1 , 2 , 3 , … , 1 3 , then N must also be divisible by 14 and 15.
Using this same idea, what is the smallest integer M such that the following statement is true?
If N is divisible by 1 , 2 , 3 , … , M , then N must also be divisible by M + 1 , M + 2 , M + 3 , and M + 4 .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Why does 23not work?
Log in to reply
Try N = 3 7 2 3 ! and M = 2 3 .
1, 2, 3, 4, ..., 22, 23 all divides N, but 27 (= M + 4) doesn't, since you have only
3 2 in the prime factorisation of N and 2 7 = 3 3 .
In short, there is a higher power of a prime in the {M+1, M+2, M+3, M + 4} set than in the {1, 2, 3, ..., M} set.
Log in to reply
25 is also a problem since it's also a prime power. The least common multiple of (1,...,23) is not divisible by 25.
Log in to reply
@Richard Desper – https://www.wolframalpha.com/input/?i=23!%2F27
why doesn't 27 divides....isn't it 9*3 in the prime factorization...
Log in to reply
@Gaurav Jain – that's my point, 23 is a solution for this ...
Log in to reply
@Relue Tamref – I think that both of you should've known this: If and ONLY if both a and b divides c , and ( b , c ) = 1 , then a b divides c .
And it is obvious that ( 9 , 3 ) = 3 .
@Gaurav Jain – 9 is not prime
N doesn't need to be M!, it's just the LCM of 2 thru M.
Why can't N=120, M=1 be a solution? Does it need to be M>=3?
Log in to reply
We are not given the value of N, you can't just assume that N=120.
We are looking for the least value of M such that the set {M+1,M+2,M+3,M+4} contains no prime powers.
If any of the four is a prime power, the least common multiple of {1,...,M} will not be divisible by it, in spite of being divisible by the first M numbers.
As a starting point, we look for numbers M that are followed by four non-prime numbers: the first such number is 23, but while neither 25 nor 27 is prime, both are prime powers.
The next such number is 31: but in this case while neither 33 nor 35 is a prime power, 32 is. But if we take M = 32, then we see none of 33,34,35,36 is a prime power. Thus any number divisible by the least common multiple of 1 through 32 is also divisible by 33, 34, 35, and 36.
Yup, this question will be much easier to be solved if we have a "list of primes" in hand.
Bonus: Would it still be practical to use your method if we add more numbers behind M + 4 ? In other words, is your solution still effective in solving the following setup? (We're still finding the minimum M .
If N is divisible by 1 , 2 , 3 , … , M , then N must also be divisible by M + 1 , M + 2 , M + 3 , M + 4 , M + 5 , M + 6 and M + 7 .
One has to check that M=24 also not possible because of M+1=25=5^2(also M+3=3^2).The next pair of primes is (31,37) with difference 6.So M=31&,32 are probable candidates. M=31 does not work, since M+1=2^5 creates problem. M=32 works,as M+i(i=1,2,3,4) all divide N. Hence M=32 is the answer.
Log in to reply
Checking for M=24 after dismissing M=23 because 25 and 27 are prime powers didn't feel necessary to me.
We see is N divisible by all primes <= M. So by saying M divides N we mean to say prime factors of M are a subset of N. So M+i divides N for all 1<i<4 implies there should not exist any prime between M and M+4. Also there should not exist any no. of the form a^b where a,b are natural nos otherwise when the no. is expressed in the form p^q where p is a prime and q is a natural no. q will exceed the highest power of the existing primes that divide N. So in that case the least possible value of M =32
Any positive natural number starting with 1 can be a solution to this problem .
This is how it can be proved. Take any positive number M.
Step 1 ) Let's Call X = Lowest common multiple of all the integers starting with 1 all the way up to M. { 1,2,3, .... , M}. It could be M! in some cases. Step 2) Let's Call Y = Lowest common multiple of the 4 integers following M . { M+1 , M+2, M+3 , M+4 }. Step 3) Finally N = Lowest common multiple of X and Y .
Using the above method, any positive number starting with 1 can be the value of M and there always exists another integer N for that M which can be found using the above described method that satisfies the criteria mentioned in the original question.
So this question has infinite valid solutions .
Please provide any feedback to cross-validate the above solution.
Problem Loading...
Note Loading...
Set Loading...
It is easy to see, that none of the numbers M +1, M + 2, M + 3 and M + 4 can be prime (all 4 has to be composite).
The smallest positive integer M, which is followed by 4 consecutive composite integers is 23. However:
M + 4 = 2 7 = 3 3 which is not a factor in any of the previous integers in our sequence ⇒ M = 2 3
Similarly, M≠24 since M + 3 = 27 won't necessarily divide N. ( e.g. when N = 3 7 2 3 ! )
The next smallest candidate for M is 31, as 32, 33, 34 and 35 are all composite.
In this case, M + 1 = 3 1 + 1 = 3 2 = 2 5 doesn’t divide e.g.
N = 2 2 2 3 1 ! but all the other integers from 1 to 31 divides it,
since it only has 2 4 in its prime factorisation instead of 2 5 .
Now, M = 32 works, as 33, 34, 35 and 36 are all composites and it is easy to prove, that:
if a , b , N ∈ Z ; a, b are coprimes ( gcd(a , b) = 1 )
then a ∣ N , b ∣ N ⇒ a b ∣ N
M + 1 = 3 2 + 1 = 3 3 = 3 × 1 1
M + 2 = 3 2 + 2 = 3 4 = 2 × 1 7
M + 3 = 3 2 + 3 = 3 5 = 5 × 7
M + 4 = 3 2 + 4 = 3 6 = 4 × 9
Hence, our answer should be: 3 2