Chinese remainder theorem for cyclotomic polynomials in Z[X]

By the Chinese remainder theorem, the canonical mapΨn:R[X]/(Xn−1)→⊕d|nR[X]/Φd(X) is an isomorphism when R is a field whose characteristic does not divide n and Φd is the dth cyclotomic polynomial. When R is the ring Z of rational integers, this map is injective but not surjective. In this paper, we give an explicit formula for the elementary divisors of the cokernel of Ψn (when R=Z) using the prime factorisation of n. We also give a pictorial algorithm using Young tableaux that takes O(n3+ϵ) bit operations for any ϵ>0 to determine a basis of Smith vectors (see Definition 3.1) for Ψn. In general when R is an integral domain, we prove that the determinant of the matrix of Ψ:R[X]/(∏jfj)→⨁jR[X]/(fj) written with respect to the standard basis is ∏1⩽i