Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
A nice and simple answer! Thank you very much. –  mathlove Nov 20 '13 at 16:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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