Question

Consider the sets A_n = {1 + k(n!) : 1 <= k <= n}, where the parameter k is assumed to be an integer. Show that any two elements of A_n are relatively prime.

Answer 1

Well, take \(a=1+k_1(n!)\) and \(b=1+k_2(n!)\) in \(A_n\). and suppose some prime \(p\) divides both \(a\) and \(b\) (there must be such a prime if they are not coprime). Then \(p|(1+k_1(n!))\) implies that \(p\) does not divide \(k_1\) or \(n!\). Likewise, \(p\) does not divide \(k_2\) either.

WLOG, assume \(k_1>k_2\). Then \(a-b=n!(k_1-k_2)\), but since \(p|a,b\), \(p|a-b\), and \(p\nmid n!\), it must be that \(p|k_1-k_2\).

Hmmm. I've gotten stuck. Give me a minute.

Answer 2

I'm sorry, but I've got to go now. If I think of something, I'll come back on later tonight and post what I've got.

Answer 3

I missed something very obvious. We have that \(p|k_1-k_2\). However, \(k_2<k_1\le n\), So \(0< k_1-k_2< n\). That means that \(p|n!\). This is a contradiction, so any two elements of the set are coprime.