0

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?

Community
  • 1
sam
  • 17
  • 2
    $\gcd(11n+24)$ is not defined. You need two or more inputs, e.g. $\gcd(x,y),\gcd(x,y,z)$, for the $\gcd$ to be defined. – user236182 Oct 17 '15 at 22:33

4 Answers4

7

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

Will Jagy
  • 139,541
5

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

miniparser
  • 1,197
  • A trace of the Euclidean algorithm might be clearer than a trace of a typical extended Euclidean algorithm. –  Oct 17 '15 at 23:27
  • Agood demonstration. Will Jagy gives a classic example of a "Magician's Proof": pulling the correct information out of thin air to wow and amaze your audience. It definitely works to show that the result is true, but leaves the uninitiated scratching their heads as to where it came from. Your approach is better, IMHO, as it shows one way to figure it out yourself. – Paul Sinclair Oct 18 '15 at 01:00
1

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*} $

marty cohen
  • 107,799
0

The idea is that if $g$ is a common divisor of $a$ and $b$, then g is also a divisor of $xa + yb$ for any integers $x$ and $y$. So you choose $x$ and $y$ to make your problem simpler to solve.

With $11n+24$ and $5n+11$ choose $x$ and $y$ so as to make the $n$ go away.

So, if $g$ is a common divisor of $11n+24$ and $5n+11$, then it is also a divisor of $-5(11n+24) + 11(5n+11) = 1$. It follow that the $\gcd$ of $11n+24$ and $5n+11$ must be $1$.

Steven Alexis Gregory
  • 26,769