4. Determine all natural numbers $n>1$ such that in some number system with $b a s e z \geqq 5$ the following divisibility criterion holds: a three-digit number $(a b c)_{z}$ is divisible by the number n if and only if the number $c+3 b-4 a$ is divisible by $n$.
SOLUTION. Since $(a b c)_{z}$ is the number $a z^{2}+b z+c$, we need to determine when the equivalence generally holds: $n \mid c+3 b-4 a$ if and only if $n \mid a z^{2}+b z+c$. Here, $a, b, c$ are arbitrary digits in base $z$, i.e., numbers from the set $\{0,1, \ldots, z-1\}$. Note that $z-1 \geq 4$, since we assume that $z \geq 5$.

If we choose $a=b=c=1$, we get that $n \mid 0$ if and only if $n \mid z^{2}+z+1$. Since zero is divisible by any integer, it must be that $n \mid z^{2}+z+1$. If we choose $a=1, b=0$ and $c=4$, we get that $n \mid 0$ if and only if $n \mid z^{2}+4$. By similar reasoning as above, we find that $n \mid z^{2}+4$.

If a number divides two numbers, it must also divide their greatest common divisor, so $n \mid \operatorname{gcd}\left(z^{2}+4, z^{2}+z+1\right)$. We find this common divisor using the Euclidean algorithm:

$$
\begin{aligned}
\operatorname{gcd}\left(z^{2}+4, z^{2}+z+1\right) & =\operatorname{gcd}\left(z^{2}+4, z^{2}+z+1-\left(z^{2}+4\right)\right)=\operatorname{gcd}\left(z^{2}+4, z-3\right)= \\
& =\operatorname{gcd}\left(z^{2}+4-z(z-3), z-3\right)=\operatorname{gcd}(4+3 z, z-3)= \\
& =\operatorname{gcd}(4+3 z-3(z-3), z-3)=\operatorname{gcd}(13, z-3) .
\end{aligned}
$$

We have found that $n \mid 13$. Since $n>1$, it must be that $n=13$. If any $n$ has the required property, it must be the number $n=13$.

Let's prove that the number 13 indeed has the required property. The necessary condition $n \mid \operatorname{gcd}(13, z-3)$ is satisfied for $n=13$ for example when $z=16$. The given equivalence then takes the form $13 \mid c+3 b-4 a$ if and only if $13 \mid a \cdot 16^{2}+b \cdot 16+c$. We will prove a stronger property, namely that the numbers $a \cdot 16^{2}+b \cdot 16+c$ and $c+3 b-4 a$ give the same remainder when divided by thirteen, or that their difference is divisible by thirteen:

$$
\left(a \cdot 16^{2}+b \cdot 16+c\right)-(c+3 b-4 a)=260 a+13 b=13(20 a+b) .
$$

The problem has a unique solution $n=13$.

Note. Similarly to the conclusion of the solution, we can prove that the given divisibility criterion for $n=13$ holds in any number system with base $z=13 k+3$.