Extended euclidean algorithm So I am trying to figure this out.
And for one of the problem the question is x*41= 1 (mod 99)
And the answer lists
 x | 41x mod 99
 0    99
 1    41
 -2   17
 5    7
 -12  3
 29   1

And conclude x=29
How did they get this value(can someone explain)? To better put, how do you calculate this?
 A: A better table would probably be the following
$$\begin{matrix}
99 & 41\\
\hline
1 & 0 & | & 99\\
0 & 1 & | & 41\\
1 & -2 & | & 17\\
-2 & 5 & | & 7\\
5 & -12 & | & 3\\
-12 & 29 & | & 1
\end{matrix}$$
where each line
$$\begin{matrix}
a & b & | & r\\
\end{matrix}$$
means
$$
99 \cdot a + 41 \cdot b = r,
$$
and you go from two consecutive lines
$$\begin{matrix}
a_{1} & b_{1} & | & r_{1}\\
a_{2} & b_{2} & | & r_{2}\\
\end{matrix}$$
to the next by doing Euclidean division of $r_{1}$ by $r_{2}$,
$r_{1} = r_{2} q + r$, with $0 \le r < r_{2}$, and then taking as the next line
$$\begin{matrix}
a_{1} - a_{2} q & b_{1} - b_{2} q & | & r,\\
\end{matrix}$$
which satisfies indeed
$$
99 \cdot (a_{1} - a_{2} q) + 41 \cdot (b_{1} - b_{2} q)
=
99 a_{1} + 41 \ b_{1} 
-
(99 \cdot a_{2}  + 41 b_{2}) q
=
r_{1} - r_{2} q = r.
$$
So the last column yields the remainders of the Euclidean algorithm. In your table, the first column is omitted, since the required inverse is the last element in the second column. I have left it in, because the full scheme provides the extra Bézout information
$$
99 \cdot (-12) + 41 \cdot 29 = 1,
$$
from which you get
$$
41 \cdot 29 \equiv 1 \pmod{99}.
$$
A: When two numbers $e,\varphi$ are given, $e<\varphi$, $GCD(e,\varphi)=1$, and we need to find $x$, such that
$$
x\cdot e = 1 (\bmod~\varphi),\tag{1}
$$
then denote 
$$
r_0 = \varphi, \qquad v_0 = 0;
$$
$$
r_1 = e, \qquad\; v_1 = 1;
$$
then for each $n\geqslant 1$ to build values:
$$
s_n = \left\lfloor \frac{r_{n-1}}{r_n} \right\rfloor;
$$
$$
r_{n+1} = r_{n-1}-r_n s_n;
$$
$$
v_{n+1} = v_{n-1}-v_n s_n;
$$
and repeat it until $r_n=1$  $(r_{n+1}=0)$.
Last value $v_n$ (when $r_n=1$) will figure as solution of equation $(1)$.
It is comfortable to build appropriate table:
$$
\begin{array}{|c|c|r|r|}
\hline
n) & r_n & v_n & s_n & \color{gray}{check: ~~ e \cdot v_n \equiv r_n (\bmod~\varphi)} \\
\hline
0) & r_0 = \varphi = 99 & \mathbf{0} & - & - \\
1) & r_1 = e = 41 & 
\mathbf{1} & 
{\small\left\lfloor\frac{99}{41}\right\rfloor}= 2 &
\color{gray}{41\cdot 1 \equiv 41 (\bmod~99)} \\
2) & 17 & -2 & 
{\small\left\lfloor\frac{41}{17}\right\rfloor}= 2 &
\color{gray}{41\cdot (-2) = -84 \equiv 17 (\bmod~99)} \\
3) & 7  &  5 & 
{\small\left\lfloor\frac{17}{7}\right\rfloor}= 2 &
\color{gray}{41\cdot 5 = 205 \equiv 7 (\bmod~99)} \\
4) & 3 & -12 & 
{\small\left\lfloor\frac{7}{3}\right\rfloor}= 2 &
\color{gray}{41\cdot (-12) = -492 \equiv 3 (\bmod~99)} \\
5) & 1 & x=\underline{\underline{29}} &
{\small\left\lfloor\frac{3}{1}\right\rfloor}= 2 &
\color{gray}{41\cdot 29 = 1189 \equiv 1 (\bmod~99)} \\
\color{gray}{6)} & \color{gray}{0} &  & & \\
\hline
\end{array}
$$
