Generalization of the Chinese remainder theorem

DOI10.3103/S1063454107030077MaRDI QIDQ946010zbMATH OpenFDO

Authors I. M. Davydova, E. Ya. Fedoseeva

Publication date 22 September 2008

Published in Vestnik St. Petersburg University. Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/S1063454107030077

zbMATH Keywords

basis matricesChinese remainder theoreminteger solutionsmarginal matricespermanentssaturated matricessystems of linear equations

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Congruences; primitive roots; residue systems (11A07) Matrices, determinants in number theory (11C20) Linear equations (linear algebraic aspects) (15A06) Determinants, permanents, traces, other special matrix functions (15A15) Matrices of integers (15B36)

Review text

Let \(B\) denote an \(m \times (m+1)\) \textit{basis} matrix with integer entries, and let \(r\) denote a column vector with \(m\) integer components. This paper presents sufficient conditions for vector solutions \(x\) with integer components of the linear system \(Bx = r\) in the cases that \(B\) is \textit{marginal} as well as \textit{saturated.} In the marginal case an integer solution exists, if all nonzero entries of \(B\) are pairwise coprime. This immediately generalizes the situation in the classical Chinese remainder theorem given in its matrix form. The proof cleverly involves the notion and basic features of the permanent of matrices. It should be mentioned that the final part of the statement of Theorem 1, in order to describe what is really meant, should be replaced by ``\dots and its \(i_0\)th row is permuted with the leading row of the new matrix.

Recommendations

• scientific article; zbMATH DE number 5219956
• The generalization of the Chinese remainder theorem
• A Generalized Chinese Remainder Theorem
• Publication:3203066
• scientific article; zbMATH DE number 3963911
• The Chinese remainder theorem
• Some remarks on the Chinese remainder theorem
• A Robust Generalized Chinese Remainder Theorem for Two Integers

Cites work

• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Solvable matrices

Cited in

(11)

• Systems of linear congruences with individual moduli
• Chinese remainder theorem for cyclotomic polynomials in \(\mathbb Z[X]\)
• scientific article; zbMATH DE number 4179430 (Why is no real title available?)
• Four proofs of the converse of the Chinese Remainder Theorem
• scientific article; zbMATH DE number 3902730 (Why is no real title available?)
• scientific article; zbMATH DE number 3963911 (Why is no real title available?)
• scientific article; zbMATH DE number 24597 (Why is no real title available?)
• Efficient remainder rule
• On Solving a Generalized Chinese Remainder Theorem in the Presence of Remainder Errors
• Simplification on dynamic range of a generalized Chinese remainder theorem for multiple integers
• Chinese remainder theorem with non-coprime moduli

This page was built for publication: Generalization of the Chinese remainder theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q946010)