\section*{Problem 2 - 051222}

Determine all non-negative integers \(n\) for which the number \(z=5^{n}-4^{n}\) is divisible by 61.
}

Every nonnegative integer \(n\) can be represented in exactly one of the following forms:

\[
n=3 k \quad \text { or } \quad n=3 k+1 \quad \text { or } \quad n=3 k+2
\]

Here, \(k\) is a nonnegative integer. For \(n=3 k\), we have:

\[
z=5^{3 k}-4^{3 k}=\left(5^{3}\right)^{k}-\left(4^{3}\right)^{k}
\]

Since \(a^{m}-b^{m}\) is always divisible by \((a-b)\) for all nonnegative integers \(m\), \(\left(5^{3}\right)^{k}-\left(4^{3}\right)^{k}\) is divisible by \(5^{3}-4^{3}=61\).

For \(n=3 k+1\), we have:

\[
z=5^{3 k+1}-4^{3 k+1}=5 \cdot 5^{3 k}-4 \cdot 4^{3 k}=5\left(5^{3 k}-4^{3 k}\right)+4^{3 k}
\]

In this case, \(z\) is not divisible by 61, because the term \(5\left(5^{3 k}-4^{3 k}\right)\) is divisible by 61, but the term \(4^{3 k}\) is not.

For \(n=3 k+2\), we have:

\[
z=5^{3 k+2}-4^{3 k+2}=25 \cdot 5^{3 k}-16 \cdot 4^{3 k}=25\left(5^{3 k}-4^{3 k}\right)+9 \cdot 4^{3 k}
\]

In this case, \(z\) is also not divisible by 61, because the term \(25\left(5^{3 k}-4^{3 k}\right)\) is divisible by 61, but the term \(9 \cdot 4^{3 k}\) is not.

Therefore, the number \(z=5^{n}-4^{n}\) is divisible by 61 if and only if \(n\) is divisible by 3.

Adapted from [5]