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.

12 Best Practices for Modern Data Ingestion. Download White Paper.


Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

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

{{ parent.tldr }}

{{ parent.urlSource.name }}