Here’s a curious identity I ran across while browsing Knuth’s magnum opus.

Here gcd(*i*, *j*) is the greatest common divisor of *i* and *j*, and φ(*n*) is Euler’s phi (or totient) function, the number of positive integers less than or equal to *n* and relatively prime to *n*.

The more general version of Smith’s determinant replaces gcd(*i*, *j*) above with *f*( gcd(*i*, *j*) ) for an arbitrary function *f*.

As a hint at a proof, you can do column operations on the matrix to obtain a triangular matrix with φ(*i*) in the *i*th spot along the diagonal.

**Source**: TAOCP vol 2, section 4.5.2, problem 42.

The first two elements in the second row are equal that the two ones in the first row. I think they would be gcd(2,1) and gcd(2,2), wouldn’t they?

Sorry about my poor English.

Francisco, thanks. I fixed the error.

Cute fact (proved by Smith in the same paper as the identity itself): the same identity holds if instead of {1,2,…,n} we use any set of positive integers with the property that all factors of elements of the set are themselves elements of the set.

(The same proof by doing column-ops proves this generalization with no extra work.)