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

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.

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

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$$
• @DrMichaelMorbius Yes: when $n$ is odd, both $7n+1$ and $15n+1$ are even. Jun 29 at 23:05