# Compute $gcd\left(1714, 1814\right)$ using Euclidean Algorithm

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.

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

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

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.

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

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