Solving modular equations that gives GCD = 1 I have problems with understanding modular equations that gives GCD = 1. For example:
$$3x \equiv 59 \mod 100$$
So I'm getting $GCD(3, 100) = 1$. Now:
$1 = -33*3 + 100$
That's where the first question appears - I always guess those -33 and 1 (here) numbers...is there a way to solve them?
And the second question - the answer to that equation, at least according to the book, is:
{$-33*59 + 100k$} (k - integer) - and why is that so? Where did the 59 came from?

$$\begin{eqnarray} \text{Note} &&\ 1 &=&\ 3\, (-33)\ \ \ \, +\ \ \ \, 100\, (1)  \\
 \stackrel{\times\, 59\ }\Rightarrow && 59\, &=&\ 3\, (-33\cdot 59) + 100\, (59)\end{eqnarray}$$ 
Hence $\ 59 = 3x+100y \ $ has a particular solution $\rm\:(x,y) = (-33\cdot 59, 59).\, $ By linearity, the general solution is the sum of this and the solution of the associated homogeneous equation $\ 0 = 3x+100y,\,$ so $\, 
\frac{y}x = \frac{-3}{100},\ $ so $\ x = 100k,\ y = -3k .\,$ So the general solution is their sum  $$(-33\cdot 59,\,59)\, +\, (100k, -3k)\, =\, (-33\cdot 59+100k,\, 59-3k)$$
