Given RSA encoding function $E: x\to x^7 \pmod{6161} $ find decoding function D So far I got:
$7\alpha \equiv 1$ mod $\phi(6161)$
$\phi(6161) = \phi(61) \times \phi(101) = 6000$
$7\alpha \equiv 1$(mod $6000)$ 
At this point we are supposed to do euclid's algorithm and somehow arrive at:
$D: x\to x^{5143}$ mod $6161$
I don't understand the euclid step
 A: If 7 is the exponent you use to encrypt, then $\alpha$ should decrypt.  What is the inverse to 7 modulo 6000?  This is where the Euclidean algorithm comes in.
A: Start the Euclidean Algorithm. So we divide $6000$ by $7$. The quotient is $857$ and the remainder is $1$, that is, 
$$6000=(7)(857)+1.$$
Now the Euclidean Algorithm is over!  We have reached a remainder of $1$. 
Thus 
$$1=(7)(-857)+6000.$$
So we have expressed $1$ as an integer linear combination of $7$ and $6000$. But we want the decoding index to be positive. So we want to replace $-857$ by a positive number congruent to $-857$ modulo $6000$.
We have $-857\equiv 6000-857\pmod{6000}$. But $6000-857=5143$, so 
$$(7)(5143)\equiv 1 \pmod{6000}.$$
We have found the modular inverse of $7$ modulo $6000$. This is the decoding index.
In general, the Euclidean Algorithm takes substantially longer, so the back substitution process is not properly illustrated by this example.
A: Hint $\rm\ mod\ m = 1\!+\!7k\!:\,\ 1\equiv -7\,\color{#C00}k\ \Rightarrow\ \dfrac{1}7\,\equiv\, \dfrac{-7k}{\ 7}\, \equiv\, -\color{#C00}k$
Therefore $\rm\ m = 6000 = 1+ 7\cdot \color{#C00}{857}\ \Rightarrow\: \dfrac{1}{7}\,\equiv\, -\color{#C00}{857}\equiv 5143\pmod{6000}$
Generally one can employ the Extended Euclidean Algorithm to compute modular inverses. The above is an optimization for the frequent special case where the modulus is $\equiv \pm1\:$ modulo the number being inverted ($= 7$ above), so the algorithm terminates in a single step.
