Examkin

Question

Difficulty: MediumDivisibility Rules and Remainder Theorem

Evaluate the exact positive remainder that results from dividing 575−455^{75} - 45 by 126126.

Answer: 80

Answer

The positive remainder is 80.
The exact remainder is determined using modular arithmetic rules. By noting that 53=1255^3 = 125, we see that 125≡−1(mod126)125 \equiv -1 \pmod{126}. The expression 5755^{75} can be rewritten as (53)25(5^3)^{25}, which evaluates to (−1)25=−1(-1)^{25} = -1. Subtracting the constant 4545 yields an intermediate remainder of −46-46. Because standard division requires a non-negative remainder, we must add the divisor (126126) to −46-46, which results in 8080.

Step-by-Step Solution

1
Relate the base of the exponential term to the divisor
53=125≡−1(mod126)5^3 = 125 \equiv -1 \pmod{126}
Finding a power of the base that equals 1 or -1 modulo the divisor significantly simplifies calculations with large exponents.
2
Express the given exponent in terms of the chosen power
575=(53)255^{75} = (5^3)^{25}
This allows for direct substitution of the modular equivalent.
3
Evaluate the remainder of the exponential portion
(−1)25=−1(mod126)(-1)^{25} = -1 \pmod{126}
Substituting −1-1 for 125125 makes evaluating the 25th25^{th} power trivial.
4
Incorporate the constant term into the expression
−1−45=−46(mod126)-1 - 45 = -46 \pmod{126}
The full expression is 575−455^{75} - 45, so the constant must be subtracted from the remainder of the exponential part.
5
Convert the negative remainder into a standard positive remainder
−46+126=80-46 + 126 = 80
Remainders must be non-negative. Adding the divisor to a negative remainder provides the correct equivalent positive remainder.

Key Concept

Modular Exponentiation and Negative Remainders

Alternative Method

You could apply the binomial theorem by rewriting 5755^{75} as 12525=(126−1)25125^{25} = (126 - 1)^{25}. Expanding this yields a series of terms that are all multiples of 126126, plus a final term of (−1)25(-1)^{25}. This clearly leaves a remainder of −1-1. Subtracting 4545 gives −46-46, which is then converted to 8080 by adding 126126.
Estimated Time:1m 0s
Rate this question

Topics

Divisibility Rules and Remainder Theorem

More questions from this topic