Examkin

Question

Difficulty: MediumDivisibility Rules and Remainder Theorem

An arithmetic expression is formulated as 7+10×28677 + 10 \times 28^{67}. When this entire value is divided by 2929, what is the resulting positive remainder?

  1. A
    3
  2. B
    12
  3. C
    17
  4. 26Answer

Answer

26
By applying the property of modular arithmetic, we know that 28≡−1(mod29)28 \equiv -1 \pmod{29}. Substituting this into the expression simplifies the exponent: 2867≡(−1)67(mod29)28^{67} \equiv (-1)^{67} \pmod{29}. Because 67 is an odd integer, (−1)67=−1(-1)^{67} = -1. The expression becomes 7+10×(−1)7 + 10 \times (-1). Following the order of operations, the multiplication is resolved first to yield −10-10, and then the addition gives 7−10=−37 - 10 = -3. Finally, to find the equivalent positive remainder modulo 29, the divisor is added to the negative result: 29−3=2629 - 3 = 26.

Step-by-Step Solution

1
Express the base 2828 in terms of modulo 2929.
28≡−1(mod29)28 \equiv -1 \pmod{29}
Converting to a small negative base drastically simplifies the calculation of large exponents.
2
Evaluate the exponent term modulo 2929.
2867≡(−1)67=−1(mod29)28^{67} \equiv (-1)^{67} = -1 \pmod{29}
An odd power of −1-1 evaluates to −1-1.
3
Apply the standard order of operations (BODMAS) to the expression.
7+10×(−1)=7−10=−3(mod29)7 + 10 \times (-1) = 7 - 10 = -3 \pmod{29}
Multiplication must be performed before addition.
4
Convert the negative remainder into a valid positive remainder.
29+(−3)=2629 + (-3) = 26
Standard positive remainders must be non-negative and strictly less than the divisor, which is achieved by adding the divisor to the negative result.

Key Concept

Modular arithmetic principles, specifically managing negative bases and converting negative remainders, applied alongside the standard order of operations.

Alternative Method

One could utilize Fermat's Little Theorem, which states ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p} for prime pp. Here, 2828≡1(mod29)28^{28} \equiv 1 \pmod{29}. The power 67 can be broken down: 2867=(2828)2×2811≡12×(−1)11=−1(mod29)28^{67} = (28^{28})^2 \times 28^{11} \equiv 1^2 \times (-1)^{11} = -1 \pmod{29}. This rigorous path mathematically verifies the simpler direct substitution of −1-1.
Estimated Time:1m 0s
Rate this question

Topics

Divisibility Rules and Remainder Theorem

More questions from this topic