I'm trying to solve the discrete logarithm problem $6^x\equiv112\!\!\!\mod\!\!151.$
I am given that
$6^{72}\cdot112^{65}\equiv112^{136} \!\!\!\mod\!\!151$
I then calculate from this equation that
$6^{72}\equiv112^{71}\!\!\!\mod\!\!151\quad\mathbf{(1)}$
I use the extended euclidean algorithm to find out that
$\gcd(71,150)=1\;$ and $\;71\cdot131=1 \!\!\!\mod\!\!150\quad\mathbf{(2)}$
So now I raise both sides of $\,\mathbf{(1)}\,$ to the power of $\,131\,$ which gives us
$62^{72\cdot131}\equiv112^{71\cdot131}\!\!\!\mod\!\!150$
$\implies6^{72\cdot131}\equiv112^1\!\!\!\mod\!\!150\quad\mathbf{(2)}$
$\implies 6^{9432}\equiv112^1\!\!\!\mod\!\!150$
$\implies6^{132}\equiv112\!\!\!\mod\!\!150$
$\implies\log_6(112)\equiv132\!\!\!\mod\!\!150$
So from this, I conclude that $x = 132$.
I know this is a wrong answer since $\;6^{132}\equiv123\!\!\!\mod\!\!151$.
Can anyone help me show where I went wrong or another way of solving this without a computer?
If it helps the answer should be $\,x=47\,.$