Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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?

share|cite|improve this answer

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.

share|cite|improve this answer
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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.