\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}
