For any integer $n$, show that $7n+1$ and $15n+1$ are relatively prime.

From the Euclidean Algorithm,\begin{align*} \gcd (15n+1,7n+1) & =1 \\ 15n+1 & =7n+1+8n. \end{align*}Hence,$$\gcd (15n+1,7n+1)=\gcd (7n+1,8n).$$To finish, I have to show the above expression equals one. Again by the Euclidean Algorithm,$$7n+1=q(8n)+r.$$If I keep going, I end up making it longer or most likely in an endless loop.

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Pedro
    Jul 1 at 19:35

1 Answer 1


The standard way is to first eliminate $n$. Consider that the greatest common divisor $d$ is also a divisor of $$ 15(7n+1)-7(15n+1)=8 $$ but at this point you're doomed, because for $n=1$ you have $$ 7n+1=8,\qquad 15n+1=16 $$ But, if you add the condition that $n$ is even, then $7n+1$ is odd and, since $d$ must also divide $7n+1$, we have $d=1$.

For odd $n$, the gcd can be $2$, $4$ or $8$. We've already seen the last case. For $n=3$ we have $$ 7n+1=22,\qquad 15n+1=46 $$ For $n=5$ we have $$ 7n+1=36,\qquad 15n+1=76 $$

  • $\begingroup$ So it is only valid when n is even? otherwise n as odd is false correct? $\endgroup$ Jun 29 at 23:03
  • $\begingroup$ @DrMichaelMorbius Yes: when $n$ is odd, both $7n+1$ and $15n+1$ are even. $\endgroup$
    – egreg
    Jun 29 at 23:05

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