Identify, using the extended euclid algorithm:


also the numbers:

$u,v \in \mathbb{Z}~~~~~~~~553u+26v=gcd(553,26)$

My calculation gives me $1$, so there isn't a real gcd, can someone approve this?

What's with $u$ and $v$ now? I can't solve this equation with any numbers $\in \mathbb{Z}$?


  • 1
    $\begingroup$ What do you mean by "real gcd"? If your calculation gives $1$, then it means that the gcd is $1$. $\endgroup$ – Wojowu Nov 11 '15 at 10:39
  • $\begingroup$ Probably that's just a term I made up. Because even of prime numbers a common divisor is 1, always. So I thought 1 is not a "real gcd". Just ignore that. $\endgroup$ – Lars Nov 11 '15 at 10:41
  • $\begingroup$ for the latter u need to use the extended euclidian algorithm see here: en.wikipedia.org/wiki/Extended_Euclidean_algorithm It is kind of using the euclidian algorithm 'backwards'. $\endgroup$ – Kees Til Nov 11 '15 at 10:52

$$553=26\times21+7$$ $$26=3\times7+5$$ $$7=1\times5+2$$ $$5=2\times2+1$$ $$2=2\times1$$ Hence $(553,26)=1$

Now $$1=5-2\times2\\=5-2\times(7-5)\\=3\times5-2\times7\\=3(26-3.7)-2.7\\=3.26-11.7\\=3.26-11(553-26.21)\\=234\times26-11\times553$$

So $u=-11$ and $v=234$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.