Maths Olympiad Prep

Library / /182 of 520

Number theory Difficulty 6.7 National olympiad Find the answer

Consider the base 27 number
n=ABCDEFGHIJKLMNOPQRSTUVWXYZ, n = ABCDEFGHIJKLMNOPQRSTUVWXYZ ,
where each letter has the value of its position in the alphabet. What remainder do you get when you divide nn by 100? (The remainder is an integer between 0 and 99, inclusive.)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

1. Express the number in base 27:
n=12725+22724+32723++2527+26 n = 1 \cdot 27^{25} + 2 \cdot 27^{24} + 3 \cdot 27^{23} + \ldots + 25 \cdot 27 + 26

2. Rewrite the sum:
n=(2725+2724++27+1)+(2724+2723++27+1)++(27+1)+1 n = (27^{25} + 27^{24} + \ldots + 27 + 1) + (27^{24} + 27^{23} + \ldots + 27 + 1) + \ldots + (27 + 1) + 1

3. Use the geometric series formula:
Each term in the sum can be expressed using the geometric series formula:
k=0m27k=27m+1126 \sum_{k=0}^{m} 27^k = \frac{27^{m+1} - 1}{26}
Applying this to each term, we get:
n=2726126+2725126+2724126++272126+27126 n = \frac{27^{26} - 1}{26} + \frac{27^{25} - 1}{26} + \frac{27^{24} - 1}{26} + \ldots + \frac{27^2 - 1}{26} + \frac{27 - 1}{26}

4. Combine the terms:
26n=2726+2725+2724++272+2726 26n = 27^{26} + 27^{25} + 27^{24} + \ldots + 27^2 + 27 - 26

5. Use the geometric series formula again:
26n=272712627 26n = \frac{27^{27} - 1}{26} - 27
Simplifying, we get:
26n=272770326 26n = \frac{27^{27} - 703}{26}
Multiplying both sides by 26:
676n=2727703 676n = 27^{27} - 703

6. Simplify using modular arithmetic:
Since λ(100)=20 \lambda(100) = 20 (Carmichael function), we have:
3813mod100 3^{81} \equiv 3 \mod 100
Therefore:
27273813mod100 27^{27} \equiv 3^{81} \equiv 3 \mod 100
Thus:
676n370337037000mod100 676n \equiv 3 - 703 \equiv 3 - 703 \equiv -700 \equiv 0 \mod 100

7. **Determine possible values of nmod100 n \mod 100 :**
Since 676n0mod100 676n \equiv 0 \mod 100 and gcd(676,100)=4 \gcd(676, 100) = 4 , we have:
676n0mod100    n0,25,50,75mod100 676n \equiv 0 \mod 100 \implies n \equiv 0, 25, 50, 75 \mod 100

8. Use modulo 4 to narrow down the options:
n(2+4+6++26)+3(1+3+5++25)mod4 n \equiv (2+4+6+\ldots+26) + 3(1+3+5+\ldots+25) \mod 4
The sum of the first series is:
2(1+2+3++13)=213142=13141mod4 2(1+2+3+\ldots+13) = 2 \cdot \frac{13 \cdot 14}{2} = 13 \cdot 14 \equiv 1 \mod 4
The sum of the second series is:
3(1+3+5++25)=3132=316931=3mod4 3(1+3+5+\ldots+25) = 3 \cdot 13^2 = 3 \cdot 169 \equiv 3 \cdot 1 = 3 \mod 4
Therefore:
n1+3=40mod4 n \equiv 1 + 3 = 4 \equiv 0 \mod 4
This eliminates 25, 50, and 75, leaving:
n0mod100 n \equiv 0 \mod 100

The final answer is 0 \boxed{0}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.