Understanding the Remainder Problem

The question asks us to find the remainder when the number \(5^{99}\) is divided by 13. This is a typical problem in modular arithmetic, often solved by looking for patterns in the remainders of powers of the base number (5 in this case) when divided by the divisor (13).

Modular Arithmetic and Cyclicity

We need to calculate \(5^{99} \pmod{13}\). Let's compute the remainders of the first few powers of 5 when divided by 13:

• \(5^1 \pmod{13} = 5\)
• \(5^2 \pmod{13} = 25 \pmod{13}\). Since \(25 = 1 \times 13 + 12\), the remainder is 12. So, \(5^2 \equiv 12 \pmod{13}\). Note that \(12\) is also equivalent to \(-1\) in modulo 13 (since \(12 = 13 - 1\)).
• \(5^3 \pmod{13}\). We can calculate this as \(5^2 \times 5^1 \pmod{13}\). So, \(12 \times 5 \pmod{13} = 60 \pmod{13}\). Since \(60 = 4 \times 13 + 8\), the remainder is 8. So, \(5^3 \equiv 8 \pmod{13}\).
• \(5^4 \pmod{13}\). We can calculate this as \(5^3 \times 5^1 \pmod{13}\). So, \(8 \times 5 \pmod{13} = 40 \pmod{13}\). Since \(40 = 3 \times 13 + 1\), the remainder is 1. So, \(5^4 \equiv 1 \pmod{13}\).

We found that \(5^4 \equiv 1 \pmod{13}\). This means the remainders of the powers of 5 when divided by 13 will repeat in a cycle of length 4: (5, 12, 8, 1, 5, 12, 8, 1, ...). This cycle length is also known as the order of 5 modulo 13.

Simplifying the Exponent

Because the cycle length is 4, to find the remainder of \(5^{99}\), we only need to know where the exponent 99 falls within this cycle. We can find this by calculating the remainder of 99 when divided by 4.

Divide 99 by 4: \(99 \div 4 = 24\) with a remainder of \(3\). Mathematically, we write this as \(99 \equiv 3 \pmod{4}\).

Calculating the Final Remainder

Since \(99 \equiv 3 \pmod{4}\), the remainder of \(5^{99}\) divided by 13 will be the same as the remainder of \(5^3\) divided by 13.

We can express \(5^{99}\) using the division result: \(5^{99} = 5^{4 \times 24 + 3} = (5^4)^{24} \times 5^3\)

Now, let's apply the modulo 13 operation:

We know \(5^4 \equiv 1 \pmod{13}\). Substituting this in:

From our earlier calculations, we found that \(5^3 \equiv 8 \pmod{13}\).

Therefore, \(5^{99} \equiv 8 \pmod{13}\).

Conclusion

The remainder when \(5^{99}\) is divided by 13 is 8.