Maths Olympiad Prep

Library / /24 of 30

, 2026

Number theory Difficulty 4.1 AIME Prove it Canada

For every positive integer aa, the units digits of a1a^1, a2a^2, a3a^3, a4a^4, a5a^5, \ldots will form a repeating sequence.
In each such sequence, the smallest number of consecutive units digits
that repeat consecutively and indefinitely is at most 44. This number is called the cycle
length. For example, when a=3a=3,
31=3, 32=9, 33=27, 34=81, 35=243, 36=729,3^1=3, \ 3^2=9, \ 3^3=27, \ 3^4=81, \ 3^5=243, \ 3^6=729, \ldots and the sequence of units digits is
33, 99, 77, 11, 33, 99, \dots. In this example, the consecutive
units digits that repeat are 33,
99, 77, 11, and so the cycle length is 44.

What is the units digit of 3433^{43}?
Determine the number of integers jj with $1j\$1\leq j\leq 2026forwhich for which 4^{j}+8^{j}$ is a multiple of 10.
Determine the number of integers kk with $1k\$1\leq k\leq 50forwhich for which 2^k+3^k$
has the same units digit as 82026k+92026k8^{2026k}+9^{2026k}.

Solution

Since we are given that the cycle length for the units digits of
powers of 33 is equal to 44, and 43=4×10+343=4\times10+3, the units digit of 3433^{43} is equal to the units digit of
333^3, which is 77.
Each integer multiple of 1010
has units digit 00, and so we begin
by determining the repeating sequence of units digits for powers of
44 and 88.

$4^1=4, 4^2=16, 4^3=64,
$\dots\$
$8^1=8, 8^2=64, 8^3=512, 8^4=4096,
8^5=32\,768, $\dots\$

For powers of 44, the consecutive
units digits that repeat are 44, 66, with cycle length 22.

For powers of 88, the consecutive
units digits that repeat are 88, 44, 22, 66, with cycle length 44.

We can determine the units digit of 4j+8j4^j+8^j by adding the corresponding units
digits of the individual powers of 44 and 88, and then taking the units digit of
that sum.

Thus, the units digits of 4j+8j4^j+8^j
are the units digits of 4+8=124+8=12,
6+4=106+4=10, 4+2=64+2=6, 6+6=126+6=12, which are 22, 00, 66, 22, and this sequence continues to repeat
with cycle length 44.

So, 4j+8j4^j+8^j is a multiple of 1010 (has units digit 00) once every 44 consecutive values of jj.

Since 2026=4×506+22026=4\times 506 +2, and
00 is the second digit in the
repeating sequence 2 ), (0 ), (6 ), (2 ), then the number of integers (j\text{2 ), (0 ), (6 ), (2 ), then the number of integers (j} with $1j\$1\leq j\leq 2026forwhich for which 4^j+8^jisamultipleof is a multiple of 10is is 506+1=507$.
For 2k2^k, the consecutive
units digits that repeat are 22, 44, 88, 66,
with cycle length 44.

For 3k3^k, the consecutive units
digits that repeat are 3 ), (9 ), (7 ), (1 ), with cycle length (4\text{3 ), (9 ), (7 ), (1 ), with cycle length (4}.

Similar to how we worked with 4j+8j4^j+8^j in part (b), the consecutive
units digits of 2k+3k2^k+3^k that repeat
are 5 ), (3 ), (5 ), (7 ), with cycle length (4\text{5 ), (3 ), (5 ), (7 ), with cycle length (4}.

For 8k8^k, the consecutive units
digits that repeat are 8 ), (4 ), (2 ), (6 ), with cycle length (4\text{8 ), (4 ), (2 ), (6 ), with cycle length (4}.

When kk is even, that is when k=2mk=2m for positive integers mm, 2026k=2026×2m=4052m2026k=2026\times2m=4052m.

Since 4052=4×10134052=4\times1013, then 4052m4052m is a multiple of 44, and so 2026k2026k is a multiple of 44 for all even integers kk.

Thus for all even integers kk, the
units digit of 82026k8^{2026k} is 66 (the fourth units digit in the
repeating sequence 88, 44, 22, 66).

When kk is odd, that is, when k=2m+1k=2m+1 for positive integers mm, we get the following equivalent
equations 2026k=2026×(2m+1)=4052m+2026=4052m+2024+2=4×1013m+4×506+2=4(1013m+506)+2\begin{align*} 2026k&=2026\times(2m+1)\\ &=4052m+2026\\ &=4052m+2024+2\\ &=4\times1013m+4\times506+2\\ &=4(1013m+506)+2\end{align*} So, 2026k2026k is 22 more than a multiple of 44 for all odd integers kk.

Thus for all odd integers kk, the
units digit of 82026k8^{2026k} is 44 (the second units digit in the
repeating sequence 88, 44, 22, 66).

For 9k9^k, the consecutive units
digits that repeat are 99, 11 with cycle length 22.

Thus when kk is odd, the units digit
of 9k9^k is 99, and when kk is even, the units digit is 11.

For all integers kk, 2026k2026k is an even integer, and so the
units digit of 92026k9^{2026k} is 11 for all integers kk.

Summarizing, we determined that the units digit of 82026k8^{2026k} is 44 when kk is odd, and is 66 when kk is even. Also, the units digit of 92026k9^{2026k} is 11 for all integers kk.

Therefore, 82026k+92026k8^{2026k}+9^{2026k} has
consecutive units digits 4+1=54+1=5 and
6+1=76+1=7 that repeat with cycle length
22.

Recall that 2k+3k2^k+3^k has
consecutive units digits 55, 33, 55, 77
that repeat with cycle length 44.

Thus, 2k+3k2^k+3^k and 82026k+92026k8^{2026k}+9^{2026k} have the same units
digit, 55, for all odd values of
kk. Also, 2k+3k2^k+3^k and 82026k+92026k8^{2026k}+9^{2026k} have the same units
digit, 77, for all values of kk equal to a multiple of 44.

For 1k501\leq k \leq 50, there are
2525 odd values of kk and 1212 values of kk equal to a multiple of 44 (since 50=4×12+250=4\times12+2), and so there are 25+12=3725+12=37 integers kk for which 2k+3k2^k+3^k and 82026k+92026k8^{2026k}+9^{2026k} have the same units
digit.

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

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.