I'm trying to solve the following function via the Extended Euclidean Algorithm, but I'm stuck at the last step where I need to sub in sub 2.
d * 7 = 1 (mod 180)
d = 1 / 7 (mod 180)
d = 7-1 (mod 180)
180 = 7 * 25 + 5
7 = 5 * 1 + 2
5 = 2 * 2 + 1
1 = 5 – 2 * 2
sub 2 = 7 – 5
1 = 5 – (7 – 5) * 2
How should I simplify this now? Any help would be appreciated.
By Euclidean algorithm (first part):
$$\begin{align*} 180 =& 7\times25 + 5\\ 7 =& 5\times1 + 2\\ 5 =& 2\times2 + 1 \end{align*}$$
Then the second part of Extended Euclidean algorithm:
$$\begin{align*} 1 =& 5 - 2\times2\\ =& 5 - (7-5\times1)\times2 &&\text{Substitute }2 = 7 - 5\times1\\ =& 7\times(-2) + 5 \times3 &&\text{Group }7\text{ and }5\text{ terms}\\ =& 7\times(-2) + (180-7\times25) \times3 &&\text{Substitute }5 = 180 - 7\times25\\ =& 180\times3 - 7\times77 &&\text{Group }180\text{ and }7\text{ terms} \end{align*}$$
Now, you should use this result to obtain $7^{-1} \pmod{180}$.