0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Try: mathcelebrity.com/euclidalgo.php $\endgroup$ – Amzoti Sep 8 '14 at 15:06
  • $\begingroup$ gcd(2569.856)=1=2560-856*3 $\endgroup$ – Jack Yoon Sep 8 '14 at 15:07
  • $\begingroup$ 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$. $\endgroup$ – hardmath Sep 8 '14 at 15:08
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Oh, I knew that z would be 1 and t = -3, but when you confirm it, that would mean that: 2569 - (856*3) = 2569*1 - 865*(-3)? $\endgroup$ – CuriousGuy1 Sep 8 '14 at 15:11
  • $\begingroup$ 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). $\endgroup$ – Lucas Mann Sep 8 '14 at 15:16
  • $\begingroup$ Ah, thank you! Didn't thought I could do -(856*3) = 856*(-3) $\endgroup$ – CuriousGuy1 Sep 8 '14 at 15:21
  • $\begingroup$ @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. $\endgroup$ – hardmath Sep 8 '14 at 19:20

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.