Smith's Determinant

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 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.