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!

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

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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