# How do I solve gcd(2569,856) with Euclid's extendeded algorithm?

With this algorithm I have to modulate until r = 0

Afterwards I have to find z and t in the formula gcd(2569, 856) = 2569*z + 856*t

So here's what I've done:

gcd(2569, 856)

2569 mod 856

2569/856 = 3.0011..

2569 - (856*3) = 1

856 mod 1 = 0 (end)

1 = 2569 - 856*3 = 2569 - (?)*3

This is where I'm stuck... What do I do with 856? What should replace the '?'

• – Amzoti Sep 8 '14 at 15:06
• gcd(2569.856)=1=2560-856*3 – Jack Yoon Sep 8 '14 at 15:07
• Depending on what you mean by "solve gcd(2569,856)", you have either found what you are looking for or you need only a slight restatement to reach the conclusion. The key result is where you wrote $2569 - 3*856 = 1$. – hardmath Sep 8 '14 at 15:08

You already have the result you want: $1 = 2569 - 856 \cdot 3$.
Indeed, $\gcd(2569, 856) = 1$ (as Euclid's algorithm tells you), $z = 1$ and $t = -3$.
• We have $2569 - (856\cdot3) = 2569\cdot1 + 865\cdot(-3)$, yes. We have $2569 \cdot 1 = 2569$ (multiplying by $1$ does not change the value) and $865\cdot(-3) = -865\cdot3$ (multiplying by a negative number means inverting the result of multiplication by its absolute value). – Lucas Mann Sep 8 '14 at 15:16
• @CuriousGuy1: If we were required to use positive integer coefficients on $2569$ and $856$, we could never express a common divisor smaller than either of them. – hardmath Sep 8 '14 at 19:20