Non-negative integer linear congruences

DOI10.1016/S0019-3577(06)80005-4MaRDI QIDQ2500585zbMATH OpenFDO

Authors John C. Harris, David Wehlau

Publication date 17 August 2006

Published in Indagationes Mathematicae. New Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0409489

zbMATH Keywords

congruence many variables

Mathematics Subject Classification ID

Congruences in many variables (11D79)

Abstract: We consider the problem of describing all non-negative integer solutions to a linear congruence in many variables. This question may be reduced to solving the congruence

x_{1} + 2 x_{2} + 3 x_{3} + ... + (n - 1) x_{n - 1} e q u i v 0 p m o d n

where values of the unknowns,

x_{i}

, are sought among the non-negative integers. We consider the monoid of solutions of this equation and prove a conjecture of Elashvili concerning the structure of these solutions. This yields a simple algorithm for generating most (conjecturally all) of the high degree indecomposable solutions of the equation.

Review text

A solution of the congruence \(\sum_{i=1}^{n-1} i x_i \equiv 0 \bmod n\) is called indecomposable if it is not the sum of two non-zero solutions. The authors show that two (open) conjectures of Alexander Elashvili about indecomposable solutions are equivalent.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Non-negative integer linear congruences

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