Characteristic polynomial of the Gcd matrix Let $A_n$ be the $n \times n$-matrix with entries $\gcd(i,j)$ and $f_n$ the characteristic polynomial of $A_n$.

Question: Is $f_n$ irreducible over $\mathbb{Q}$ for all $n$ except $n=8$?

This is true for $n \leq 60$.
 A: Edit. See the calculation modulo $2$ below.
This is not an answer, but it is too long for a comment. The matrix $A_n$ can be decomposed as $A_n=D_n^T\Phi_nD_n$ where the entries of $D_n$ (D for divisors, not for diagonal) are either $1$ if $i|j$, or $0$ otherwise, and $\Phi_n={\rm diag}(\phi(1),\ldots,\phi(n))$, $\phi$ being the Euler's totient function.
Notice that the matrix $D_n$ is the $n\times n$ upper-left block of an infinite upper triangular matrix $D$. Its diagonal is made of $1$s, so that $\det D_n=1$. Thus
$$f_n(X)=\det(XD_n^{-T}D_n^{-1}-\Phi_n).$$
The matrix $D_n^{-T}D_n^{-1}$ is the $n\times n$ upper-left block of $D^{-T}D^{-1}$. The entries of $D^{-1}$ are known to be either $\mu(j/i)$ if $i|j$, or $0$ otherwise. Therefore
$$(D_n^{-T}D_n^{-1})_{ij}=\sum_{k|i,j}\mu\left(\frac ik\right)\mu\left(\frac jk\right).$$
For instance this is zero when $p^2|j$ but $p$ does not divide $i$. Also the diagonal entry corresponding to $j=i$ equals $2^r$, where $r$ is the number of distinct prime factors of $i$. A closed formula is that the $(i,j)$-entry equals
$$\mu\left(\frac{{\rm lcm}(i,j)}{{\rm gcd}(i,j)}\right)2^{P(i,j)},$$
where $P(i,j)$ is the number of distinct prime factors of ${\rm gcd}(i,j)$ for which the valuations agree:
$$v_p(i)=v_p(j)\ge1.$$
Calculation modulo 2. Since $\phi(j)$ is even for every $j\ge3$, the matrix $\Phi_n$ reduces to ${\rm diag}(1,1,0,\ldots,0)$. Thus $f_n(X)=X^n-aX^{n-1}+bX^{n-2}$ where
$$a=(D_n^{-T}D_n^{-1})\binom{\hat1}{\hat1}+(D_n^{-T}D_n^{-1})\binom{\hat2}{\hat2}$$
is the sum of minors obtained by deleting either the first row and column, or the second,
and
$$b=(D_n^{-T}D_n^{-1})\binom{\widehat{12}}{\widehat{12}}$$ is the minor when deleting the two first columns and rows. Because $\det(D_n^{-T}D_n^{-1})=1$, this gives
$$a=(D_nD_n^T)_{11}+(D_nD_n^T)_{22},\qquad b=(D_nD_n^T)\binom{12}{12},$$
the latter being a $2\times2$ minor. These quantities involve only the two first rows $(1,\ldots,1)$ and $(0101\ldots)$ of $D_n$. We obtain
$$a=n^2+\lfloor\frac n2\rfloor^2=n+\lfloor\frac n2\rfloor,\qquad b=n\lfloor\frac n2\rfloor-\lfloor\frac n2\rfloor^2=(n+1)\lfloor\frac n2\rfloor.$$
Hence (mod $2$)
$$f_n(X)=\left\{\begin{array}{lcr} X^n, & & n=0,3, \\
X^{n-1}(X+1), & & n=1 \\ X^{n-2}(X^2+X+1), & & n=2. \end{array}\right.$$
