What is the smallest possible value of $N$ provided $N$ denotes the smallest number of consecutive positive integers?

Question

Let $N$ be a number such that whenever you take $N$ consecutive positive integers,atleast one of them is coprime to $374$.What is the smallest possible value of $N$ ?

Options are:

A. 4

B. 5

C. 6

D. 7

ISI BMath UGA 2014

$374=2\times11\times17$

Now in order to look for a continuous streak of numbers $N$ such that atleast one of them is coprime to $374$,look for the numbers starting from $11$ as $11$ is a factor of $374$.Now $12$ is not coprime to $374$ but $13$ is.And this way we can proceed upto $17$. Then $N=7$ which is not infact the answer but my question is why $6$ the answer as $13$ is already coprime to $ 374$ and $ 6<7$.Is that the reason ? But if it were true, then

consider the numbers $5,6,7,8$ (or any $4$ consecutive numbers per se, you will see that atleast one of them is coprime to $374$ as there is a multiple of $3$ there which will be coprime to this $374$)

$5$ is coprime to $374$. So the answer could have been $4$ as well. But why $6$?

So why is option C the answer here

Answer 1

Anyway, the longest string of integers that have a factor in common with 374 is five; take two consecutive odd numbers, one divisible by 11 and the other by 17, then the three neighboring even numbers. If you are not sure about this, it is just necessary to check the numbers from $1$ to $374,$ mark the ones for which $\gcd(n,374) > 1,$ then count the longest consecutive strings. The actual factorizations do not really matter, just 2, 11, 17. I deliberately put the sequences of five consecutive up to $2 \cdot 374 = 748.$

118 = 2 * 59
119 = 7 * 17
120 = 2^3 * 3 * 5
121 = 11^2
122 = 2 * 61



252 = 2^2 * 3^2 * 7
253 = 11 * 23
254 = 2 * 127
255 = 3 * 5 * 17
256 = 2^8

=================================

492 = 2^2 * 3 * 41
493 = 17 * 29
494 = 2 * 13 * 19
495 = 3^2 * 5 * 11
496 = 2^4 * 31



626 = 2 * 313
627 = 3 * 11 * 19
628 = 2^2 * 157
629 = 17 * 37
630 = 2 * 3^2 * 5 * 7

Answer 2

Indeed the Answer is $6$, Option C.

Let's think we need $4$ consecutive integers $a_p, a_p + 1, a_p + 2, a_p + 3$. To avoid unnecessary notations let's call them $I, J, K, L$ respectively. Now two of them are divisible by $2$.

Say those are $J$ and $L$. Now what's about $I$ and $K$... It may be the case that $I$ is divisible by $11$ (it may also be true for $17$, but let's think about $11$ first, the other case can also be solved similarly). Can $K$ be divisible by $17$? If so, $0 \mod 11 \equiv I \equiv 15 \mod 17$. And thus, $K$ is divisible by $17$. But is there any existence of such integer – this might be the whole confusion. Yes, there can be one such $I$. The reason being, when we are calculating LCM of two primes, that is the first position after $0$, where both of the primes again flash $0$ as remainder. Thus intermediate all integers can be thought of the cross product of the remainders of the two primes. So this approves that such and $I$ and $K$ exist. Thus our assumption of $4$ is wrong.

Thus $5$ may be the case. What if instead of $J$ and $L$; $I$ and $K$ are divisible by $2$ and the role of $I$ and $K$ in previous case is swapped with $J$ and $L$? Then $L+1$ is divisible by $2$. Thus not $5$.

Option C manages to alley by all of these constraints. And this is the correct one.