Let $1=d_1<d_2<\ldots<d_{2m}=n$ be the divisors of a positive integer $n$, where $n$ is not a perfect square. Consider the determinant $$D=\begin{vmatrix}n+d_1&n&\ldots&n\\n&n+d_2&\ldots&n\\\ldots&\ldots&&\ldots\\n&n&\ldots&n+d_{2m}\end{vmatrix}.$$(a) Prove that $n^m$ divides $D$. (b) Prove that $1+d_1+d_2+\ldots+d_{2m}$ divides $D$.
Problem
Source: Moldova 2000 Grade 12 P1
Tags: determinant, divisbility, number theory
natmath
28.04.2021 00:57
We can subtract the first column from each other column to show that
$$D=\begin{vmatrix}n+d_1&-d_1& -d_1 &\ldots&-d_1\\n&d_2&0&\ldots&0\\ n& 0&d_3&\ldots &0\\\ldots&\ldots&\ldots&&\ldots\\n&0&0&\ldots&d_{2m}\end{vmatrix}.$$Define $D_k$ as the determinant of the matrix formed by the intersection of the first $k$ rows and columns of the above matrix (e.g. $D=D_{2m}$)
Expanding along the bottom row of $D_k$ for $k\geq 2$ (and then expanding on the rightmost column) we have,
$$D_k=(-1)^{k+1}n\cdot (-1)^{k}(-d_1)\prod_{i=2}^{k-1}d_i+(-1)^{2k}d_{k}D_{k-1}$$$$D_k=d_{k}D_{k-1}+n\prod_{i=1}^{k-1}d_i$$We also have the initial conditions
$$D_1=n+d_1$$
We claim that
$$D_k=\left(\prod_{i=1}^kd_i\right)\left(1+n\sum_{i=1}^k \frac{1}{d_i}\right)$$We proceed by induction.
Clearly this satisfies base cases of $D_1=n+d_1$ and $D_2=n(d_1+d_2)+d_1d_2$
For our inductive step, we take
$$d_kD_{k-1}+n\prod_{i=1}^{k-1} d_i$$$$d_k\left(\prod_{i=1}^{k-1}d_i\right)\left(1+n\sum_{i=1}^{k-1} \frac{1}{d_i}\right)+n\prod_{i=1}^{k-1}d_i$$$$\left(\prod_{i=1}^k d_i\right)\left(1+n\sum_{i=1}^{k-1} \frac{1}{d_i}\right)+\frac{n}{d_k}\prod_{i=1}^{k}d_i$$$$\left(\prod_{i=1}^k d_i\right)\left(1+\frac{n}{d_k}+n\sum_{i=1}^{k-1} \frac{1}{d_i}\right)$$$$\left(\prod_{i=1}^k d_i\right)\left(1+n\sum_{i=1}^{k} \frac{1}{d_i}\right)$$$$D_k$$Hence our hypothesized relation satisfies the entire recursion.
We have
$$D=D_{2m}=\left(\prod_{i=1}^{2m}d_i\right)\left(1+n\sum_{i=1}^{2m} \frac{1}{d_i}\right)$$$$D=\left(n^m\right)\left(1+\sum_{i=1}^{2m} d_i\right)$$
Hence $n^m$ and $1+d_1+d_2+\ldots+d_{2m}$ both divide $D$.