# Euclid Algorithm

Printable View

• Apr 10th 2008, 02:47 AM
Poolmaths
Euclid Algorithm
Urgent please help

10010, 966 find the GCD

What am i doing wrong?

10010 = 966 x 10 + 350

966 = 350 x 2 + 266

350 = 266 x 1 + 84

266 = 84 x 3 + 12

84 = 12 x 7
So 12 is the answer!?!
Wrong answer though
• Apr 10th 2008, 03:07 AM
Soroban
Hello, Poolmaths!

Your penultimate step . . .

Quote:

$966 \;= \;84(3) + {\bf{\color{red}14}}$
• Apr 10th 2008, 03:10 AM
Poolmaths
266 not 966 in the penultimate step. any other ideas?
• Apr 10th 2008, 03:53 AM
xifentoozlerix
$84=14\times6$ after the correction, giving 14 as the correct answer.
• Apr 10th 2008, 05:07 AM
Poolmaths
New Question
A follow on from the previous question.
find integers x and y such that 10010x + 966y = 14

having trouble working back.
• Apr 10th 2008, 05:28 AM
xifentoozlerix
answers =
.
.
.
$(-149, 1544)$
$(-80, 829)$
$(-11, 114)$ This is the one you are looking for.
$(58, -601)$
$(127, -1316)$
.
.
.

I cheated though. To help you do this by hand, try this link.