# Thread: Euclid Algorithm

1. ## 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

2. Hello, Poolmaths!

Your penultimate step . . .

$966 \;= \;84(3) + {\bf{\color{red}14}}$

3. 266 not 966 in the penultimate step. any other ideas?

4. $84=14\times6$ after the correction, giving 14 as the correct answer.

5. ## New Question

A follow on from the previous question.
find integers x and y such that 10010x + 966y = 14

having trouble working back.

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