Join the DZone community and get the full member experience.Join For Free
How to Simplify Apache Kafka. Get eBook.
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 ith spot along the diagonal.
Source: TAOCP vol 2, section 4.5.2, problem 42.
Published at DZone with permission of John Cook , DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.