0
$\begingroup$

I have till now considered EEA as a way to find the linear combination's integer multipliers value to find $\gcd$, as follows:

Given two integers, not both zero, first find the $\gcd$, and then take the remainder at each step, and express the others in terms of that (by substituting), starting from the penultimate step in reverse. The last step has $r_{n+1}=0$.

$$ \begin{align} a = bq_1 + r_1 <--> & \ r_1 = a - bq_1 \\ b= r_1q_2 + r_2 <--> & \ r_2 = b - r_1q_2 \\ r_1 = r_2q_3 + r_3<--> & \ r_3 = r_1-r_2q_3 \\ &... \\ r_{n-2} = r_{n-1}q_{n} + r_{n}<--> & \ r_n = r_{n-2}-r_{n-1}q_{n} \\ r_{n-1} = r_{n}q_{n+1} + r_{n+1}<--> & \ \\ \end{align} $$

It is easy to calculate using EEA, the value of integer multipliers for dividend ($a$), divisor ($b$), for a given value of $\gcd = r_n$. But, to get integer multipliers is not occurring to me, for value of linear combination being $0$, as shown here in Problem $2$.

Also, want to know the logic behind finding integer multipliers for such specific value of linear combination, when the value is a multiple of $\gcd$, including $0$, as any integer divides $0$.

$\endgroup$
1
  • 1
    $\begingroup$ What is your question? Can you please give an example what you want to get? Your last sentence "...know the logic..." is unclear. Please explain what you mean. $\endgroup$ – Somos Dec 11 '17 at 17:49
2
$\begingroup$

The way you pose the question is slightly unclear for me, but if I am reading it correctly, I think you want continue the Euclidean Algorithm one step further (instead of stopping at the $\gcd$, stop at $0$) in order to arrive at a last line that looks like $$r_{n-1} = r_{n}q_{n+1} + 0 < -- > 0 = r_{n-1}-r_{n}q_{n+1} $$

$\endgroup$
2
  • $\begingroup$ But, how can $0$'s value be used,i.e. substituted for, as in EEA so to get Bezout's coefficients. $\endgroup$ – jiten Dec 12 '17 at 22:46
  • $\begingroup$ In exactly the same manner as $\gcd$ is in the usual case. It's just on emote step. $\endgroup$ – abstractnonsense Dec 12 '17 at 22:50

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.