[SOLVED] Linear Congruence Theory

I have a question on the calculations in linear congruences if somebody could please clear up for me?

Say for example, the linear congruence: $\displaystyle 9x \equiv 21 (mod 30)$

We check that there are solutions: $\displaystyle (9,30)=1$ & $\displaystyle 3|21 \Rightarrow 3$ incongruent solutions.

Then simplify to: $\displaystyle 3x \equiv 7 (mod10)$

Then check if they are relatively prime s.t. there exists a multiplicative inverse, $\displaystyle \overline{3}$, such that $\displaystyle 3 \cdot \overline{3} \equiv 1 (mod 10)$:

$\displaystyle (3,10) = 1 \Rightarrow \exists \overline{3}$, such that $\displaystyle 3 \cdot \overline{3} \equiv 1 (mod 10)$.

The we use the Euclidean Algorithm to find $\displaystyle \overline{3}$:

$\displaystyle 10 = 3 \cdot 3 + 1$

$\displaystyle 3 = 1 \cdot 3$

$\displaystyle \overline{3} \equiv (-3) \equiv 7 (mod 10)$

$\displaystyle \Rightarrow 3 \cdot 7 \equiv 1 (mod 10)$

Then going back to the original question:

$\displaystyle 3x \equiv 7 (mod 10)$

$\displaystyle \Leftrightarrow x \equiv 7 \cdot 3x \equiv 7 \cdot 7 \equiv 9 (mod 10)$

$\displaystyle \Rightarrow x \equiv 9,19,29 (mod 30)$

This was an example in class, but I do believe the last line should say: $\displaystyle \Rightarrow x = 9,19,29 \equiv 9 (mod 30)$

My question is:

1. - How do we get the multiplicative inverse from the Euclidean Algorithm?

- Specifically, how does one get $\displaystyle \overline{3} \equiv (-3) (mod 10)$ from the Euclidean Algorithm?

- Which 3 are we looking at in the algorithm?

2. - How does the original question of $\displaystyle 3x \equiv 7 (mod 10)$ translate to $\displaystyle x \equiv 7 \cdot 3x \equiv 7 \cdot 7$?

- Why is $\displaystyle 3x$ suddenly changed to 7?

Other than that, I think I understand all of the other steps. Just couple of small hiccups in the theory I don't understand. Any help would be much appreciated. Thanks.