To solve this problem, we need to determine the remainder when \(5^{124}\) is divided by 124. This can be efficiently done using Euler's theorem, which states that if \(a\) and \(n\) are coprime, then:
\(a^{\phi(n)} \equiv 1 \pmod{n}\)
where \(\phi(n)\) is the Euler's totient function.
- First, let's find \(\phi(124)\). The number 124 can be factored as \(2^2 \times 31\).
- The formula for Euler's totient function is:
- \(\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)...\left(1 - \frac{1}{p_k}\right)\)
- Applying this to 124, we get:
- \(\phi(124) = 124 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{31}\right)\)
- \(= 124 \times \frac{1}{2} \times \frac{30}{31} = 62 \times \frac{30}{31} = 60\)
- According to Euler's theorem, \(5^{60} \equiv 1 \pmod{124}\).
- Now, we need to find \(5^{124} \mod 124\). Notice that:
- \(5^{124} = (5^{60})^2 \times 5^4\)
- Since \(5^{60} \equiv 1 \pmod{124}\), we have:
- \((5^{60})^2 \equiv 1^2 \equiv 1 \pmod{124}\)
- Therefore:
- \(5^{124} \equiv 5^4 \pmod{124}\)
- Calculate \(5^4\):
- \(5^4 = 625\)
- Finally, compute the remainder of 625 modulo 124:
- Divide 625 by 124 to get the remainder:
- \(625 \div 124 = 5 \text{ remainder } 5\)
Thus, the remainder is \(5\).
Therefore, the correct answer is 5.