What is the remainder when $5342^{82}$ is divided by 11?
I. solution: In problem 473 (see p. 81), we made an observation that if $b=c k+d$, then $b^{n}=c K+d^{n}$, where $b, c, k, d, K$ are integers and $n$ is a positive integer. This can also be stated as the remainder of the division $b^{n}: c$ being the same as the remainder of the division $d^{n}: c$, where $d=b-c k$. Applying this with $b=5342$ and $c=11$, we can take $d$ as the remainder of the division $5342 : 11$, which is 7, and thus the desired remainder can be obtained as the remainder of the division $7^{82}: 11$, which is 1.

Similarly to the base, we can also transition to examining smaller numbers in the exponent. We can apply Fermat's theorem to our problem ${ }^{2}$ since 11 is a prime number, and 7 and 11 are relatively prime, so $7^{11-1}-1=7^{10}-1$ is divisible by 11: $7^{10}-1=11 k$. Furthermore, $7^{80}-1=\left(7^{10}\right)^{8}-1$ is divisible by $7^{10}-1$ and thus by 11 as well, so $7^{80}-1=11 K$, or $7^{80}=11 K_{1}+1$. Now $7^{82}=7^{2} \cdot 7^{80}=49\left(11 K_{1}+1\right)=11 K_{2}+49$ and this shows that the desired remainder is the same as the remainder of the division $49: 11$, which is 5.

Gazsi Lajos (Kaposvár, Táncsics M. g. II. o. t.)

II. solution: After transitioning from examining $5342^{82}$ to $7^{82}$, we can proceed from power to power in determining the remainder. It is not necessary to actually calculate each power because if we have already calculated the remainder of a power, the remainder of the next power is the same as the remainder of the product of the already obtained remainder and 7. Indeed, if

$$
7^{n}=11 K_{n}+r_{n}
$$

then

$$
7^{n+1}=7 \cdot 7^{n}=7\left(11 K_{n}+r_{n}\right)=11 \cdot 7 \cdot K_{n}+7 r_{n}
$$

Since there can be at most 11 different remainders when dividing by 11, by the 12th step at the latest, a remainder must appear twice, and from then on the remainders repeat periodically, which also simplifies the calculation.

The calculation proceeds as follows: when dividing by 11,

|  |  |  |  |  |
| :--- | :---: | :--- | :--- | :--- |
| $7^{1}$ | remainder | 7, |  |  |
| $7^{2}=49$ | " | 5, |  |  |
| $7^{3}$ | " | $=7 \cdot 5=35$, | remainder $=2$, |  |
| $7^{4}$ | " | $=7 \cdot 2=14, \quad "$ | $=3$, |  |
| $7^{5}$ | " | $=7 \cdot 3=21, \quad "$ | $=10$, |  |
| $7^{6}$ | " | $=7 \cdot 10=70, \quad "$ | $=4$, |  |
| $7^{7}$ | " | $=7 \cdot 4=28, \quad "$ | $=6$, |  |
| $7^{8}$ | " | $=7 \cdot 6=42, \quad "$ | $=9$, |  |
| $7^{9}$ | " | $=7 \cdot 9=63, \quad "$ | $=8$, |  |
| $7^{10}$ | " | $=7 \cdot 8=56$, | $=$ | $=1$, |
| $7^{11}$ | " | $=7 \cdot 1=7$. |  |  |

From here, the remainders $7,5,2,3,10,4,6,9,8,1$ repeat periodically. The 20th, 30th, ..., 80th powers will have a remainder of 1 again, the 81st will have a remainder of 7, and the 82nd power of 7 will give a remainder of 5 when divided by 11, and with this, $5342^{22}$ as well.

Németh Attila (Győr, Bencés g. I. o. t.)

Remarks: In transitioning to a smaller base and a smaller exponent, our solvers used a number of other transformations in addition to the above thought processes. Some of these (the capital letters denote integers):

$$
\begin{gathered}
5342=11 \cdot 486-4 ; \quad(-4)^{82}=2^{164}=2^{4}\left(2^{5}\right)^{32}=16(33-1)^{32}= \\
=16\left(11 M_{1}-1\right)^{32}=16 \cdot 11 M_{2}+16(-1)^{32} \text {-the remainder when divided by 11 is the same as that of 16; } \\
7^{82}=49^{41}=\left(11 P_{1}+5\right)^{41}=11 P_{2}+5^{41} ; 5^{41}=5 \cdot 25^{20}=5(11 \cdot 2+3)^{20}= \\
=11 P_{3}+5 \cdot 3^{20} ; 5 \cdot 3^{20}=5 \cdot 81^{5}=5(11 \cdot 7+4)^{5}=11 P_{4}+5 \cdot 4^{5} ; \\
5 \cdot 4^{5}=20 \cdot 4^{4}=(11+9)(11 \cdot 23+3) \text { the remainder is the same as that of } 9 \cdot 3=27 \text {. }
\end{gathered}
$$

The first step of the last transformation shows that a larger base can also be useful. Similar to the second solution, the remainders of the first, second, ..., sixth powers of 49 when divided by 11 are $5,3,4,9,1,5$, respectively; thus the remainders of the 10th, 15th, ..., 40th powers are 1 again, and the 41st is 5.[^0]


[^0]:    ${ }^{1}$ We can also arrive at this conclusion as follows: $5342^{82}-7^{82}$ is divisible by $5342-7=11 \cdot 485$, and thus by 11 as well; however, this does not show how the number 7 came into our consideration.

    ${ }^{2}$ See, for example, Kürschák-Hajós-Neukomm-Surányi: Mathematical Competition Problems, Part I, Secondary School Special Topics, Tankönyvkiadó 1955, pp. 58 and 45; or: Faragó László: Elements of Number Theory, Secondary School Special Topics, Tankönyvkiadó 1954, pp. 75 and 48.