# 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. – Somos Dec 11 '17 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. – jiten Dec 12 '17 at 22:46
• In exactly the same manner as $\gcd$ is in the usual case. It's just on emote step. – abstractnonsense Dec 12 '17 at 22:50