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

Namboothiri, K. Vishnu

Math. Bohem. 146, No. 1, 47-54 (2021).

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)].

Reviewer: László Tóth (Pécs)

MSC:

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

Keywords:

restricted linear congruence; generalized gcd; generalized Ramanujan sum; finite Fourier transform

Citations:

Zbl 1353.11066; Zbl 0034.02105

References:

[1]	Apostol, T. M., Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics. Springer, New York (1976) · Zbl 0335.10001 · doi:10.1007/978-1-4757-5579-4
[2]	Bibak, K.; Kapron, B. M.; Srinivasan, V., On a restricted linear congruence, Int. J. Number Theory 12 (2016), 2167-2171 · Zbl 1353.11066 · doi:10.1142/S179304211650130X
[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 · doi:10.1016/j.jnt.2016.07.018
[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 · doi:10.1142/S0129054118500089
[5]	Cohen, E., An extension of Ramanujan’s sum, Duke Math. J. 16 (1949), 85-90 · Zbl 0034.02104 · doi:10.1215/S0012-7094-49-01607-5
[6]	Cohen, E., An extension of Ramanujan’s sum. II. Additive properties, Duke Math. J. 22 (1955), 543-550 · Zbl 0067.02205 · doi:10.1215/S0012-7094-55-02260-2
[7]	Cohen, E., A class of arithmetical functions, Proc. Natl. Acad. Sci. USA 41 (1955), 939-944 · Zbl 0066.29203 · doi:10.1073/pnas.41.11.939
[8]	Dixon, J. D., A finite analogue of the Goldbach problem, Can. Math. Bull. 3 (1960), 121-126 · Zbl 0093.25902 · doi:10.4153/CMB-1960-013-5
[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 · doi:10.2307/2972413
[10]	Liskovets, V. A., A multivariate arithmetic function of combinatorial and topological significance, Integers 10 (2010), 155-177 · Zbl 1230.11007 · doi:10.1515/INTEG.2010.012
[11]	McCarthy, P. J., The generation of arithmetical identities, J. Reine Angew. Math. 203 (1960), 55-63 · Zbl 0101.28002 · doi:10.1515/crll.1960.203.55
[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 · doi:10.1017/cbo9780511618314
[13]	Namboothiri, K. V., On the number of solutions of a restricted linear congruence, J. Number Theory 188 (2018), 324-334 · Zbl 1440.11202 · doi:10.1016/j.jnt.2018.01.013
[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 · doi:10.1073/pnas.40.9.825
[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 · doi:10.1016/j.jnt.2012.08.021
[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