What is the least nonnegative number $a$ congruent to $3^{340}\pmod{341}$? Find the least nonnegative number $a$ congruent to $3^{340} \pmod{341}$.

What steps should I take to get to the answer?
 A: As $341=11\cdot31,$
Using Fermat's Little Theorem, $ 3^{10}\equiv1 \pmod {11}$
$\implies 3^{340}=(3^{10})^{34}\equiv1^{34}\equiv1\pmod{11}\ \ \ \ (1)$
Again applying  Fermat's Little Theorem, $3^{30}\equiv1\pmod {31}$
$\implies 3^{340}=(3^{30})^{11}\cdot 3^{10}\equiv 1\cdot3^{10}\equiv 3^{10} \pmod {31}$
Now, $3^3\equiv-4\pmod {31}\implies 3^{10}=3\cdot (3^3)^3\equiv3\cdot (-4)^3\equiv 3(-2)\equiv-6$
$\implies 3^{340}\equiv-6\ \ \ \ (2)$
Now, use CRT in $(1),(2)$ to find $x\equiv56\pmod{341}$
A: mod $\,11\!:\ 3^{340}\! \equiv (3^{10})^{34} \equiv 1^{34}\! \equiv 1\ $ by little Fermat. $ $ Similarly
mod $\,31\!:\ 3^{340}\! \equiv 3^{10} (3^{30})^{10}\! \equiv (3^5)^2 1^{10}\! \equiv (9(9\cdot 3)))^2\! \equiv (9(-4))^2\!\equiv (-5)^2\! \equiv \color{#0a0}{25}$
By CRT, $ $ mod $\,11\!:\ 1 \equiv 3^{340}\! = \color{#0a0}{25}+31k \equiv 3-2k,\,$ so $\, 3k\equiv 3,\,$ so $\,\color{#c00}{k\equiv 1}.\,$
Therefore $\, 3^{340}\! = 25\!+\!31\color{#c00}k = 25\!+\!31(\color{#c00}1\!+\!11n) = 56\! +\! 340n$.
A: Using Carmichael function, $\lambda(341)=$lcm$(\phi(11),\phi(31))=$lcm$(10,30)=10$
$\displaystyle \implies 3^{30}\equiv1\pmod{341}$ and as $340\equiv10\pmod{30}$
$\displaystyle \implies 3^{340}\equiv3^{10}\pmod{341}$
Now, $\displaystyle3^5=243\equiv-98,3^6\equiv-98\cdot3\equiv47,3^7\equiv49\cdot3=141\pmod{341}$
$\displaystyle3^8\equiv141\cdot3=423\equiv82,3^9\equiv82\cdot3=246\equiv-95\pmod{341}$
$\displaystyle\implies 3^{10}\equiv3\cdot(-9)=-285\equiv56\pmod{341}$
