The calculation of the greatest common divisor takes several steps:
$\begin{eqnarray*}
78 & = & 2 · 35 + 8 \\
35 & = & 4 · 8 + 3 \\
8 & = & 2 · 3 + 2 \\
3 & = & 1 · 2 + 1
\end{eqnarray*}$
Then we need to work our way back up:
$\begin{eqnarray*}
1 & = & 3 − 2 \\
~ & = & 3 − (8 - 2 · 3) = 3 · 3 − 8 \\
~ & = & 3 · (35 - 4 · 8) -8 = 3 · 35 − 13 · 8 \\
~ & = & 3 · 35 − 13 · (78-2 · 35) = 29 · 35 − 13 · 78
\end{eqnarray*}$
First we go through the Euclidean algorithm computation that $gcd(34, 89) = 1$
$\begin{eqnarray*}
89 & = & 2 · 34 + 21 \\
34 & = & 1 · 21 + 13 \\
21 & = & 1 · 13 + 8 \\
13 & = & 1 · 8 + 5 \\
8 & = & 1 · 5 + 3 \\
5 & = & 1 · 3 + 2 \\
3 & = & 1 · 2 + 1
\end{eqnarray*}$
Then we reverse our steps and write 1 as the desired linear combination:
$\begin{eqnarray*}
1 & = & 3 − 2 \\
~ & = & 3 - (5 - 3) = 2 · 3 - 5 \\
~ & = & 2(8-5)-5=2·8-3·5 \\
~ & = & 2·8-3(13-8)=5·8-3·13 \\
~ & = & 5(21-13)-3·13=5·21-8·13 \\
~ & = & 5·21-8·(34-21)=13·21-8·34 \\
~ & = & 13(89-2·34)-8·34=13·89-34·34
\end{eqnarray*}$
Thus s = -34, so an inverse of 34 modulo 89 is -34, which can also be written as 55.
To solve the congruence $4x \equiv 5$ (mod 9) using the inverse of 4 modulo 9,
first, find the multiplicative inverse of 4 modulo 9.
The inverse is a number 'y' such that $4*y \equiv 1$ (mod 9).
By checking the multiples of 4,
we find that $4*7 = 28$ which is 1 more than 27 (a multiple of 9).
Therefore, 7 is the inverse of 4 modulo 9.
Next, we multiply both sides of the original congruence
by this inverse: $7*(4x) \equiv 7*5$ (mod 9).
This simplifies to $28x \equiv 35$ (mod 9),
which further simplifies to $x \equiv 35$ (mod 9) since $28 \equiv 1$ (mod 9).
Reducing 35 modulo 9 gives us $35 \equiv 8$ (mod 9),
because $35 - 8 = 27$, which is a multiple of 9.
So the solution is $x \equiv 8$ (mod 9).
General Case: $x = \sum_{i=1}^n a_i M_i y_i $
The answer will be unique modulo $3 · 4 · 5 = 60$
$a_1 = 2, m_1 = 3$
$a_2 = 1, m_2 = 4$
$a_3 = 3, m_3 = 5$
$m = m_1 · m_2 · m_3 = 60$
$M_1 = 60/3 = 20,M_2 = 60/4 =15,M_3 = 60/5 = 12$
Then we need to find inverses $y_i$ of $M_i$ modulo $m_i$
$y_1 = 2,y_2 = 3,y_3 = 3$
$x = a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3 = 233 \equiv 53 \pmod{60}$
So the solutions are all integers of the form $53 + 60k$, where $k$ is an integer.
By Fermat's little theorem we know that $3^4 \equiv 1$ (mod 5);
therefore $3^{300} = (3^4)^{75} \equiv 1^{75} \equiv 1$ (mod 5),
and so $3^{302} = 3^2 \cdot 3^{300} \equiv 9 \cdot 1 = 9$ (mod 5), so $3^{302}$ mod 5 = 4.
Similarly, $3^6 \equiv 1$ (mod 7); therefore $3^{300} = (3^6)^{50} \equiv 1$ (mod 5),
and so $3^{302} = 3^2 \cdot 3^{300} \equiv 9$ (mod 7), so $3^{302}$ mod 7 = 2.
Finally, $3^{10} \equiv 1$ (mod 11); therefore $3^{300} = (3^{10})^{30} \equiv 1$ (mod 11),
and so $3^{302} = 3^2 \cdot 3^{300} \equiv 9$ (mod 11), so $3^{302}$ mod 11 = 9.