\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{gcd det}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 97}
\maketitle
\section*{Problem}
Let $n$ be a given positive integer.
Find the determinant of the $n \times n$ matrix
whose $(i,j)$th entry is $\gcd(i,j)$.
\section*{Video}
\href{https://www.youtube.com/watch?v=SnEj4CljU18&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/SnEj4CljU18}}
\newpage
\section*{Solution}
The answer is the product $\varphi(1) \varphi(2) \dots \varphi(n)$,
where $\varphi$ is the Euler phi function.
The proof is by induction on $n$,
with base cases immediate.
The main claim is that we can eliminate nearly all
of the entries in the last column by doing column operations.
To be precise:
\begin{claim*}
Let $n = p_1^{e_1} \dots p_k^{e_k}$.
Then for any integer $1 \le m \le n$, we have
\[
\sum_{S \subseteq \{1,2,\dots,k\}}
(-1)^{|S|} \gcd\left(m, \frac{n}{\prod_{i \in S} p_i}\right)
=
\begin{cases}
0 & m < n \\
\varphi(n) & m = n.
\end{cases}
\]
\end{claim*}
Hence, if the claim is true, then we can
take the $\frac{n}{\prod_{i \in S} p_i}$'th columns
for each nonempty $S$ and add/subtract them from the $n$th column
(subtraction if $|S|$ is odd, addition if $|S|$ is even).
This would leave all zeros except $\varphi(n)$ in the bottom right.
Since we didn't touch any of the other rows or columns,
the original problem is solved by induction.
\begin{proof}
[Proof of claim]
Let $m = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$.
The sum can be factored in the following way:
\[
\prod_{i=1}^k \left( p_i^{\min(a_i,e_i)}
- p_i^{\min(a_i,e_i-1)} \right).
\]
If $m = n$, then $a_i = e_i$ and the above product
becomes the usual factorization of the Euler phi function.
On the other hand, if $m < n$,
then there exists some particular index $i$
such that $a_i < e_i$.
That makes the corresponding term in the product zero,
and so the whole product vanishes.
\end{proof}
\end{document}