Question

The remainder obtained when \(5^{124}\) is divided by 124 is

• A. 5
• B. 0
• C. 2
• D. 1

Hint:

Use Euler's theorem: \(a^{\phi(n)} \equiv 1 \pmod{n}\) for \(\gcd(a, n) = 1\).

Answer 1

The Correct Option is A

Step 1: Understanding the Concept:
Use modular arithmetic and Euler's theorem.
Step 2: Detailed Explanation:
\(124 = 4 \times 31\)
By Euler's theorem, \(\phi(31) = 30\), so \(5^{30} \equiv 1 \pmod{31}\)
\(5^{124} = 5^{30 \times 4 + 4} \equiv 5^4 = 625 \equiv 625 - 31 \times 20 = 625 - 620 = 5 \pmod{31}\)
For mod 4: \(5 \equiv 1 \pmod{4}\), so \(5^{124} \equiv 1 \pmod{4}\)
Check 5 mod 4 = 1, consistent.
By Chinese Remainder Theorem, \(5^{124} \equiv 5 \pmod{124}\)
Step 3: Final Answer:
Remainder = 5.