1
$\begingroup$

So I know the answer for this is $2$, but based on my own work, I can't get to that solution. I haven't done a gcd before where $b>a$. I thought I could just flip the numbers and use the same method but that didn't seem to work. Here's what I have so far, what I am doing wrong?

$$\begin{align} \mathrm{gcd}(1714, 1814) &= \mathrm{gcd}(1814, 1714) \\ \mathrm{gcd}(1814, 1714) &= (1714, 100)\\ &= (100, 14)\\ &= (14, 9)\\ &= (9, 5)\\ &= (5, 4)\\ &= (4, 1)\\ &= (1, 0)\\ &= 1\\ \end{align} $$

I basically tried using the Euclidian algorithm method where you keep doing long division into each number to get the remainder and continue with that process.

$\endgroup$
  • 2
    $\begingroup$ You may want to recheck the step from (100,14) to (14,9). $\endgroup$ – dxiv May 24 '17 at 4:38
  • 1
    $\begingroup$ If you know it is $2$, then the error must be when you get a number divisible by $2$. $\endgroup$ – Thomas Andrews May 24 '17 at 4:44
  • $\begingroup$ Ah ok, I see where the error is now. Thanks! $\endgroup$ – Generalkidd May 24 '17 at 4:45
  • 1
    $\begingroup$ Arithmetic. The mortal bane of all true mathematicians. $ 100 =7*14+2$ not $100=7*14 +9$. $\endgroup$ – fleablood May 24 '17 at 7:15
3
$\begingroup$

\begin{align} GCD(1814,1714)&=(1714,100)\\ &=(100,14)\\ &=(14,2)\\ \end{align} So, $2$ is the $GCD$

$\endgroup$
3
$\begingroup$

The answer is clearly wrong; both $1714$ and $1814$ are even, so $2$ divides both; the gcd is at least $2$.

In your solution, you really should write $\gcd(1814,1714)=\gcd(1714,100)=\cdots$ etc. The remainder when you divide $100$ by $14$ is $2$ ($100=7\times 14+2$) so $\gcd(100,14)=\gcd(14,2)$ etc.

$\endgroup$
2
$\begingroup$

When you reach (100,14) the next step gives (14,2) since $14 \times 7 = 98$ and $100 - 98 = 2$.

$\endgroup$
0
$\begingroup$

written as a continued fraction:

$$ \frac{ 1814 }{ 1714 } = 1 + \frac{ 100 }{ 1714 } $$ $$ \frac{ 1714 }{ 100 } = 17 + \frac{ 14 }{ 100 } $$ $$ \frac{ 100 }{ 14 } = 7 + \frac{ 2 }{ 14 } $$ $$ \frac{ 14 }{ 2 } = 7 + \frac{ 0 }{ 2 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 1 & & 17 & & 7 & & 7 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 18 }{ 17 } & & \frac{ 127 }{ 120 } & & \frac{ 907 }{ 857 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 1 \\ \frac{ 1 }{ 1 } & \mbox{digit} & 17 \\ \frac{ 18 }{ 17 } & \mbox{digit} & 7 \\ \frac{ 127 }{ 120 } & \mbox{digit} & 7 \\ \frac{ 907 }{ 857 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 907 \cdot 120 - 857 \cdot 127 = 1 $$

$$ \gcd( 1814, 1714 ) = 2 $$
$$ 1814 \cdot 120 - 1714 \cdot 127 = 2 $$

$\endgroup$

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.