## Task 36/77

The smallest natural number $n>1$ is sought, such that

$$
z_{n}=1977+n^{462}
$$

is divisible by 1978.
Due to $1977 \equiv -1(\bmod 1978)$, it must be that $n^{462} \equiv 1(\bmod 1978)$. Since $1978 \equiv 0(\bmod 2)$, it follows that $n \equiv 1(\bmod 2)$. Therefore, (since $n > 1$) $n \geq 3$.

The prime factorization of 1978 yields $1978 = 2 \cdot 23 \cdot 43$, and the prime factorization of 462 gives $462 = 2 \cdot 3 \cdot 7 \cdot 11$.

From this, the following representations can be derived:

$$
462 = 1 \cdot 462 = 22 \cdot 21 = 42 \cdot 11 = (2-1) \cdot 462 = (23-1) \cdot 21 = (43-1) \cdot 11
$$

Thus,

$$
n^{462} = \left(n^{2-1}\right)^{462} = \left(n^{23-1}\right)^{21} = \left(n^{43-1}\right)^{11}
$$

By Fermat's Little Theorem, $a^{p-1} \equiv 1(\bmod p)$ if $p$ is a prime and $a$ is not divisible by $p$. Since 2, 23, and 43 are primes and the smallest possible number 3 is not divisible by any of these three primes, it follows that

$$
3 \equiv 1(\bmod 2); \quad 3^{22} \equiv 1(\bmod 23); \quad 3^{42} \equiv 1(\bmod 43)
$$

Thus,

$$
\begin{aligned}
& 3^{462} \equiv 1(\bmod 2); \quad \left(3^{22}\right)^{21} \equiv 1(\bmod 23); \quad \left(3^{42}\right)^{11} \equiv 1(\bmod 43) \\
& 3^{462} \equiv 1(\bmod 2); \quad 3^{462} \equiv 1(\bmod 23); \quad 3^{462} \equiv 1(\bmod 43)
\end{aligned}
$$

Since 2, 23, and 43 are primes (pairwise coprime), it follows that

$$
3^{462} \equiv 1(\bmod 2 \cdot 23 \cdot 43) \equiv 1(\bmod 1978)
$$

Thus, $n = 3$ is the desired number. $3^{462}$ is a 221-digit number that starts with 269 and ends with 9.

### 2.18 Problems and Solutions 1978