<s>[INST] 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?
 [/INST] 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}$
</s>