Restricted linear congruences

DOI10.1016/J.JNT.2016.07.018MaRDI QIDQ331108zbMATHOpenAlexFDO

Authors Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan, Roberto Tauraso, László Tóth

Publication date 26 October 2016

Published in Journal of Number Theory (Search for Journal in Brave)

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

zbMATH Keywords

discrete Fourier transformRamanujan sumrestricted linear congruence

Mathematics Subject Classification ID

Congruences; primitive roots; residue systems (11A07) Arithmetic functions; related numbers; inversion formulas (11A25) Congruences in many variables (11D79)

Abstract: In this paper, using properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions, we give an explicit formula for the number of solutions of the linear congruence $a_1{x}_1+cdots+a_k{x}_{k}equivbpmodn$, with $gcd(x_i,n)=t_i$ ($1leqileqk$), where $a_1,t_1,ldots,a_k,t_k,b,n$ ($ngeq1$) are arbitrary integers. As a consequence, we derive necessary and sufficient conditions under which the above restricted linear congruence has no solutions. The number of solutions of this kind of congruence was first considered by Rademacher in 1925 and Brauer in 1926, in the special case of $a_i=t_i=1$ $(1leqileqk)$. Since then, this problem has been studied, in several other special cases, in many papers; in particular, Jacobson and Williams [{it Duke Math. J.} {�f 39} (1972), 521--527] gave a nice explicit formula for the number of such solutions when $(a_1,ldots,a_k)=t_i=1$ $(1leqileqk)$. The problem is very well-motivated and has found intriguing applications in several areas of mathematics, computer science, and physics, and there is promise for more applications/implications in these or other directions.

Recommendations

• On a restricted linear congruence
• On the number of solutions of a restricted linear congruence
• A formula for the number of solutions of a restricted linear congruence
• scientific article; zbMATH DE number 3550776
• Order-restricted linear congruences

Cites work

• scientific article; zbMATH DE number 5014512 (Why is no real title available?)
• scientific article; zbMATH DE number 3106649 (Why is no real title available?)
• A CLASS OF ARITHMETICAL FUNCTIONS
• A Finite Analogue of the Goldbach Problem
• A Generalization of the Euler φ-Function
• A Multivariate Arithmetic Function of Combinatorial and Topological Significance
• A VON STERNECK ARITHMETICAL FUNCTION AND RESTRICTED PARTITIONS WITH RESPECT TO A MODULUS
• A unified method for treating a linear congruence with constraints
• Adding generators in cyclic groups
• Adding units mod \(n\)
• An extension of Ramanujan's sum. II. Additive properties
• Coprime solutions to \(ax\equiv b \pmod n\)
• Counting maps on doughnuts
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• Counting the number of solutions of linear congruences
• ERROR TERMS IN ADDITIVE PRIME NUMBER THEORY
• Enumeration of unrooted hypermaps of a given genus
• Enumeration of unrooted maps of a given genus
• Generalized compact knapsacks, cyclic lattices, and efficient one-way functions
• Introduction to arithmetical functions
• MMH* with arbitrary modulus is always almost-universal
• On a restricted linear congruence
• On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes
• On the addition of units and non-units in finite commutative rings
• On the addition of units and nonunits mod \(m\)
• On the number of distinguished representations of a group element
• On the sumset of atoms in cyclic groups
• Ramanujan sums as supercharacters
• Representations of even functions (mod \(r\)). III: Special topics
• Some remarks on a paper of V. A. Liskovets
• The discrete Fourier transform of \(r\)-even functions
• The power of primes: security of authentication based on a universal hash-function family

Cited in

(23)

• MMH* with arbitrary modulus is always almost-universal
• The number of restricted solutions of some systems of linear congruences
• The Modular Subset-Sum Problem and the size of deletion correcting codes
• Arithmetic sums subject to linear and congruent conditions and some applications
• scientific article; zbMATH DE number 3557872 (Why is no real title available?)
• Non-negative integer linear congruences
• Restricted congruences in computing
• A generalization of Schönemann's theorem via a graph theoretic method
• scientific article; zbMATH DE number 3550776 (Why is no real title available?)
• On a restricted linear congruence
• Order-restricted linear congruences
• Unweighted linear congruences with distinct coordinates and the Varshamov-Tenengolts codes
• Distinct solution to a linear congruence
• On the number of solutions of a restricted linear congruence
• On a class of enumeration problems in additive arithmetics
• Coprime solutions to \(ax\equiv b \pmod n\)
• Deletion correcting codes meet the Littlewood-Offord problem
• On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes
• A formula for the number of solutions of a restricted linear congruence
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• Counting subrings of the ring \(\mathbb Z_m \times \mathbb Z_n\)
• Linear congruences with ratios
• Proofs, generalizations and analogs of Menon's identity: a survey

This page was built for publication: Restricted linear congruences

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