## Task 4.

For a natural number $n$, let $\tau(n)$ denote the number of natural divisors of the number $n$, and let $\tau_{1}(n)$ denote the number of natural divisors of the number $n$ that give a remainder of 1 when divided by 3. Determine all possible integer values of the fraction

$$
\frac{\tau(10 n)}{\tau_{1}(10 n)}
$$
## Solution.

Let $n=3^{a} \cdot b \cdot m$, where $a$ is a non-negative integer, and $b$ and $m$ are natural numbers (possibly 1) such that all prime factors of $b$ give a remainder of 1 when divided by 3, and those of $m$ give a remainder of 2.

Then $\tau(10 n)=(a+1) \cdot \tau(b) \cdot \tau(10 m)$.

For $\tau_{1}(n)$, the prime factor 3 must not be taken, prime factors from $b$ can be taken at will, and the only condition on those from $m$ is that they must be taken an even number of times. Therefore, $\tau_{1}(10 n)=\tau(b) \cdot \tau_{1}(10 m)$. Thus,

$$
\frac{\tau(10 n)}{\tau_{1}(10 n)}=(a+1) \cdot \frac{\tau(10 m)}{\tau_{1}(10 m)}
$$

Let $m=2^{c_{1}} \cdot 5^{c_{2}} \cdot p_{3}^{c_{3}} \cdots p_{k}^{c_{k}}$, then $\tau(10 m)=\left(c_{1}+2\right)\left(c_{2}+2\right)\left(c_{3}+1\right) \cdots\left(c_{k}+1\right)$. Consider two cases.

- The number $\tau(10 m)$ is even. Then one of the parentheses (in the expression for $\tau(10 m)$) is even. Let this parenthesis belong to the factor $p_{j}$ and let it be equal to $2 t$. If we choose each prime factor (except $p_{j}$) in any way, then we see that the number of occurrences of $p_{j}$ can be chosen in exactly $t$ ways. Therefore, in this case, $\tau_{1}(10 m)=\frac{1}{2} \tau(10 m)$. In this case, the given fraction can achieve values of the form $2(a+1)$, i.e., any even natural number is a possible value, and there are no other possibilities in this case.
- The number $\tau(10 m)$ is odd. All parentheses are odd, which means that the exponent of each prime factor is even. For each combination of exponents whose sum is even (i.e., which gives a divisor with a remainder of 1 when divided by 3), the first exponent that is not 0 is reduced by one, and for each combination that gives an odd sum, the last exponent that is not 0 (or the first if we reach the end) is increased by 1. In this way, all combinations with an odd sum are in a bijective relationship with all combinations with an even sum (except the one where all exponents are 0). This means that $\tau_{1}(10 m)=\frac{1}{2}(\tau(10 m)+1)$. Let $\tau(10 m)=t$. Therefore, in this case,

$$
\frac{\tau(10 n)}{\tau_{1}(10 n)}=2(a+1) \cdot \frac{t}{t+1}
$$

Since we are only interested in integer values of the fraction, we see that $t+1$ divides $2(a+1)$, so the above fraction is of the form $t t^{\prime}$, where $t^{\prime}$ is some natural number. Since all parentheses in $t$ are odd, we see that the first two are at least 3, so the number $t$ is composite. Therefore, the given fraction cannot be an odd prime number.

It remains to show that the given fraction can take the value $x y$, where $x$ and $y$ are natural numbers greater than 1. This is achieved for

$$
n=3^{\frac{x y-1}{2}} \cdot 2^{x-2} \cdot 5^{y-2}
$$

## CROATIAN MATHEMATICAL OLYMPIAD

## Final test for IMO team selection

Zagreb, May 6, 2017.