Question

When \((629)^{24}\) is divided by 21, find the remainder.

• A. 1
• B. 2
• C. 5
• D. 11

Hint:

Break 21 into its coprime factors 3 and 7, work out 629 mod 3 and mod 7 separately (both come out to -1), then combine the two remainders.

Answer 1

The Correct Option is A

Step 1: Split 21 into coprime factors.
21 = 3 \(\times\) 7, and 3 and 7 share no common factor. So instead of working with mod 21 directly, we find the remainder of \(629^{24}\) modulo 3 and modulo 7 separately, then combine the two results.

Step 2: Find the remainder modulo 3.
The digit sum of 629 is \(6+2+9=17\), and 17 leaves remainder 2 when divided by 3 (since \(17 = 3 \times 5 + 2\)). So \(629 \equiv 2 \equiv -1 \pmod{3}\).
Raising to the 24th power: \((-1)^{24} = 1\). So \(629^{24} \equiv 1 \pmod{3}\).

Step 3: Find the remainder modulo 7.
\(7 \times 89 = 623\), and \(629 - 623 = 6\). So \(629 \equiv 6 \equiv -1 \pmod{7}\).
Raising to the 24th power: \((-1)^{24} = 1\). So \(629^{24} \equiv 1 \pmod{7}\).

Step 4: Combine the two results.
We now know \(629^{24}\) leaves remainder 1 when divided by 3, and remainder 1 when divided by 7. A number that is 1 more than a multiple of 3 and also 1 more than a multiple of 7 must be 1 more than a multiple of \(21 = 3 \times 7\) (their least common multiple).
So \(629^{24} \equiv 1 \pmod{21}\).

Final Answer:
The remainder when \(629^{24}\) is divided by 21 is 1, which rules out 2, 5 and 11.
\[ \boxed{1} \]