som van machten

Opgave - EMC 2014 vraag 1

Bewijs dat er oneindig veel natuurlijke getallen zijn die niet kunnen geschreven worden als $a^{\tau(a)}+b^{\tau(b)}$, met $a$ en $b$ natuurlijke getallen.

($\tau(x)$ is het aantal positieve delers van $x$)

Oplossing

We gaan de volgende bewering bewijzen:
Bewering: Voor elke positieve gehele getal $n$, $n^{\tau(n)}$ is een volkomen kwadraat.
Bewijs
Voor $\tau(n)$ even, is het triviaal.
Voor $\tau(n)$ oneven,
laat $d_1, d_2, \cdots, d_k$ de positieve delers van $n$ zijn met $1 = d_1 < d_2 < \cdots < d_k = n$ en $k = \tau(n), k \equiv 1\pmod{2}$.
Dan hebben we:
\begin{equation*}
\begin{split}
d_1 \cdot d_k &= n\\
d_2 \cdot d_{k-1} &= n\\
&\vdots\\
d_{\frac{k+1}{2}-1} \cdot d_{\frac{k+1}{2}+1} &= n\\
d_{\frac{k+1}{2}} \cdot d_{\frac{k+1}{2}} &= n\\
\end{split}
\end{equation*}
Dus $d_{\frac{k+1}{2}}^2 = n$, dus $n$ is een volkomen kwadraat dat geeft dat $n^{\tau(n)}$ een volkomen kwadraat is.
Dus we zijn klaar. QED

Omdat $n^{\tau(n)}$ een volkomen kwadraat is voor alle positieve gehele getallen $n$, hebben we dat $a^{\tau(a)}, b^{\tau(b)}$ volkomen kwadraten zijn.
Merk op dat volkomen kwadraten $0$ of $1\pmod{4}$ zijn.
Dus $a^{\tau(a)} + b^{\tau(b)} \equiv 0 + 0 \equiv 0\pmod{4}$
of $a^{\tau(a)} + b^{\tau(b)} \equiv 0 + 1 \equiv 1\pmod{4}$
of $a^{\tau(a)} + b^{\tau(b)} \equiv 1 + 0 \equiv 1\pmod{4}$
of $a^{\tau(a)} + b^{\tau(b)} \equiv 1 + 1 \equiv 2\pmod{4}$
Dus elke geheel getal dat $3\pmod{4}$ is kan niet geschreven worden als $a^{\tau(a)} + b^{\tau(b)}$, dus we zijn klaar. QED