A number Theory problem for beginners...

$\begin{aligned} 2^{41} & \equiv 2^{6\times 6+5} \text{ (mod 23)} \\ & \equiv 2^5(64)^6 \text{ (mod 23)} \\ & \equiv 32(69-5)^6 \text{ (mod 23)} \\ & \equiv 9 \times 5^6 \text{ (mod 23)} \\ & \equiv 9 \times 25^3 \text{ (mod 23)} \\ & \equiv 9 \times (23+2)^3 \text{ (mod 23)} \\ & \equiv 9 \times 2^3 \text{ (mod 23)} \\ & \equiv 9 \times 8 \text{ (mod 23)} \\ & \equiv 72 \text{ (mod 23)} \\ & \equiv \boxed 3 \text{ (mod 23)} \end{aligned}$

By Fermat's little theorem , $2^{22} \pmod{23} \equiv 1 \quad \implies \quad 2^{44} \pmod{23} \equiv 1 \quad \implies \quad 2^{41} \cdot 2^3 \pmod{23} \equiv 1 \quad \implies \quad 2^{41} \pmod{23} \equiv 8^{-1}.$ We're left to find the multiplicative inverse . That is, we have to find the smallest positive integer $x$ such that there exist an integer $y$ satisfying $8x + 23y = 1$ . A simple trial and error shows that $(x,y) = (3,-1)$ . Hence, $2^{41} \pmod{23} \equiv \boxed3.$