A determinant

Let $\gcd(i, j)$ denote the greatest common divisor of $i, j$ and let $\varphi$ denote Euler's totient function. Prove that:

$$\begin{vmatrix}
\gcd(1,1) &\gcd(1, 2)  &\cdots  & \gcd(1,n)\\
 \gcd(2,1)&\gcd(2,2)  &\cdots  & \gcd(2,n)\\
 \vdots&  \vdots  & \ddots &\vdots \\
 \gcd(n,1)&\gcd(n,2)  &\cdots  &\gcd(n,n)
\end{vmatrix}= \prod_{j=1}^{n}\varphi(j)$$

Solution

Hidden Message

---

This is what we call Smith's determinant. You may want to look up for it. There are several proofs other elementary and others a bit more advanced.