\section*{Problem 1 - 071041}

What remainder does a natural number \(a\) leave when divided by 73, if the numbers \(a^{100}-2\) and \(a^{101}-69\) are divisible by 73?
}

If \(a\) is a natural number such that \(a^{100}-2\) and \(a^{101}-69\) are divisible by 73, then on the one hand, the divisibility of \(a^{101}-2a\) by 73 follows, i.e., the existence of an integer \(r\) with \(a^{101}-2a=73r\), and on the other hand, the existence of an integer \(s\) with \(a^{101}-69=73s\).

This implies \(2a-69=73(s-r)\), so there exists an integer \(t\) with

\[
2a=69+73t \rightarrow 2a=69+73+73(t-1) \rightarrow 2a=142+73(t-1)
\]

Since \(2a-69\) is odd, \(t\) must also be an odd number. Then \(t-1\) is even, i.e., of the form \(t-1=2n\), \(n\) an integer, and we have

\[
2a=142+2n \cdot 73 \quad \text{so} \quad a=71+73n
\]

The remainder when \(a\) is divided by 73 is therefore at most the number 71.

Additionally, it is shown that 71 as a remainder is actually possible, i.e., that there is at least one number \(a\) with the properties mentioned in the problem. This can be done as follows. We have:

\[
\begin{array}{rc}
71 \equiv -2 & (\bmod 73) \\
71^{9} \equiv (-2)^{9} = -512 \equiv -7 \cdot 73 - 1 \equiv -1 & (\bmod 73) \\
71^{99} \equiv 2 & (\bmod 73) \\
71^{100} \equiv -4 \equiv 69 & (\bmod 73)
\end{array}
\]

If more generally \(a \equiv 71 (\bmod 73)\), i.e., \(a \equiv -2 (\bmod 73)\), then

\[
a^{100} \equiv 2 \quad (\bmod 73) \quad ; \quad a^{101} \equiv -4 \quad (\bmod 73)
\]

Consequently,

\[
a^{100}-2 \equiv 2-2=0 \quad (\bmod 73) \quad ; \quad a^{101}-69 \equiv -4-(-4)=0 \quad (\bmod 73)
\]

Thus, exactly all natural numbers \(a \equiv -2 (\bmod 73)\) satisfy all the conditions of the problem.

Adapted from \([5]\)