Could someone explain how to use CRT on the following example: $$x\equiv 7\pmod {17}$$ $$x\equiv 9\pmod {13}$$ $$x\equiv 3\pmod {12}$$
$a_1=7$, $m_1=17$, $M=2652$, $\frac{M}{m_1}=156$
$a_2=9$, $m_2=13$, $\frac{M}{m_2}=204$
$a_3=3$, $m_3=12$, $\frac{M}{m_3}=221$
First equation: $$x\equiv 7\pmod {17}\Rightarrow 156b_1\equiv 1\pmod {17}\Rightarrow 156 : 17 = 9 (3)\Rightarrow 3b_1\equiv 1\pmod {17}\Rightarrow b_1\equiv 3^{\phi(17)-1}\equiv 3^{15}\equiv ?\pmod {17}$$
$\phi(n)$ is Euler function, and $\phi(17)=16$
I am stuck here. How to find integer $(?)$
Could someone give detailed explanation?
We have
$$3^{16}\equiv 1\ (\ mod\ 17\ )$$
and
$$3^{16}=3^{15}\times 3 \equiv 1\equiv 6\times 3\ (\ mod\ 17\ )$$
So, we get $$3^{15}\equiv 6\ (\ mod\ 17\ )$$
by multiplying $3^{15}\times 3\equiv 6\times 3$ by $3^{-1}$