pairwise relatively prime pairs

Question

Let m be divisible by $1,2, ... , n$.

Show that the numbers $1+m(1+i)$ where $i = 0,1,2, ... , n$ are pairwise relatively prime.

My proof was as following let us have two different numbers $1+m(1+i)$ and $1+m(1+j)$, let d divides them. Thus $d\mid i-j$.

I feel this won't lead anywhere, any hints or solutions will be appreaciated.

Answer 1

Actually, what you did does lead to somewhere, although you missed a factor of $m$. The appropriate assumption is for some $i \neq j$, there's a $d \ge 2$ where $d \mid 1 + m(1 + i)$ and $d \mid 1 + m(1 + j)$, leading to $d \mid m(i - j)$. Note each prime factor $p$ of $d$ must divide $m$ and/or $i - j$. Since $|i - j| \le n$, if $p \mid i - j$ then $p \le n$, so because $2$ through $n$ divides $m$, you also have $p \mid m$. As such, in any case, all prime factors $p$ of $d$ must have $p \mid m$.

This means $p \mid m(1 + i)$, so $p \not\mid 1 + m(1 + i)$, and likewise $p \not\mid 1 + m(1 + j)$. Since this means $d$ doesn't divide either value, this is a contradiction of the assumption, thus showing no such $d \ge 2$ exists, i.e., all of the numbers are relatively prime.

Answer 2

Notice that for $k =2,....n$ that $k|m$ so $k\not \mid 1+m(i+1)$.

so if $d|1+m(1+i)$ then either $d=1$ or $d > n$ (assuming $d$ is a natural number and not negative).

So if $1+m(1+i)$ and $1+m(1+j)$ have a common divisor $d$ then either $d=1$ or $d > n$. As a common divisor, $d|1+m(1+i) - (1+m(1+j)=m(i-j)$. Now $\gcd(d,m)|\gcd(m,1+m(1+i))=1$ so $d|i-j$. But $|i-j| <n$. But $d > n$ or $d =1$.

If $d > n > |i-j|$ but $d|i-j$ will only be possible if $i = j$.

So either $i=j$ or the only divisors $1+m(1+i)$ and $1+m(1+j)$ have in common is $1$

Answer 3

Let $a_i=1+m(i+1)$, and suppose there is a prime $p$ such that $p\mid a_i, a_j$, that is, there are two different elements that have a common prime factor. Then,

$$p\mid a_j-a_i=m(j-i)$$

Now there are two possibilities with the same outcome:

• $p\mid m$
• $p\mid j-i$. Since $1\leq i,j\leq n+1$ we have that $|j-i|\leq n$ so $p\leq n$. Since all numbers less than $n$ divides $m$, we must have $p\mid m$.

This means that $$p\mid a_i-m(i+1)=1$$ So $p=\pm 1$. This is impossible, so $a_i,a_j$ have no common prime factor.