Restricted linear congruences

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\equiv b(\mathrm{mod}n)$, with $\gcd (x_i,n)=t_i$ ($1\le i\le k$), where $a_1,t_1,\dots ,a_k,t_k,b,n$ ($n\ge 1$) 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$ $(1\le i\le k)$. Since then, this problem has been studied, in several other special cases, in many papers; in particular, Jacobson and Williams [{\it Duke Math. J.} {\bf 39} (1972), 521--527] gave a nice explicit formula for the number of such solutions when $(a_1,\dots ,a_k)=t_i=1$ $(1\le i\le k)$. 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.

Journal of Number Theory, to appear

References in corpus (4)

• Adding generators in cyclic groups
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• MMH* with arbitrary modulus is always almost-universal
• On a restricted linear congruence

Cited by in corpus (11)

• Explicit Formulas for the Weight Enumerators of Some Classes of Deletion Correcting Codes
• MMH* with arbitrary modulus is always almost-universal
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• On an almost-universal hash function family with applications to authentication and secrecy codes
• Unweighted linear congruences with distinct coordinates and the Varshamov--Tenengolts codes
• On a restricted linear congruence
• On the number of solutions of a restricted linear congruence
• Proofs, generalizations and analogs of Menon's identity: a survey
• On solving a restricted linear congruence using generalized Ramanujan sums
• A generalization of Schönemann's theorem via a graph theoretic method
• Harer-Zagier generating functions, the Redfield-Polya cycle index and Cohen semilinear congruences