Smith's Determinant
Join the DZone community and get the full member experience.
Join For Freehere’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.
Published at DZone with permission of John Cook, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Trending
-
Unlocking Game Development: A Review of ‘Learning C# By Developing Games With Unity'
-
Authorization: Get It Done Right, Get It Done Early
-
How To Use an Automatic Sequence Diagram Generator
-
Revolutionize JSON Parsing in Java With Manifold
Comments