I am solving RSA algorithm wherein I have to find d by finding $7$ inverse modulo $480$. Please help in solving till end using extended euclidean algorithm
Using extended Euclidean Algorithm for finding inverse as follows:
$$480 = 7(68) + 4$$
$$68 = 4(17) + 0$$
Now, I am getting remainder 0 here. How shall I proceed ahead after this first step
Best Answer
By here $\,\ \overbrace{7^{-1}_{480} \equiv \dfrac{1-480(\color{#c00}{480^{-1}_7})}7}^{\rm\large inverse\ reciprocity}\equiv \dfrac{1-480(\color{#c00}2)}7\equiv -137,\ $ by $\bmod 7\!:\ \color{#c00}{\dfrac{1}{480}}\equiv \dfrac{8}4\equiv\color{#c00} 2$