Debug back-substitution in extended Euclidean algorithm

Question

I'm trying to find the modular inverse of 28 mod 45 with the Euclidean algorithm but I'm getting the wrong answer. According to online calculators, the answer is $37$, but I'm getting $42$, here are my steps, where am I messing up? Thanks in advance.

Euclidean algorithm: $$45=28\left(1\right)+17$$

$$28=17\left(1\right)+11$$

$$17=11\left(1\right)+6$$

$$11=6\left(1\right)+5$$

$$6=5\left(1\right)+1$$

Then I rearrange the bottom 3 equations: $$6-5\left(1\right)=1$$ $$11-6\left(1\right)=5$$ $$17-11\left(1\right)=6$$

Substitute for $5$ in the $6-5(1)=1$ equation:

$$6-\left(11-6\left(1\right)\right)\left(1\right)=1$$ $$6-11+6=1$$ $$2(6)+11(-1)=1$$

And finally, substitute the $6$ to get my answer of $42$:

$$2\left(17-11\left(1\right)\right)+11\left(-1\right)=1$$ $$2\left(17\right)+11\left(-3\right)=1$$ $$45-3\ =\ 42$$

Answer 1

I don't know where does the last line come from. From$$2\times17+(-3)\times11=1,$$you should get that$$2\times17+(-3)\times(28-17)=1,$$or$$5\times17-3\times28=1.$$And now$$5\times(45-28)-3\times28=1,$$or$$5\times45-8\times28=1.$$So, the inverse of $28$ mod $45$ is $-8$, or $37$.

Answer 2

Work backwards as follows: \begin{align*} 1&=6-5=6-(11-6)\\ &=2\cdot6-11=2\cdot(17-11)-11\\ &=2\cdot17-3\cdot11=2\cdot17-3(28-17)\\ &=5\cdot17-3\cdot28=5\cdot(45-28)-3\cdot28\\ &=5\cdot45-8\cdot28, \end{align*} so $28(-8)=1\bmod45$.

Answer 3

Here is the standard layout of the extended Euclidean algorithm, which yields the coefficients of a Bézout's relation between $28$ and $45$. It uses the fact that each remainder $r_i$ in the algorithm satisfy a Bézout's relation $\;u_i\, 28+v_i\,45=r_i$ and that these coefficients satisfy the recurrence relation of order $2$ $$u_{i+1}=u_{i-1}-q_iu_i,\qquad v_{i+1}=v_{i-1}-q_iv_i, $$ where $q_i$ is the quotient in the $i$-th division. \begin{array}{r|rr|l} r_i&u_i&v_i&q_i \\\hline 45 & 0 & 1 \\ 28 & 1 & & 1 \\ \hline 17 & -1 & 1 & 1 \\ 11 & 2 & -1 & 1 \\ 6 & -3 & 2 & 1 \\ 5 & 5 & -3 & 1 \\ \hline 1 & \color{red}{-8} & \color {red}5 \end{array} so the relation is $$-8\cdot 28+5\cdot 45=1$$ and therefore $\;28^{-1}\bmod 45=-8\equiv 37$.

Answer 4

NOT AN ANSWER BUT FOOD FOR THOUGHT.

Alternatively (although not Euclidean Algorithm exactly):

$28$ goes into $45$, $1$ times with $17$ left over so: $1\cdot 28 \equiv -17 \pmod {45}$

$17$ goes into $45$, $2$ times with $11$ left over so: $2\cdot 1\cdot 28 \equiv 2(-17)\equiv -34 \equiv 11 \pmod {45}$

$11$ goes inot $44$, $4$ times with $1$ left over so: $4\cdot 2\cdot 1\cdot 28 \equiv 4\cdot 11 \equiv 44 \equiv -1 \pmod {45}$

So $-4\cdot 2\cdot 1\cdot 28 \equiv 1\pmod 45$

And $-4 \cdot 2 \cdot 1\equiv -8\equiv 37 \equiv 28^{-1} \pmod {45}$.

This differs from the classical Euclidean Algorithm in that the remainder always divides into the original modulus rather than the previous quotient. Has an advantage that you you have a straight product which is easier to calculate than a seriers of sums and products. Not sure why this isn't done more or why I never noticed it before.

... oh, I guess I see the bug....

Consider

$28 \equiv -17 \pmod {45}$

$3\cdot 28 \equiv -51 \equiv -6\pmod {45}$

$21 \cdot 28 \equiv -42 \equiv 3 \pmod {45}$

$(15\cdot 21)\cdot 28 \equiv 45 \equiv 0 \pmod {45}$

And $15\cdot 21 \equiv 45 \cdot 7 \equiv 0\pmod {45}$.

By dividing into the original modulus we make no assurance that the remainders are relatively prime to the original modulus.

We can make a rule that you only multiply be terms relatively prime to the modulus but that defeats the original purpose of EA to find out what is the gcd of terms.

Still as we know $45 = 5\times 3^2$ and $\gcd(28, 45)=1$ this is easy to work. Of course if you have an number lots of factors, say $360$, the the rule, don't multiply by any multiple of $2,3,5$ makes this method impractical.....

Oh, well. I thought it worked so well......