<s>[INST] Solve $79x \equiv 1 \pmod {90}$ This is an example in my lecture notes and I am a little confused as to how my lecturer has gone about doing this. In my notes, it says

$90 = 2 \times 3^2 \times 5$. So we can now say that solving $79x \equiv 1 \pmod {90}$ is equivalent to solving
$$79x \equiv 1 \pmod 2$$
$$7x \equiv 1 \pmod 9$$
$$4x \equiv 1 \pmod 5$$
...

How has she got the $79, 7$ and $4$ in the equivalent set of equations?
 [/INST] to solve the problem $79x \equiv 1 \pmod{90}$ you can use the Chinese Remainder Theorem to obtain the answer. For this way you need to factorize the 90 so the factors are pairwise coprimes (like the modules in the congruences your lecturer made), then you need to transform the congruences to the form:
$$ 
  \left\{
    \begin{aligned}
      x & \equiv b_1 \pmod{a_1} \\
      x & \equiv b_2 \pmod{a_2} \\
      \vdots & \\
      x & \equiv b_r \pmod{a_r}
    \end{aligned}
 \right.
$$
For this particular case we have that $90 = 2 \cdot 5 \cdot 9$ is a good factorization because the three factors are coprimes pairwise, so we need to fix the congruences to match the structure above:
The first congruence is in mod 2, so we can simplify it because $79 \equiv 1 \pmod 2$, so:
$ 79 \cdot x \equiv 1 \cdot x \pmod{2} \quad \Rightarrow \quad x \equiv 1 \pmod{2} $
Second congruence is $4x \equiv 1 \pmod{5}$. The multiplicative inverse of 4 in mod 5 is the same number: $ 4 \cdot 4 = 16 \equiv 1 \pmod{5}$ and taking product by 4 on the congruence:
$ 4 \cdot 4 \cdot x \equiv 4 \cdot 1 \pmod{5} \Rightarrow x \equiv 4 \pmod{5} $
In the last congruence $7x \equiv 1 \pmod{9}$ the inverse of 7 is again 4.
Using this inverse we obtain an equivalent congruence:
$ 4 \cdot 7 \cdot x \equiv 4 \cdot 1 \pmod{9} \Rightarrow x \equiv 4 \pmod{9} $
Now resolve the initial problem is equivalent to find x that
$$
  \left\{
    \begin{aligned}
      x & \equiv 1 \pmod 2 \\
      x & \equiv 4 \pmod 5 \\
      x & \equiv 4 \pmod 9
    \end{aligned}
  \right. 
$$
Now x can be obtained using the theorem (check http://en.wikipedia.org/wiki/Chinese_remainder_theorem for more information about this).
To find x is convenient to express in a linear combination of the $b_i$:
$ x = \sum_{1 \le i \le r} m_i b_i \pmod{n} $
In this case we must search for the coefficients:
$
 \begin{align}
   m_1 & \quad \text{coefficient for mod 2} \\
   m_2 & \quad \text{coefficient for mod 5} \\
   m_3 & \quad \text{coefficient for mod 9}  
 \end{align}
$
This coefficients are obtained using the expression $ m_i = s_i \cdot \frac{n}{a_i} $, where $s_i = \left(\frac{n}{a_i}\right)^{-1}$ in mod $a_i$.
For this problem $n = 90$ and
$
  \begin{align}
    a_1 & = 2 \\
    a_2 & = 5 \\
    a_3 & = 9 
  \end{align}
$
Inverses are:
$
  \begin{align}
    s_1 = \left(\frac{90}{2}\right)^{-1} \pmod 2 = 1 \\
    s_2 = \left(\frac{90}{5}\right)^{-1} \pmod 5 = 2 \\
    s_3 = \left(\frac{90}{10}\right)^{-1} \pmod 9 = 1 
  \end{align}
$
and the coefficients in mod 90:
$
  \begin{align}
    m_1 = s_1 \cdot \frac{90}{2} = 1 \cdot 45 = 45 \\
    m_2 = s_2 \cdot \frac{90}{5} = 2 \cdot 18 = 36 \\
    m_3 = s_3 \cdot \frac{90}{10} = 1 \cdot 10 = 10
  \end{align}
$
Value of x is obtained evaluating the linear combination:
$
  x = \sum_{1 \le i \le 3} m_i \cdot b_i
    = 45 \cdot 1 + 36 \cdot 4 + 10 \cdot 4
    = 229 \equiv 49 \pmod{90}
$
We can check that $x = 49$ satisfies the three congruences:
$
  \begin{align}
    49 & \equiv 1 \pmod 2 \\
    49 & \equiv 4 \pmod 5 \\
    49 & \equiv 4 \pmod 9
  \end{align}
$
and the initial problem:
$ 79 \cdot 49 = 3871 \equiv 1 \pmod 90 \quad (\text{because } 3871 = 90 \cdot 43 + 1)$
There is a CRT calculator in this page http://davidwees.com/chineseremaindertheorem/ 
Hope this could be useful.
</s>