70. For which natural numbers $n$ is the sum $5^{n}+n^{5}$ divisible by 13? What is the smallest $n$ that satisfies this condition?
70. First, let's find the remainders of the division by 13 of the numbers \(5^n\) and \(n^5\) for the first few values of \(n = 0, 1, 2, \ldots\). It is more convenient to start with the numbers \(5^n\):

\(n\)

| 0 | 1 | 2 | 3 | 4 | . | . | . |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| 1 | 5 | 25 | 125 | 625 | . | . | . |
| 1 | 5 | -1 | -5 | 1 | . | . | . |

[Here we write the remainder -1 instead of "remainder 12" and "remainder -3" instead of "remainder 8", which allows us to easily find all subsequent remainders: if \(5^n\) gives a remainder of -1 when divided by 13, i.e., \(5^n = 13k - 1\), where \(k\) is an integer, then \(5^{n+1} = 5^n \cdot 5 = (13k - 1) \cdot 5 = 13(5k) - 5\) gives a remainder of -5 when divided by 13; similarly, if \(5^m\) gives a remainder of -5 when divided by 13, i.e., \(5^m = 13l - 5\), then \(5^{m+1} = 5^m \cdot 5 = (13l - 5) \cdot 5 = 13(5l) - 25 = 13(5l - 2) + 1\) gives a remainder of 1 when divided by 13.] There is no need to continue the table further: since \(5^4 = 13q + 1\), then \(5^5 = 5^4 \cdot 5 = (13q + 1) \cdot 5\) gives the same remainder as the number 5 (remainder 5) when divided by 13; the number \(5^6 = 5^4 \cdot 5^2 = (13q + 1) \cdot 5^2\) gives the same remainder as the number \(5^2\) (remainder -1) when divided by 13, and so on; thus, in our "sequence of remainders," the numbers \(1, 5, -1, -5\) alternate sequentially.

Similarly, we can create a table of remainders from the division by 13 of the numbers \(n^5\), where \(n = 0, 1, 2, \ldots\), and so on. But the number \((13p + r)^5 = \frac{(13p + r)(13p + r) \ldots (13p + r)}{5 \text{ factors}}\) gives the same remainder as the number \(r^5\) when divided by 13; therefore, it is sufficient to limit ourselves to the values \(n = 0, 1, 2, 3, \ldots, 12\). Further, if the number \(n\) is equal to (or gives a remainder of) \(s\) when divided by 13, and the number \(n^2\) gives a remainder of \(t\) when divided by 13, then the number \(n^5 = n^2 \cdot n^2 \cdot n\) gives the same remainder as the product \(t \cdot t \cdot s\) when divided by 13—this fact can simplify the creation of the required table for the values \(n = 4, 5, 6\). Finally, note that if the number \(n^5\) gives a remainder of \(u\) when divided by 13, then the number \((13 - n)^5 = \underbrace{(13 - n)(13 - n) \ldots (13 - n)}\) gives the same remainder as the number \((-n)^5\), i.e., the remainder -u, or \(13 - u\).

Now we can create our table:

![](https://cdn.mathpix.com/cropped/2024_05_21_b937612abb2773f7abffg-128.jpg?height=648&width=971&top_left_y=176&top_left_x=52)

(The remainders corresponding to the values \(n = 7, 8, \ldots, 12\) are written based on the fact that the numbers \(n^5\) and \((13 - n)^5\) give "complementary" remainders \(u\) and \(-u\).) After the value \(n = 12\) in our table, the same remainders \(0, 1, 6, -4, -3, 5, 2, -2, -5, 3, 4, -6, -1\) will "periodically" repeat.

Since the first table has a "period" of 4, and the second has a "period" of 13, the value \(4 \cdot 13 = 52\) is the "period" of the combination of both tables: increasing \(n\) by 52 (or any multiple of 52) does not change the remainders of the division by 13 of both numbers \(5^n\) and \(n^5\). Further, we are only interested in those columns of the second table that correspond to remainders \(\pm 1\) and \(\pm 5\) (since in the first table, only the remainders \(1, 5, -1, -5\) alternate). But within the range from \(n = 0\) to \(n = 51\), the remainder 1 in the second table corresponds to the values \(n = 1, 1 + 13 = 14\), \(1 + 2 \cdot 13 = 27\), and \(1 + 3 \cdot 13 = 40\); of these four numbers, only 14 has the form \(4x + 2\), which in the first table corresponds to the remainder -1; thus, the number \(n = 14\) satisfies the required condition \((5^{14} + 14^5\) is divisible by 13\). Similarly, the remainder -1 in the second table within the same range corresponds to the values \(n = 12, 12 + 13 = 25\), \(12 + 2 \cdot 13 = 38\), and \(12 + 3 \cdot 13 = 51\); of these numbers, only 12 has the form \(4y\), which in the first table leads to the remainder 1. Similarly, the remainder 5 in the second table corresponds to the values \(n = 5, 5 + 13 = 18\), \(5 + 2 \cdot 13 = 31\), and \(5 + 3 \cdot 13 = 44\), and the remainder -5 to the values \(n = 8, 8 + 13 = 21\), \(8 + 2 \cdot 13 = 34\), and \(8 + 3 \cdot 13 = 47\); but of the first four numbers, only 31 has the form \(4z + 3\), ensuring a remainder of -5 from the division of \(5^{31}\) by 13, and of the last four numbers, only 21 has the form \(4\tau + 1\), ensuring a remainder of 5 from the division of \(5^{21}\) by 13. Thus, within the range \(0 \leq n \leq 52\), the required condition is satisfied by the following four natural numbers: \(n = 12, 14\), 21, and 31; the entire set of natural numbers satisfying the condition of the problem consists of the following four "series" of numbers:

\[
\begin{gathered}
n = 52m + 12, \quad n = 52m + 14 \text{ (i.e., } n = 26(2m) + 12 \quad n \\
= 26(2m + 1) - 12)
\end{gathered}
\]

\[
n = 52m + 21 \quad \text{and} \quad n = 52m + 31 \text{ (i.e., } n = 52m \pm 21 \text{);}
\]

here \(m = 0, 1, 2, \ldots\) (and in the formula \(n = 52m - 21\) we must have \(m > 0\)).

Clearly, the smallest \(n\) that satisfies the conditions of the problem is \(n = 12\).