Let $N$ and $M$ be positive integers, and $p$ and $q$ be distinct prime numbers. Suppose that $N+M$ is a five-digit number, $N$ is divisible by $p$, and the number of its divisors is $q$, while $M$ is divisible by $q$, and the number of its divisors is $p$. Determine the possible values of $N$ and $M$.
To determine the number of divisors of a number, we multiply the numbers that are one greater than the exponents in its prime factorization. In our case, this product must be a prime number. If more than one prime factor were present in the prime factorization, the number of divisors would not be a prime number; thus, both numbers must be prime powers.

From this, it follows that if the number $N$ has $q$ divisors, then its exponent is $(q-1)$. Since only one prime appears in the prime factorization of $N$ and $N$ is divisible by $p$, this prime must be $p$. Therefore, $N=p^{q-1}$. Similarly, we get $M=q^{p-1}$.

We need to examine when the sum $N+M=p^{q-1}+q^{p-1}$ is a five-digit number. The right side of the equation remains the same if $p$ and $q$ are swapped, so for simplicity, we assume $p \leq q$. If $p^{q-1}$ is at least a six-digit number, then the sum $p^{q-1}+q^{p-1}$ is also at least a six-digit number. Since $2^{18}$, $3^{12}$, $5^{10}$, and $7^{6}$ are all at least six-digit numbers, we only need to check the following 13 cases (the corresponding $p^{q-1}+q^{p-1}$ values are listed in the table).

| $p q q$ | 2 | 3 | 5 | 7 | 11 | 13 | 17 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 2 | 4 | 7 | 21 | 71 | 1035 | 4109 | **65553** |
| 3 |  | 18 | 106 | 778 | **59170** |  |  |
| 5 |  |  | 1250 | **18026** |  |  |  |

In these cases, the possible values of $N$ and $M$ (considering that they can be swapped) are:

| $p$ | $q$ | $N$ | $M$ |
| :---: | :---: | :---: | :---: |
| 2 | 17 | 65536 | 17 |
| 17 | 2 | 17 | 65536 |
| 3 | 11 | 59049 | 121 |
| 11 | 3 | 121 | 59049 |
| 5 | 7 | 15625 | 2401 |
| 7 | 5 | 2401 | 15625 |

Note. Unfortunately, during the grading, relatively few solutions received full marks. Many provided the primes but not the numbers $N$ and $M$, which was a result of inattention. Many also provided only three solutions instead of six, and did not realize that $N$ and $M$ can be swapped. Many did not provide sufficiently detailed reasoning, resulting in lost points (usually either they did not derive the expressions for $N$ and $M$ in terms of $p$ and $q$, or they only listed the correct primes, showed that they were indeed correct, but did not explain why other solutions were not possible). Those who provided only the final result without any reasoning received 0 points, as the competition rules state that points cannot be awarded for just the result. However, there were also some excellent solutions.