Olimpiadi della Matematica

Solution:

a. If $d$ is a divisor of $n$ then $n / d$ is also a divisor of $n$. It follows that for every divisor $d$ of $n = k^{2}$ with $0 < d < k$ there exists a corresponding divisor $n / d$ with $n / d = k^{2} / d > k$, and conversely for every divisor $d$ of $k^{2}$ with $d > k$ there exists a corresponding divisor $0 < n / d < k$.
The positive divisors of $k^{2}$ less than $k$ are therefore just as many as those greater than $k$, as required.

Alternative solution. If $n$ is a perfect square, its prime factorization has the form $n = p_{1}^{2\alpha_{1}} \cdot p_{2}^{2\alpha_{2}} \cdots p_{i}^{2\alpha_{i}}$. Its divisors are numbers of the form $p_{1}^{\beta_{1}} \cdots p_{i}^{\beta_{i}}$, with $0 \leq \beta_{j} \leq 2\alpha_{j}$ for every $j = 1, \ldots, i$. In particular $k = p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}} \cdots p_{i}^{\alpha_{i}}$. If we write $n = d \cdot \frac{n}{d}$ as a product of two of its divisors, we must redistribute the prime factors of $n$ between the two divisors considered. We will thus have that the two factors are of the form
$$d = p_{1}^{\beta_{1}} \cdots p_{i}^{\beta_{i}}, \quad \frac{n}{d} = p_{1}^{2\alpha_{1} - \beta_{1}} \cdots p_{i}^{2\alpha_{i} - \beta_{i}}$$
which we can write, in terms of $k$, as
$$d = k \cdot p_{1}^{\beta_{1} - \alpha_{1}} \cdots p_{i}^{\beta_{i} - \alpha_{i}}, \quad \frac{n}{d} = k \cdot p_{1}^{\alpha_{1} - \beta_{1}} \cdots p_{i}^{\alpha_{i} - \beta_{i}}:$$
we are multiplying $k$ by a number and by its reciprocal, so one of $d$ and $n / d$ will be greater than $k$ and the other will be less than $k$. In particular, for every divisor less than $k$ there is one greater than $k$.

b. By what was shown in part (a), the divisors in total are twice those less than $k$ plus 1 (that is, the divisor $k$). The positive integers less than $k$ are $k-1$, so $n$ can have at most $2(k-1)+1 = 2k-1$ divisors.

c. Continuing the reasoning made in part (b), saying that $n = k^{2}$ has $2k-1$ divisors means that all positive integers less than or equal to $k$ divide $n$. Observe that for $k = 1$ we have $n = 1$, which has a unique positive divisor (itself), so indeed the number of divisors is $2k-1 = 2 \cdot 1 - 1$. Similarly, for $k = 2$ we have $n = 4$, whose divisors are $1, 2$ and $4$, as required: $2 \cdot 2 - 1 = 3$. We then observe that an integer $n$ has no divisors $>1$ in common with $n-1$. If $k \geq 3$ this leads to a contradiction: we observed that $k-1 > 1$ must divide $k^{2}$, and this is absurd because $k-1$ divides $n-1 = k^{2} - 1 = (k+1)(k-1)$. There are therefore no solutions for $k \geq 3$, so the desired $k$ are only $k = 1$ and $k = 2$.