# Finding integer multipliers for linear combination's value $= 0$, using Extended Euclidean Algorithm

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

• 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. Dec 11, 2017 at 17:49

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}$$
• But, how can $0$'s value be used,i.e. substituted for, as in EEA so to get Bezout's coefficients. Dec 12, 2017 at 22:46
• In exactly the same manner as $\gcd$ is in the usual case. It's just on emote step. Dec 12, 2017 at 22:50