GCD values

By the Euclidean Algorithm,

$gcd(17x+277, 7x+107)$

$=gcd(17x+277-2(7x+107), 7x+107)$

$=gcd(3x+63, 7x+107)$

$= gcd(3x+63, 7x+107-2(3x+63))$

$=gcd(3x+63, x-19)$

$=gcd(3x+63-2(x-19), x-19)$

$=gcd(x+101, x-19)$

$=gcd(120, x-19)$ .

Note that $x-19$ could have any remainder when divided by $120$ , so $gcd(120, x-19)$ could be any factor of $120$ . Note that since $120=2^3 \cdot 3 \cdot 5$ , there are $(3+1)(1+1)(1+1)=(4)(2)(2)=16$ factors of $120$ .

Thus, there are $\boxed{16}$ different possible values for $gcd(17x+277, 7x+107)$ .

Let $\gcd (17x+277,7x+107)=d$ then we have $7(17x+277)-17(7x+107)$ is divisible by $d$ . Therefore $d|120$ . Since $120=2^3 \cdot 3 \cdot 5$ then the numbers of possible values of $d$ is $(3+1)(1+1)(1+1)=16$ .

Applying the Euclidean Algorithm, we get $\gcd(17x+277,7x+107)$ $=\gcd(3x+63. 7x+107)$ $=\gcd(3x+63, x-19)$ $=\gcd(120,x-19)$ Now since $x$ ranges over the positive integers, the GCD can be any positive factor of $120$ . Since $120 = 2^3 \cdot 3 \cdot 5$ , there are $(3+1)(1+1)(1+1) = \boxed{16}$ possible values.

Just a side note, wouldn't negative GCD's work? Because then $x$ can be less than $19$ ...

It is well known that $\gcd(x,y)=\gcd(x,ax+by)$ for all $x,y,a,b\in\mathbb Z$ . So we have $\begin{array}{ll}\gcd(17x+277,7x+107)&=&\gcd(7x+107,17x+277-2(7x+107))\\&=&\gcd(7x+107,3x+63)\\&=&\gcd(3x+63,7x+107-2(3x+63))\\&=&\gcd(3x+63,x-19)\\&=&\gcd(x-19,3x+63-3(x-19))\\&=&\gcd(x-19,120)\end{array}$ Since $x$ ranges over all positive integers, $x-19$ reaches all positive divisors of $120$ ; on the other hand, since $\gcd(x,y)\mid x$ , we have $\gcd(x-19,120)\mid 120$ . So the $\gcd$ in the text assumes all and only the divisors of $120$ . But $120=2^3\cdot3\cdot5$ , and it has $(3+1)(1+1)(1+1)=16$ divisors, so the answer is $\boxed{16}$

Using Euclid's algorithm for finding GCD is quite one of the best ways to answer this problem. If you're not familiar with it, you might want to read about it here: http://www.cut-the-knot.org/blue/Euclid.shtml .

$\gcd(17x+277,7x+107)=\gcd(3x+63,7x+107) \\ \gcd(3x+63,7x+107)=\gcd(3x+63,x-19) \\ \gcd(3x+63,x-19)=\gcd(x-19,120)$

Therefore, $\gcd(17x+277,7x+107)$ is a factor of $120$ . But, $120=2^3 \cdot 3 \cdot 5$ . Therefore it has $(3+1)(1+1)(1+1)=16$ factors. Thus, the number of possible gcd's is 16 .

Using the Euclidean algorithm , if we say it simply , then the process will be like this, divide the divisor by the remainder in every division step , e.g. 17x+277 / 7x+107 In this division , the remainder will be 3x+63 . Now , according to the rule i have said, we have to keep dividing , it means the next step will be, 7x+107/3x+63 and this division will end up with a remainder x-19... We just have to keep dividing untill we get remainder 0 , But in this division , our result will end up in 120 , i mean the last remainder will be 120 and the last divisor will be (x-19) . Now, examine that the more the value of x grow up , the value of GCD will lessen . So , the greatest GCD of these two polynomial will be 120 and the least GCD will be 1 . So , the total number of different possible GCD will be all the divisor of 120 . The number of divisor of 120 is 16 . So there are 16 possible values for the two given polynomial's GCD .

We apply the Euclidean Algorithm repeatedly: $\begin{aligned} &\;\; \gcd(17x+277, \, 7x+107) \\ &= \gcd((17x+277) - 2(7x+107), \, 7x+107) \\ &= \gcd(3x+63, \, 7x+107) \\ &= \gcd(3x+63, \,(7x+107) - 2(3x+63)) \\ &= \gcd(3x+63, x-19) \\ &= \gcd((3x+63) - 3(x-19),\, x-19) \\ &= \gcd(120,\, x-19) \end{aligned}$ The greatest common divisor of two numbers has to be a factor of each number, by definition. Therefore, this value must be a factor of $120.$ For each factor $f$ of $120,$ we can set $x-19 = f$ to get $\gcd(120, \, x-19) = x-19 = f.$ Thus, the possible values of the GCD are exactly the factors of $120.$

We know that $120 = 2^3 3^1 5^1.$ So, $120$ has $4 \times 2 \times 2 = \boxed{16}$ factors.

If g = gcd(17 x +277 , 7 x + 107) then g divides both 17 x +277 and 7 x + 107
therefore g divides 14 x + 214 so g|(17 x +277)-(14 x + 214) or g|(3 x +63)-----------(1). And g|(7 x + 107)-(3 x +63) i.e g|(4 x +44)
Therefore g|(4 x +44)- (3 x +63) or g|( x -19) implying that g|(3 x -57) ---------(2) From (1) and (2) we deduce that g|120. Now 120 = 2x2x2x3x5 which has 16 divisors . So there are 16 possible values of g