Restricted linear congruences

DOI10.1016/J.JNT.2016.07.018zbMATH Open1353.11067arXiv1503.01806OpenAlexW2222139442MaRDI QIDQ331108FDOQ331108

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)

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.

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

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

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)

Cites Work

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

Cited In (23)

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

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)