Strategies to solve congruence problems Which strategy is best to use when solving problems of the following sort?   $$x^{29} \equiv 3\pmod {184}$$ 
 A: Hint $\ $ Let $\rm\ a,b,p,n = 3,5,23,29\ $ in the more instructive generalization below. 
Lemma $\ $ If $\rm\ p\ne 2\:$ is  prime, and $\rm\:2p = a^2b\!+\!1\:$ and $\rm\ \color{#c00}{p\!-\!1\mid 3n\!+\!1}\ $ then
$\rm\qquad\qquad\qquad\qquad\qquad x^n\! \equiv a\ \, \Rightarrow\, \ x \equiv ab^2\,\ \ (mod\ 8p)$  
Proof $\ $ $\rm\:2p = a^2b\!+\!1\:\Rightarrow\:(a,2p)=1\:\Rightarrow\:(x,2p)=1,\:$ by $\rm\:x^n\!\equiv a\:\ (mod\ 2p).\ $ Hence
$\rm mod\ 8, p\!:\ x^{p-1}\! \equiv 1\ $ by little Fermat, $ $ and $\rm\ x\:$ odd $\rm\:\Rightarrow\: mod\ 8\!:\ x^2\equiv 1,\:$ and $\rm\:2\mid p\!-\!1.$
$\rm mod\ 8p\!:\ a \equiv x^n\Rightarrow\: a^{-3}\!\equiv x^{\color{#c00}{-3n}}\!\equiv x^{\color{#c00}{1+j\,(p-1)}}\! \equiv x.\ $ Finally $\rm\ a^{-3}$ is computed as follows
$\rm 2p = a^2b\!+\!1\:\Rightarrow\:4\mid a^2b\!-\!1\:\Rightarrow\:8p\mid(a^2b)^2\!-\!1,\:$ so $\rm\:mod\ 8p\!:\ (a^2b)^2\!\equiv 1\:\Rightarrow\:a^{-3}\!\equiv ab^2.$
A: $x^{29}\equiv3\pmod {184}$
$\implies x^{29}\equiv3\pmod {23}$ as $184=23\cdot8$
Now, $\phi(23)=22\implies x^{22}\equiv1\pmod{23}\implies x^{29}\equiv x^7\cdot x^{22}\pmod{23}\equiv x^7$
$\implies x^7\equiv3\pmod{23}\implies x^{21}\equiv 3^3\pmod {23}\equiv 4$
So, $4\cdot x^{22}\equiv x^{21}\cdot1\pmod{23}\implies 4x\equiv1\pmod {23}\equiv 24$
So, $x\equiv6\pmod {23}$
Similarly, $ x^{29}\equiv3\pmod 8$ as $184=23\cdot8$
As $\lambda(8)=2, x^2\equiv1\pmod 8$
$\implies x^{29}=(x^2)^{14}\cdot x\equiv x\pmod 8\implies x\equiv3\pmod 8$
Now, apply Chinese remainder theorem, to find $x\equiv 75\pmod {184}$
