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 '?'

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