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 at 3:05
  • $\begingroup$ Suppose $x=4,y=13$. Then $7x-y=15, x+2y=30$ and the $\gcd$ is $15$ $\endgroup$ – Ross Millikan May 28 at 3:06
  • $\begingroup$ Oh! Didn't catch that, I only tried with coprimes right next to each other. $\endgroup$ – Shanker May 28 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.