Let $S(a)$ be a set of the multiples of an integer $a$.

Then, here is my question.

Question : Is the following true for any $n\ge 2\in\mathbb N$ ?

Supposing that any two of $n$ integers $a_1, a_2,\cdots,a_n$ are coprime, then there exists a set of $n$ consective integers $k,k+1,\cdots,k+n-1$ such that $$k+i\in S(a_j)\ \ \text{($i=0,1,\cdots,n-1$)}.$$ Suppose that if $k+p\in S(a_r), k+q\in S(a_s)$ and $p\not=q$ , then $r\not=s$.

Example : Suppose that $a_b$ represents that $a$ is a multiple of $b$.

The $(n,a_1,a_2,a_3)=(3,3,5,7)$ case has an example $[48_3, 49_7, 50_5]$.

The $(n,a_1,a_2,a_3,a_4)=(4,2,3,5,11)$ case has an example $[8_2,9_3,10_5,11_{11}]$.

The $(n,a_1,a_2,a_3,a_4,a_5)=(5,2,3,5,7,11)$ case has an example $[119_7,120_5,121_{11},122_2,123_3]$.

Motivation : We know the $n=2$ case is true. I've been able to prove that the $n=3,4$ cases are true. The above proposition seems true for $n$ in general, but I'm facing difficulty for proving that. Can anyone help?


We will prove a slightly stronger statement.

Let $n \geq 2$ be an integer, and $a_1,\ldots,a_n$ pairwise coprime integers. Then there exists an integer $k$ such that $k + i \in S(a_{i+1})$ for all $0 \leq i \leq n-1$.

The $n=2$ case is obvious. We will use induction on $n$. Let $n > 2$, and let $a_1,\ldots,a_n$ be pairwise coprime integers. By induction hypothesis, there exist integers $k,l$ such that $k + i \in S(a_{i+1})$ for all $0 \leq i \leq n-2$ and $l + i \in S(a_{i+2})$ for all $0 \leq i \leq n-2$. Write $A = a_1 a_2 \cdots a_{n-1}$, $B = a_2 a_3 \cdots a_n$ and $C = a_2 a_3 \cdots a_{n-1}$. For any $0 \leq i \leq n-3$ we have $l + i \in S(a_{i+2})$ and $k + 1 + i \in S(a_{i+2})$, and thus $l - (k+1)$ is divisible by every $a_j$ for $2 \leq j \leq n-1$. So $l - (k-1)$ is also divisible by $C$. So we can write $l - (k-1) = xC$ for some integer $x$.

Now note that gcd$(A,B) = C$, and thus there exist integers $s,t$ such that $sA + tB = C$. We see that $l-(k+1) = xC = xsA + xtB$, which we can write as $l - xtB = (k+1) + xsA$. Now consider the consecutive integers $k + xsA, k + xsA + 1, \ldots, k + xsA + (n-1)$. For $0 \leq i \leq n-2$, $A \in S(a_{i+1})$, and thus $k + xsA + i \in S(a_{i+1})$. Finally, we note that $k + xsA + (n-1) = l - xtB + (n-2)$. As $B \in S(a_n)$, we get $k + xsA + (n-1) \in S(a_n)$. So the integers $k + xsA, k + xsA + 1, \ldots, k + xsA + (n-1)$ satisfy the conditions, which completes the proof.

  • $\begingroup$ A nice and simple answer! Thank you very much. $\endgroup$ – mathlove Nov 20 '13 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.