Question

The least remainder when \( 17^{30} \) is divided by 5, is

• A. 2
• B. 1
• C. 4
• D. 3

Hint:

For powers of numbers modulo a prime, use Euler’s theorem to reduce large exponents modulo the prime.

Answer 1

The Correct Option is C

Step 1: Use Euler's Theorem.
We are asked to find the remainder when \( 17^{30} \) is divided by 5. By Euler's theorem, if \( a \) and \( n \) are coprime (i.e., \( \gcd(a, n) = 1 \)), then: \[ a^{\phi(n)} \equiv 1 \, (\text{mod} \, n) \] where \( \phi(n) \) is Euler's totient function.

Step 2: Compute \( \phi(5) \).
Since 5 is a prime number, \( \phi(5) = 5 - 1 = 4 \). Therefore, by Euler's theorem: \[ 17^4 \equiv 1 \, (\text{mod} \, 5) \]

Step 3: Simplify the exponent.
We need to find \( 17^{30} \mod 5 \). We can break the exponent down using the fact that \( 17^4 \equiv 1 \, (\text{mod} \, 5) \). First, express 30 as: \[ 30 = 4 \times 7 + 2 \] So, \[ 17^{30} = 17^{4 \times 7 + 2} = (17^4)^7 \times 17^2 \] Since \( 17^4 \equiv 1 \, (\text{mod} \, 5) \), we have: \[ (17^4)^7 \equiv 1^7 = 1 \, (\text{mod} \, 5) \] Thus, \[ 17^{30} \equiv 17^2 \, (\text{mod} \, 5) \]

Step 4: Calculate \( 17^2 \mod 5 \).
Now, calculate \( 17^2 \mod 5 \): \[ 17 \equiv 2 \, (\text{mod} \, 5) \] So, \[ 17^2 \equiv 2^2 = 4 \, (\text{mod} \, 5) \]

Step 5: Conclusion.
Thus, \( 17^{30} \equiv 4 \, (\text{mod} \, 5) \), so the least remainder when \( 17^{30} \) is divided by 5 is \( 4 \), corresponding to option (C).