Consecutively divides

If N N is divisible by 1 , 2 , 3 , , 13 1,2,3,\ldots, 13 , then N N must also be divisible by 14 and 15.

Using this same idea, what is the smallest integer M M such that the following statement is true?

If N N is divisible by 1 , 2 , 3 , , M 1,2,3,\ldots,M , then N N must also be divisible by M + 1 , M + 2 , M + 3 , M+1,M+2,M+3, and M + 4 M+4 .


The answer is 32.

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.

3 solutions

Zee Ell
Jul 6, 2017

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 = 27 = 3 3 which is not a factor in any of the previous integers in our sequence M 23 M + 4 = 27 = 3^3 \text {which is not a factor in any of the previous integers in our sequence } \Rightarrow M ≠ 23

Similarly, M≠24 since M + 3 = 27 won't necessarily divide N. ( e.g. when N = 23 ! 3 7 ) ( \text {e.g. when } N = \frac {23!}{3^7} )

The next smallest candidate for M is 31, as 32, 33, 34 and 35 are all composite.

In this case, M + 1 = 31 + 1 = 32 = 2 5 doesn’t divide e.g. \text {In this case, } M + 1 = 31 + 1 = 32 = 2^5 \text { doesn't divide e.g. }

N = 31 ! 2 2 2 but all the other integers from 1 to 31 divides it, N = \frac {31!}{2^22} \text { 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 . \text { since it only has } 2^4 \text { 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 ) \text {if } a, b, N \in \mathbb {Z} \text { ; a, b are coprimes ( gcd(a , b) = 1 ) }

then a N , b N a b N \text { then } a | N , b | N \Rightarrow ab | N

M + 1 = 32 + 1 = 33 = 3 × 11 M + 1 = 32 + 1 = 33 = 3 × 11

M + 2 = 32 + 2 = 34 = 2 × 17 M + 2 = 32 + 2 = 34 = 2 × 17

M + 3 = 32 + 3 = 35 = 5 × 7 M + 3 = 32 + 3 = 35 = 5 × 7

M + 4 = 32 + 4 = 36 = 4 × 9 M + 4 = 32 + 4 = 36 = 4 × 9

Hence, our answer should be: 32 \text {Hence, our answer should be: } \boxed {32}

Why does 23not work?

Timothy Bennett - 3 years, 10 months ago

Log in to reply

Try N = 23 ! 3 7 and M = 23. \text {Try } N = \frac {23!}{3^7} \text { and } M=23.

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 27 = 3 3 . 3^2 \text { in the prime factorisation of N and } 27 = 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.

Zee Ell - 3 years, 10 months ago

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.

Richard Desper - 3 years, 10 months ago

Log in to reply

@Richard Desper https://www.wolframalpha.com/input/?i=23!%2F27

Relue Tamref - 3 years, 10 months ago

why doesn't 27 divides....isn't it 9*3 in the prime factorization...

Gaurav Jain - 3 years, 10 months ago

Log in to reply

@Gaurav Jain that's my point, 23 is a solution for this ...

Relue Tamref - 3 years, 10 months ago

Log in to reply

@Relue Tamref I think that both of you should've known this: If and ONLY if both a a and b b divides c c , and ( b , c ) = 1 (b,c)=1 , then a b ab divides c c .

And it is obvious that ( 9 , 3 ) = 3 (9,3)=3 .

Steven Jim - 3 years, 10 months ago

@Gaurav Jain 9 is not prime

Ray Henry - 3 years, 10 months ago

N doesn't need to be M!, it's just the LCM of 2 thru M.

Jerry Barrington - 3 years, 10 months ago

Why can't N=120, M=1 be a solution? Does it need to be M>=3?

Jovan Trujillo - 3 years, 10 months ago

Log in to reply

We are not given the value of N, you can't just assume that N=120.

Pi Han Goh - 3 years, 10 months ago
Richard Desper
Jul 17, 2017

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 M+4 ? In other words, is your solution still effective in solving the following setup? (We're still finding the minimum M M .

If N N is divisible by 1 , 2 , 3 , , M 1,2,3,\ldots,M , then N N must also be divisible by M + 1 , M + 2 , M + 3 , M + 4 , M + 5 , M + 6 M+1,M+2,M+3,M+4,M+5,M+6 and M + 7 M+7 .

Pi Han Goh - 3 years, 10 months ago

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.

vinod trivedi - 3 years, 10 months ago

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.

Richard Desper - 3 years, 10 months ago
Vinayak Dutta
Jul 19, 2017

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.

Sandip Karmakar - 3 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...