Generalization of the Chinese remainder theorem
type: Item
instance of: scholarly article
title: Generalization of the Chinese remainder theorem
zbMATH Open document ID: 1171.15017
DOI: 10.3103/S1063454107030077
author: I. M. Davydova
author: E. Ya. Fedoseeva
published in: Vestnik St. Petersburg University. Mathematics
publication date: 2008-09-22T00:00:00Z
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''.
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 11A07
Mathematics Subject Classification ID: 03B35
Mathematics Subject Classification ID: 15A06
Mathematics Subject Classification ID: 11C20
Mathematics Subject Classification ID: 15A15
zbMATH DE Number: 5345537
zbMATH Keywords: Chinese remainder theorem
zbMATH Keywords: systems of linear equations
zbMATH Keywords: integer solutions
zbMATH Keywords: basis matrices
zbMATH Keywords: saturated matrices
zbMATH Keywords: marginal matrices
zbMATH Keywords: permanents
MaRDI profile type: Publication
cites work: Solvable matrices
cites work: An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
Recommended article: Q5430239
Recommended article: The generalization of the Chinese remainder theorem
Recommended article: A Generalized Chinese Remainder Theorem
Recommended article: Q3203066
Recommended article: Q3731662
Recommended article: The Chinese remainder theorem
Recommended article: Some remarks on the Chinese remainder theorem
Recommended article: A Robust Generalized Chinese Remainder Theorem for Two Integers
description: scientific article; zbMATH DE number 5345537