Key Concepts and Formulas

This problem involves finding the remainder of a large power when divided by a number, which is a classic application of modular arithmetic. Specifically, we will leverage:

1. Modular Exponentiation: The process of finding the remainder of a large power of an integer when divided by another integer.
2. Properties of Modulo:
   • If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $ac \equiv bd \pmod{m}$.
   • If $a \equiv b \pmod{m}$, then $a^k \equiv b^k \pmod{m}$ for any positive integer $k$.
3. Fermat's Little Theorem: If $p$ is a prime number, then for any integer $a$ not divisible by $p$, we have $a^{p-1} \equiv 1 \pmod{p}$.

Step-by-step Solution

Our goal is to find the remainder of $5^{99}$ when divided by 11. This can be written as finding $5^{99} \pmod{11}$.

Step 1: Simplify the base (if necessary) First, check if the base of the exponent ($5$ in this case) can be simplified modulo $11$. Since $5 < 11$, $5 \equiv 5 \pmod{11}$. No simplification is needed here.

Step 2: Find the cyclical pattern (Order of 5 modulo 11) We look for the smallest positive integer $k$ such that $5^k \equiv 1 \pmod{11}$. This is called the order of $5$ modulo $11$. According to Fermat's Little Theorem, since $11$ is a prime number and $5$ is not divisible by $11$, we know that $5^{11-1} \equiv 5^{10} \equiv 1 \pmod{11}$. This tells us that the order divides $10$, so $k$ could be $1, 2, 5,$ or $10$. Let's calculate powers of $5$ modulo $11$:

• $5^1 \equiv 5 \pmod{11}$
• $5^2 = 25 \equiv 3 \pmod{11}$ (Since $25 = 2 \times 11 + 3$)
• $5^3 \equiv 5^2 \times 5^1 \equiv 3 \times 5 = 15 \equiv 4 \pmod{11}$ (Since $15 = 1 \times 11 + 4$)
• $5^4 \equiv 5^3 \times 5^1 \equiv 4 \times 5 = 20 \equiv 9 \pmod{11}$ (Since $20 = 1 \times 11 + 9$)
• $5^5 \equiv 5^4 \times 5^1 \equiv 9 \times 5 = 45 \equiv 1 \pmod{11}$ (Since $45 = 4 \times 11 + 1$)

We found that $5^5 \equiv 1 \pmod{11}$. This is a more efficient cycle than $5^{10}$. The significance of finding $5^5 \equiv 1 \pmod{11}$ is that any power of $5^5$ will also be congruent to $1$ modulo $11$. That is, $(5^5)^m \equiv 1^m \equiv 1 \pmod{11}$.

Step 3: Reduce the exponent using the cycle Now, we want to evaluate $5^{99} \pmod{11}$. We use the fact that $5^5 \equiv 1 \pmod{11}$. Divide the exponent $99$ by the cycle length $5$: $99 = 5 \times 19 + 4$ This means we can rewrite $5^{99}$ as: $5^{99} = 5^{(5 \times 19) + 4} = (5^5)^{19} \times 5^4$ Now, substitute the modular equivalences: $5^{99} \equiv (1)^{19} \times 5^4 \pmod{11}$ $5^{99} \equiv 1 \times 5^4 \pmod{11}$ $5^{99} \equiv 5^4 \pmod{11}$

Step 4: Calculate the final remainder From Step 2, we already calculated $5^4 \equiv 9 \pmod{11}$. Therefore, $5^{99} \equiv 9 \pmod{11}$ The remainder when $5^{99}$ is divided by $11$ is $9$.

Tips and Common Mistakes to Avoid

• Don't overcomplicate: Sometimes, a smaller cycle (like $5^5 \equiv 1 \pmod{11}$) exists even if Fermat's Little Theorem suggests a larger one ($5^{10} \equiv 1 \pmod{11}$). Always test smaller powers to find the actual order for efficiency.
• Modular Arithmetic is your friend: Always perform modulo operations at intermediate steps to keep numbers small and manageable. For instance, instead of calculating $5^4 = 625$ directly and then $625 \pmod{11}$, we calculated $5^2 = 25 \equiv 3 \pmod{11}$, then $5^3 \equiv 3 \times 5 \equiv 15 \equiv 4 \pmod{11}$, etc. This reduces the chance of large calculation errors.
• Be careful with negative remainders: While $9 \equiv -2 \pmod{11}$ is true, the problem asks for the remainder, which by convention is a non-negative integer less than the divisor. So $9$ is the correct final answer.
• Understanding the binomial expansion (alternative approach): The original solution tried to use the binomial theorem. While valid, it's often more complex for this type of problem. If $5^5 = 3125 = 11 \times 284 + 1$, we can write $3125 = 11k + 1$. Then $(3125)^{19} = (11k+1)^{19}$. By the binomial theorem, this expands to $(11k)^{19} + \binom{19}{1}(11k)^{18}(1) + \dots + \binom{19}{18}(11k)(1)^{18} + (1)^{19}$. All terms except the last one will have a factor of $11$, so $(11k+1)^{19} \equiv 1^{19} \equiv 1 \pmod{11}$. This confirms $(5^5)^{19} \equiv 1 \pmod{11}$, which is the same result achieved more simply by $1^{19} \equiv 1 \pmod{11}$.

Summary and Key Takeaway

To find the remainder of a large power $a^n$ when divided by $m$:

1. Find the cycle length (order) of $a$ modulo $m$, i.e., the smallest positive integer $k$ such that $a^k \equiv 1 \pmod{m}$. Fermat's Little Theorem can help narrow down possibilities if $m$ is prime.
2. Reduce the exponent $n$ modulo $k$. Let $n = qk + r$, where $r$ is the remainder.
3. Then $a^n \equiv a^r \pmod{m}$. Calculate $a^r \pmod{m}$ to find the final remainder. Applying this method, the remainder on dividing $5^{99}$ by $11$ is $9$.