Over a million developers have joined DZone.

Smith's Determinant

DZone's Guide to

Smith's Determinant

· Big Data Zone ·
Free Resource

How to Simplify Apache Kafka. Get eBook.

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

\[\left|    \begin{array}{llll}       \gcd(1,1) & \gcd(1,2) & \ldots & \gcd(1, n) \\       \gcd(2,1) & \gcd(2,2) & \ldots & \gcd(2, n) \\       \vdots & \vdots & & \vdots \\       \gcd(n,1) & \gcd(n,2) & \ldots & \gcd(n, n)     \end{array}\right| = \varphi(1) \varphi(2) \cdots \varphi(n) \>

Here gcd(ij) 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(ij) above with f( gcd(ij) ) 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 ith spot along the diagonal.

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


Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}