Pairwise relatively prime proof (number theory)
Show that if $k \in \mathbb{Z}$, then the integers $6k-1$, $6k+1$, $6k+2$, $6k+3$, and $6k+5$ are pairwise relatively prime. I am still new and uncomfortable with proofs. Any help would be great.
$\endgroup$ 33 Answers
$\begingroup$When you're not sure what to do, look at examples. (This can be a good idea even if you are sure what to do!) In this case,
$$\begin{align} k=1&\Rightarrow 5,7,8,9,11\\ k=2&\Rightarrow 11,13,14,15,17\\ k=3&\Rightarrow 17,19,20,21,23\\ k=4&\Rightarrow 23,25,26,27,29\\ k=5&\Rightarrow 29,31,32,33,35\\ &\vdots \end{align}$$
You might notice that only the middle number in each list is even, and only the one next to it is divisible by $3$. Is it obvious that this should be the case? You might also notice that there's always a multiple of $5$, which moves around. Can you see why that happens? Finally, you might notice that the difference between the largest and smallest numbers in each list is always $6$. So how large can a number $d$ possibly be if it divides two numbers in one of the lists?
$\endgroup$ $\begingroup$A common prime factor $\,p\,$ divides their difference $\,\le 6 = (5k\!+\!5)-(5k\!-\!1),\,$ so $\,p\in\{2,3,5\}$
By Euclid $\,\gcd(6,6k\!+\!i,6k\!+\!j) = \gcd(6,i,j)$ is $1$ if $\,i$ or $\,j\in\{\pm1,5\}$ else $\{i,j\}\!=\! \{2,3\}\!\Rightarrow$ gcd $= 1$
Thus $\,p\ne 2,3,\,$ so $\,p=5.\ $ If $\,5\mid 6k+i,\,6k+j\,$ then $\,5\mid 6k+i-(6k+j) = i-j.\,$ However $\,i,j\in \{\color{#c00}{-1},1,2,3,5\}\equiv \{1,2,3,\color{#c00}4,5\}\pmod 5\,$ are all incongruent mod $5,\,$ so $\ p\ne 5.\ \ $ QED
$\endgroup$ $\begingroup$Hint: Look at these numbers as numbers $\pmod 6$. They are $-1, 1, 2, 3, 5 \pmod 6$. If you take the difference of any pair you will notice both numbers are not divisible by their difference. For example numbers in the form $1 \pmod 6$ and $5 \pmod 6$ aren't divisible by 4. Also, none of the numbers are more than 6 apart, so they can't have a common factor of more than 6. If two numbers share a factor their difference will be a factor of both numbers, and none of the numbers do, so all the numbers are relatively prime.
$\endgroup$ 2
