Of course, we are working with congruence because we want to find the smallest positive \(x\) such that \(x \equiv 3^{123} \pmod 7\text{.}\) Now first write \(3^{123} = (3^3)^{41}\text{.}\) We have:
since \(27 \equiv 6 \pmod 7\text{.}\) Notice further that \(6^2 = 36\) is congruent to 1 modulo 7. Thus we can simplify further:
But \(1^{20} = 1\text{,}\) so we are done: