Showing $\gcd(n!i+1,n!j+1) = 1$ for $n \in \mathbb{N}$ if $i$ and $j$ are integers with $1\leq i < j \leq n$

Question

For $n$, a positive integer, and integers $i,j$ with $1\leq i < j \leq n$, I wish to show that $\gcd(n!i+1,n!j+1) = 1$.

I have shown that $\gcd(n!i+1,n!j+1) = \gcd(n!i+1, n(j-i)$), which I believe is important. I have a hunch that the proof involves the fact that $b|a \implies b\not{|}(a+1)$, and have shown this as a lemma. May I have a hint as to how to proceed?

Answer 1

$\begin{align}{\bf Hint}\ \ \ (im\!+\!1,jm\!+\!1) \,&=\, (im\!+\!1,(j\!-\!i)m)\ \ \, {\rm by}\ \ (x,y) = (x,\,y\!-\!x)\\[.3em] &=\, (im\!+\!1,\,j\!-\!i)\ \ \ \ \ \ \ \ \,{\rm by}\ \ (im\!+\!1,m) = 1\\[.3em] &=\, 1\ \ {\rm if}\ \ j\!-\!i\mid m \\ \end{align}$

Answer 2

For any prime $p \leq n$ both $n!i + 1, n!j + 1$ are $\equiv 1 \ \text{mod} \ p$. On the other hand, for any prime $p>n$, it cannot be that $p$ divides both $n!i + 1, n!j + 1$, since then it would divide their difference $n!(j-i)$, which is impossible since $j-i \leq n$.

Answer 3

Well you can subtract the smaller term for the larger.

$\gcd(n!i+1, n!j+1)= \gcd(n!i+1, (n!j+1)-(n!i+1))=\gcd(n!i + 1, n!(j-i))$

Now $n!|n!i$ so $n!i + 1$ and $n!$ are relatively prime.

So $\gcd(n!i+1, n!(j-i)) = \gcd(n!i + 1, j-i)$.

And $1 < j-i < n$ so $(j-i)|n!$ so $j-i$ is relatively prime to $n!i+1$

.....

Two lemmas:

1) $\gcd(am + 1, a) = 1$.

2) If $\gcd(a,m) = 1$ then $\gcd(a, bm) = \gcd(a,b)$.