Cfrgtkky

Let $A=[a_{ij}]_{n×n}$ be the matrix defined by letting $a_{ij}$ be the rational number such that $$a_{ij}=gcd(i,j ).$$ How prove that $A$ is invertible, and compute $det(A)$? thanks in advance

There is a general trick that applies to this case.

Assume a matrix $A=(a_{i,j})$ is such that there exists a function $psi$ such that
$$
a_{i,j}=sum_{k|i,k|j}psi(k)
$$
for all $i,j$.

Then
$$
det A=psi(1)psi(2)cdotspsi(n).
$$
To see this, consider the matrix $B=(b_{i,j})$ such that $b_{i,j}=1$ if $i|j$ and $b_{i,j}=0$ otherwise. Note that $B$ is upper-triangular with ones on the diagonal, so its determinant is $1$.

Now let $C$ be the diagonal matrix whose diagonal is $(psi(1),ldots,psi(n))$.

A matrix product computation shows that
$$
A=B^tCBquadmbox{hence}quad det A=(det B)^2det C=psi(1)cdotspsi(n).
$$

Now going back to your question.
Consider Euler's totient function $phi$.
It is well-known that
$$
m=sum_{k|m}phi(k)
$$
so
$$
a_{i,j}=gcd(i,j)=sum_{k|gcd(i,j)}phi(k)=sum_{k|i,k|j}phi(k).
$$

Applying the general result above, we find:
$$
det A=phi(1)phi(2)cdotsphi(n).
$$

This is a nice result. We have
$$ det(A)= phi(1)phi(2)dotsphi(n), $$
where $phi$ is Euler's phi function, $phi(n)$ being the number of positive integers $ile n$ that are relatively prime with $n$. It satisfies
$$ sum_{jmid n}phi(j)=n, $$
which we use below.

Let's write $a_n$ for the determinant of the $ntimes n$ version of $A$. The sequence $a_1,a_2,a_3,dots$ begins $$ 1, 1, 2, 4, 16, 32, 192, dots $$
which OEIS catalogs as $A001088$.

A cute short proof that only uses basic linear algebra (LDU decomposition) appears in a recent note,

Warren P. Johnson. An $LDU$ Factorization in Elementary Number Theory, Math. Mag. 76 (5), (2003), 392–394. MR1573717.

What one shows is that
$$ A=LPhi L^T $$ where $L$ is the $ntimes n$ matrix whose $i,j$ entry
is $1$ if $j$ divides $i$, and is $0$ otherwise, and $Phi$ is the diagonal matrix whose $i,i$ entry is $phi(n)$. Note that $L$ is lower diagonal, with $1$s as entries along its main diagonal, so $det(L)=det(L^T)=1$, and the result follows once we prove that $A=LPhi L^T$, as claimed. Johnson calls this Le Paige's result, who established it to compute $det(A)$ (originally found by H. J. S. Smith around 1875, according to the references at the OEIS site).

To prove Le Paige's result, simply expand $LPhi L^T$, and note that its $i,j$ entry is
$$ sum_{k=1}^n L_{ik}Phi_{kk}(L^T)_{kj}=sum_{k=1}^n L_{ik}phi(k) L_{jk}=sum_{kmid i,kmid j}phi(k) =sum_{k|{rm gcd}(i,j)} phi(k)={rm gcd}(i,j)=A_{ij}, $$
where I use $B_{ij}$ to denote the $i,j$ entry of the matrix $B$.