Greatest common divisor of 11n+24 and 5n+11

Question

I found out that the answer is 1 from http://www.wolframalpha.com/input/?i=gcd%2811n%2B24%2C5n%2B11%29, but I cannot find a way to prove that on my own.

I think that it is 1 because: gcd(11n+24)=1 and gcd(5n+11)=1

so gcd(11n+24,5n+11)=1

Do I assume correctly?

Answer 1

If a number divides $5n+11$ and $11n+24,$ then the number also divides both (multiples) $55n + 121$ and $55n+120.$ Since it divides both $55n + 121$ and $55n+120,$ it divides their difference, which is $1.$

Answer 2

you can get it by just applying the Euclidean Alg.:

$11n+24=2(5n+11)+(n+2)$

$5n+11=5(n+2)+1$

$n+2=(n+2)1$

clearly $1$ is the last nonzero remainder and so is the $GCD(11n+24,5n+11)$

Answer 3

Or, keep subtracting the smaller:

$\begin{align*} gcd(11n+24, 5n+11) &=gcd(11n+24-(5n+11), 5n+11)\\ &=gcd(6n+13, 5n+11)\\ &=gcd(6n+13-(5n+11), 5n+11)\\ &=gcd(n+2, 5n+11)\\ &=gcd(5n+11, n+2)\\ &=gcd(5n+11-5(n+2), n+2) \qquad\text{(combining 5 steps)}\\ &=gcd(1, n+2)\\ &= 1\\ \end{align*} $