A formula for the number of solutions of a restricted linear congruence. (English) Zbl 1513.11123

Author’s abstract: Consider the linear congruence equation \(x_1+\cdots+x_k\equiv b\pmod{n^s}\) for \(b\in\mathbb{Z}\), \(n,s\in\mathbb{N}\). Let \((a,b)_s\) denote the generalized gcd of \(a\) and \(b\) which is the largest \(l^s\) with \(l\in\mathbb{N}\) dividing \(a\) and \(b\) simultaneously. Let \(d_1,\ldots,d_{\tau(n)}\) be all positive divisors of \(n\). For each \(d_j\mid n\), define \(\mathcal{C}_{j,s}(n)=\{1\leq x\leq n^s\colon(x,n^s)_s=d^s_j\}\). K. Bibak et al. [Int. J. Number Theory 12, No. 8, 2167–2171 (2016; Zbl 1353.11066)] gave a formula using Ramanujan sums for the number of solutions of the above congruence equation with some gcd restrictions on \(x_i\). We generalize their result with generalized gcd restrictions on \(x_i\) and prove that for the above linear congruence, the number of solutions is \[\frac{1}{n^s}\sum\limits_{d\mid n}c_{d,s}(b)\prod\limits_{j=1}^{\tau(n)}\Bigl(c_{{n}/{d_j},s}\Bigl(\frac{n^s}{d^s}\Big)\Big)^{g_j}\] where \(g_j=|\{x_1,\ldots,x_k\}\cap\mathcal{C}_{j,s}(n)|\) for \(j=1,\ldots,\tau(n)\) and \(c_{d,s}\) denotes the generalized Ramanujan sum defined by E. Cohen [Duke Math. J. 16, 85–90 (1949; Zbl 0034.02105)].


11D79 Congruences in many variables
11P83 Partitions; congruences and congruential restrictions
11L03 Trigonometric and exponential sums (general theory)
11A25 Arithmetic functions; related numbers; inversion formulas
Full Text: DOI


[1] Apostol, T. M., Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics. Springer, New York (1976) · Zbl 0335.10001
[2] Bibak, K.; Kapron, B. M.; Srinivasan, V., On a restricted linear congruence, Int. J. Number Theory 12 (2016), 2167-2171 · Zbl 1353.11066
[3] Bibak, K.; Kapron, B. M.; Srinivasan, V.; Tauraso, R.; Tóth, L., Restricted linear congruences, J. Number Theory 171 (2017), 128-144 · Zbl 1353.11067
[4] Bibak, K.; Kapron, B. M.; Srinivasan, V.; Tóth, L., On an almost-universal hash function family with applications to authentication and secrecy codes, Int. J. Found. Comput. Sci. (2018), 357-375 · Zbl 1391.94730
[5] Cohen, E., An extension of Ramanujan’s sum, Duke Math. J. 16 (1949), 85-90 · Zbl 0034.02104
[6] Cohen, E., An extension of Ramanujan’s sum. II. Additive properties, Duke Math. J. 22 (1955), 543-550 · Zbl 0067.02205
[7] Cohen, E., A class of arithmetical functions, Proc. Natl. Acad. Sci. USA 41 (1955), 939-944 · Zbl 0066.29203
[8] Dixon, J. D., A finite analogue of the Goldbach problem, Can. Math. Bull. 3 (1960), 121-126 · Zbl 0093.25902
[9] Lehmer, D. N., Certain theorems in the theory of quadratic residues, Am. Math. Monthly 20 (1913), 151-157 \99999JFM99999 44.0248.09 · JFM 44.0248.09
[10] Liskovets, V. A., A multivariate arithmetic function of combinatorial and topological significance, Integers 10 (2010), 155-177 · Zbl 1230.11007
[11] McCarthy, P. J., The generation of arithmetical identities, J. Reine Angew. Math. 203 (1960), 55-63 · Zbl 0101.28002
[12] Montgomery, H. L.; Vaughan, R. C., Multiplicative Number Theory I: Classical Theory, Cambridge Studies in Advanced Mathematics 97. Cambridge University Press, Cambridge (2007) · Zbl 1142.11001
[13] Namboothiri, K. V., On the number of solutions of a restricted linear congruence, J. Number Theory 188 (2018), 324-334 · Zbl 1440.11202
[14] Nicol, C. A.; Vandiver, H. S., A Von Sterneck arithmetical function and restricted partitions with respect to a modulus, Proc. Natl. Acad. Sci. USA 40 (1954), 825-835 · Zbl 0056.04001
[15] Rademacher, H., Aufgabe 30, Jahresber. Dtsch. Math.-Ver. 34 (1925), page 158 German · JFM 52.0139.03
[16] Rademacher, H., Aufgabe 30. Lösung von A. Brauer, Jahresber. Dtsch. Math.-Ver. 35 (1926), 92-94 German \99999JFM99999 52.0139.03 · JFM 52.0139.03
[17] Sander, J. W.; Sander, T., Adding generators in cyclic groups, J. Number Theory 133 (2013), 705-718 · Zbl 1353.11018
[18] Tóth, L., Counting solutions of quadratic congruences in several variables revisited, J. Integer Seq. 17 (2014), Article 14.11.6, 23 pages · Zbl 1321.11041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.