# 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.

-
Hint: what happens when you take a difference between two of the numbers? – Braindead Jan 28 '14 at 20:06
6k always disappears, but obviously the difference isn't always the same. Is there something more or less obvious that I'm missing? – Anna Jan 28 '14 at 20:11
If two numbers have a common multiple, their sum or difference (in fact, any integer linear combination) must be also divisible by the common multiple. – Braindead Jan 28 '14 at 20:18

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?

-

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.

-
The fact that all primes are of the form $6k-1$ or $6k+1$ does not imply that all numbers of these forms are prime. Consider $6\cdot 8+1=49, 6\cdot 6-1=35$ – Ross Millikan Jan 28 '14 at 21:04
Simplified and revised answer – qwr Jan 28 '14 at 21:11

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

-