Let $$f(a,b)=\sum_{d|a, \ d|b}d.$$ Let $M=(a_{i,j})_{i,j=1}^{n}$. Evaluate $\det M$.
Solution. The idea is utilization of Lower-upper triangular decomposition. Using a software (like Mathematica) one observes that for small $n$ the matrices $L$ and $U$ coulde be intepreted as - $L=(l_{i,j})_{i,j=1}^{n}$, where $$l_{i,j}=\begin{cases} 1, & \text{j divides i}\\
0, & \text{otherwise} \end{cases}$$ and $U=(u_{i,j})_{i,j=1}^{n}$ where $$u_{i,j}=\begin{cases} i, & \text{i divides j}\\
0, & \text{otherwise} \end{cases}$$
It is directly verified that this holds in general (all $n$).
Obviously $\det L=1$, while $\det U=n!$ (the diagonal elements are $1,2,\ldots,n$). Thus $\det M=n!$.
The same idea could be employed for similar looking determinants, for example the one having $\gcd(i,j)$ at place $(i,j)$.
Prime divides element with index that prime
Let $s$ be a positive integer. Let $\{a_n\}_{n=1}^{\infty}$ be a
sequence given by $$a_1=0, \ a_2=2s, \ a_3=3, \ a_{n+3}=s a_{n+1}+a_n \ \
\ \text{for} \ n\ge 1.$$
Prove that for any prime number $p$, the number $a_p$ is divisible by $p$.
Solution. Let the roots of the equation $x^3-sx-1=0$ be $x_1, x_2$ and $x_3=-x_1-x_2$ (Vieta's formulas), they are algebraic integers (by definition). One directly observes (using the initial conditions) that $a_n=x_1^n+x_2^n+(-x_1-x_2)^n$. Assume $p>2$ (the other is obvious). We have
$$a_p=x_1^p+x_2^p+(-x_1-x_2)^p=-\sum_{k=1}^{p-1}{p\choose k}x_1^kx_2^{p-k}$$
${p\choose k}$ is divisible by $p$ for $1\le k \le p-1$, so we obtain that $a_p=p A$ where $A$ is an algebraic integer, since algebraic integers form a ring. However, from here we see that $A$ is also rational, hence $A$ is integer. Thus $p$ divides $a_p$.
I would like to thank Mr. Bozhilov for finding a mistake in the original proof, and his fruitful discussion, which led to a resolution.
The problem appeared at AKHIMO 2018.
Prove that for any prime number $p$, the number $a_p$ is divisible by $p$.
Solution. Let the roots of the equation $x^3-sx-1=0$ be $x_1, x_2$ and $x_3=-x_1-x_2$ (Vieta's formulas), they are algebraic integers (by definition). One directly observes (using the initial conditions) that $a_n=x_1^n+x_2^n+(-x_1-x_2)^n$. Assume $p>2$ (the other is obvious). We have
$$a_p=x_1^p+x_2^p+(-x_1-x_2)^p=-\sum_{k=1}^{p-1}{p\choose k}x_1^kx_2^{p-k}$$
${p\choose k}$ is divisible by $p$ for $1\le k \le p-1$, so we obtain that $a_p=p A$ where $A$ is an algebraic integer, since algebraic integers form a ring. However, from here we see that $A$ is also rational, hence $A$ is integer. Thus $p$ divides $a_p$.
I would like to thank Mr. Bozhilov for finding a mistake in the original proof, and his fruitful discussion, which led to a resolution.
The problem appeared at AKHIMO 2018.
Subscribe to:
Posts (Atom)