Number Theory Question, Relative Primes We have 16 random, consecutive natural numbers, like(2,3,...,17).
Prove that we can always choose one of them, which is relative prime to the other 15.
In other words, for any kind of n, we have, n,n+1,...n+15, and from that one of them is relative prime to the other 15.
I tried thinking in a way that 8 of them must be divisible with 2, so 8 of them are not good.
At least 5 of them is divisible with 3, and so on, but I can't really prove why you can always have 1.
 A: Hopefully I didn't make any mistake in counting.
Assume by contradiction that this is not true.
Then, there are $\binom{16}{2}=120$ pairs of numbers. Now, for each pair their $gcd$ is not one, therefore they are divisible by a prime $p$.
Moreover, if $p|m,k$ then $p|m-k \leq 15$ therefore $p \in \{ 2,3,5,7,11,13 \}$.
Now define $A_p:= \{ (m,k)| n \leq m,k \leq n+15 , p|m,k\}$. We know that
$$A_2 \cup A_3 \cup A_5 \cup A_7 \cup A_{11} \cup A_{13}$$
has 120 elements.
There are exactly $8$ numbers divisible by $2$, therefore there are $\binom{8}{2}=28$ elements in $A_2$.
There are at most $6$ numbers divisible by $3$, therefore there are at most $\binom{6}{2}=15$ elements in $A_3$.
There are at most $4$ numbers divisible by $5$, therefore there are at most $\binom{4}{2}=6$ elements in $A_5$.
There are at most $3$ numbers divisible by $7$, therefore there are at most $\binom{3}{2}=3$ elements in $A_7$.
There are at most $2$ numbers divisible by $11$, therefore there are at most $\binom{2}{2}=1$ elements in $A_{11}$.
There are at most $2$ numbers divisible by $13$, therefore there are at most $\binom{2}{2}=1$ elements in $A_{13}$.
Therefore there are at most $28+15+6+3+1+1=54$ elements in 
$$A_2 \cup A_3 \cup A_5 \cup A_7 \cup A_{11} \cup A_{13}$$
