1
$\begingroup$

I would like some help on the problem above, it is a part of a school problem set but I'm having a bit of trouble with the explanation for it. The question is as follows:

Suppose x and y are relatively prime integers. What are all possible values for gcd(7x−y, x+ 2y)? Explain.

From what I understand, the only common prime factor between x and y has to be 1 and from trial and error, I find that the resulting gcd also seems to 1. Could anyone please help me show how this could be written out and explained? Thank you!

$\endgroup$
3
  • $\begingroup$ If $x=2$ and $y=5$, $\gcd(7x-y,x+2y)=\gcd(9,12)=3$. $\endgroup$
    – CY Aries
    Commented May 28, 2019 at 3:05
  • $\begingroup$ Suppose $x=4,y=13$. Then $7x-y=15, x+2y=30$ and the $\gcd$ is $15$ $\endgroup$ Commented May 28, 2019 at 3:06
  • $\begingroup$ Oh! Didn't catch that, I only tried with coprimes right next to each other. $\endgroup$
    – Shanker
    Commented May 28, 2019 at 3:10

1 Answer 1

4
$\begingroup$

Since the $\gcd$ has to be a divisor of $7x-y$ and $x+2y$, it has to divide twice the first plus the second, or $15x$. It also has to divide the $7$ times the second minus the first, or $15y$. Therefore, it has to divide $\gcd(15x,15y)=15$. Thus the four possible values are $1,3,5,15$ obtained on the pairs e.g $(2,1),(1,1),(1,2),(4,13)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .