  Let $X = (x_1,\dots,x_n)$ be a vector of distinct positive integers. The $n
\times n$ matrix $S = S(X) := (\gcd(x_i,x_j))_{i,j=1}^n$, where $\gcd(x_i,x_j)$
denotes the greatest common divisor of $x_i$ and $x_j$, is called the greatest
common divisor (GCD) matrix on $X$. By a surprising result of Beslin and Ligh
[Linear Algebra and Appl. 118], all GCD matrices are positive definite. In this
paper, we completely characterize the GCD matrices satisfying the stronger
property of being totally nonnegative (TN) or totally positive (TP). As we
show, a GCD matrix is never TP when $n \geq 3$, and is TN if and only if it is
$\textrm{TN}_2$, i.e., all its $2 \times 2$ minors are nonnegative. We next
demonstrate that a GCD matrix is $\textrm{TN}_2$ if and only if the exponents
of each prime divisor in the prime factorization of the $x_i$s form a monotonic
sequence. Reformulated in the language of kernels, our results characterize the
subsets of integers over which the kernel $K(x,y) = \gcd(x,y)$ is totally
nonnegative. The proofs of our characterizations depend on Gantmacher and
Krein's notion of a Green's matrix. We conclude by showing that a GCD matrix is
TN if and only if it is a Green's matrix. As a consequence, we obtain explicit
formulas for all the minors and for the inverse of totally nonnegative GCD
matrices.
