Prove that $\gcd(5x+2y,2x+y)=1$ if $\gcd(x,y)=1$

Question

Let $\gcd(x,y)=1$. Prove that $5x+2y$ and $2y+x$ are always co-prime.

I’ve tried a lot of things (really a lot), but nothing has worked for me.

One of the best ideas that came to my mind (I think) is to use a proof by contradiction:

Suppose $\exists d >1$ Such that $d\mid 5x+2y$ and $d\mid 2x+y$. After some modular arithmetic I’ve found that $d\mid x$ And $d\mid y$. But what does that mean?

Answer 1

• Tool: Euclidean algorithm

$$\begin{align}\gcd(5x+2y,2x+y)= &\gcd(3x+y,2x+y)\\ =&\gcd(x,2x+y)\\ =&\gcd(x+y,x)\\ =&\gcd(x,y).\end{align}$$

So, we get

$$\gcd(5x+2y,2x+y)=\gcd(x,y)$$

This implies, if $\gcd(x,y)=1$, then $\gcd(5x+2y,2x+y)=1.$

Answer 2

You might want to use or show first that gcd $(a,b)$ = gcd$(a-b, b)$ then use this fact repeatedly will help you. You can show this fact using the definitions only.

Then gcd $ (5x+2y, 2x+y) $ = gcd $(3x+y, 2x+y)$ = gcd$(x, 2x+y)$ = gcd$(x, x+y)$. So the statement you are trying to prove is not true.

Example- Take $x = 3$ and $y = 12$.

Answer 3

If $d$ divides $5x+2y,2x+y$

$d$ must divide $5x+2y-2(2x+y)=x$

Similarly, $d$ must divide $5(2x+y)-2(5x+2y)=y$

$\implies d$ must divide $(x,y)$

Answer 4

We have $$ \pmatrix{5x+2y \\ 2x+y} = \pmatrix{5 & 2 \\ 2 & 1} \pmatrix{x \\ y} $$ The matrix has determinant $1$ and so is invertible over $\mathbb Z$. Therefore, $x$ and $y$ can be expressed as integer linear combinations of $5x+2y$ and $2x+y$ and so have the same common divisors.