Determine the smallest positive integer $n$ with the following property: For all positive integers $x, y$, and $z$ with $x \mid y^{3}$ and $y \mid z^{3}$ and $z \mid x^{3}$, it always holds that $x y z \mid (x+y+z)^{n}$.

(Gerhard J. Woeginger)

Answer. The smallest such number is $n=13$.
We note that $x y z \mid (x+y+z)^{n}$ holds if and only if for every prime $p$ the inequality

$$
v_{p}(x y z) \leq v_{p}\left((x+y+z)^{n}\right)
$$

is satisfied, where as usual $v_{p}(m)$ denotes the exponent of $p$ in the prime factorization of $m$.

Let $x, y$ and $z$ be positive integers with $x \mid y^{3}, y \mid z^{3}$ and $z \mid x^{3}$. Let $p$ be any prime, and without loss of generality, let the multiplicity of $p$ in $z$ be the smallest, i.e., $v_{p}(z) = \min \left\{v_{p}(x), v_{p}(y), v_{p}(z)\right\}$.

On the one hand, we have $v_{p}(x+y+z) \geq v_{p}(z)$, and on the other hand, it follows from the divisibility relations that $v_{p}(x) \leq 3 v_{p}(y) \leq 9 v_{p}(z)$. Overall, we therefore obtain

$$
\begin{aligned}
v_{p}(x y z) & = v_{p}(x) + v_{p}(y) + v_{p}(z) \\
& \leq 9 v_{p}(z) + 3 v_{p}(z) + v_{p}(z) = 13 v_{p}(z) \\
& \leq 13 v_{p}(x+y+z) = v_{p}\left((x+y+z)^{13}\right),
\end{aligned}
$$

which means that the required property is satisfied for $n=13$.

It remains to show that this is already the smallest possible number with this property. Let $n$ now be a number that has the desired property. Set $(x, y, z) = \left(p^{9}, p^{3}, p^{1}\right)$ for a prime $p$ (to ensure that both inequalities in (12) are satisfied with equality), so we get

$$
\begin{aligned}
13 & = v_{p}\left(p^{13}\right) = v_{p}\left(p^{9} \cdot p^{3} \cdot p^{1}\right) = v_{p}(x y z) \\
& \leq v_{p}\left((x+y+z)^{n}\right) = v_{p}\left(\left(p^{9} + p^{3} + p^{1}\right)^{n}\right) = n \cdot v_{p}\left(p\left(p^{8} + p^{2} + 1\right)\right) = n.
\end{aligned}
$$

Thus, we have shown $n \geq 13$.

Remark. In fact, all $n \geq 13$ have this property, since $(x+y+z)^{n}$ is then a multiple of $(x+y+z)^{13}$.

(Birgit Vera Schmidt, Gerhard Woeginger)