Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
restricted linear congruence; generalized gcd; generalized Ramanujan sum; finite Fourier transform
restricted linear congruence; generalized gcd; generalized Ramanujan sum; finite Fourier transform
Summary:
Consider the linear congruence equation $x_1+\ldots +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. (2016) 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 (1955).
References:
[1] Apostol, T. M.: Introduction to Analytic Number Theory. Undergraduate Texts in Mathematics. Springer, New York (1976). DOI 10.1007/978-1-4757-5579-4 | MR 0434929 | Zbl 0335.10001
[2] Bibak, K., Kapron, B. M., Srinivasan, V.: On a restricted linear congruence. Int. J. Number Theory 12 (2016), 2167-2171. DOI 10.1142/S179304211650130X | MR 3562020 | 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. DOI 10.1016/j.jnt.2016.07.018 | MR 3556678 | 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. DOI 10.1142/S0129054118500089 | MR 3799234 | Zbl 1391.94730
[5] Cohen, E.: An extension of Ramanujan's sum. Duke Math. J. 16 (1949), 85-90. DOI 10.1215/S0012-7094-49-01607-5 | MR 0027781 | Zbl 0034.02104
[6] Cohen, E.: An extension of Ramanujan's sum. II. Additive properties. Duke Math. J. 22 (1955), 543-550. DOI 10.1215/S0012-7094-55-02260-2 | MR 0072163 | Zbl 0067.02205
[7] Cohen, E.: A class of arithmetical functions. Proc. Natl. Acad. Sci. USA 41 (1955), 939-944. DOI 10.1073/pnas.41.11.939 | MR 0075230 | Zbl 0066.29203
[8] Dixon, J. D.: A finite analogue of the Goldbach problem. Can. Math. Bull. 3 (1960), 121-126. DOI 10.4153/CMB-1960-013-5 | MR 0123519 | 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. DOI 10.2307/2972413 | MR 1517830
[10] Liskovets, V. A.: A multivariate arithmetic function of combinatorial and topological significance. Integers 10 (2010), 155-177. DOI 10.1515/INTEG.2010.012 | MR 2601316 | Zbl 1230.11007
[11] McCarthy, P. J.: The generation of arithmetical identities. J. Reine Angew. Math. 203 (1960), 55-63. DOI 10.1515/crll.1960.203.55 | MR 0111712 | 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). DOI 10.1017/cbo9780511618314 | MR 2378655 | Zbl 1142.11001
[13] Namboothiri, K. V.: On the number of solutions of a restricted linear congruence. J. Number Theory 188 (2018), 324-334. DOI 10.1016/j.jnt.2018.01.013 | MR 3778637 | Zbl 06855850
[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. DOI 10.1073/pnas.40.9.825 | MR 0063399 | Zbl 0056.04001
[15] Rademacher, H.: Aufgabe 30. Jahresber. Dtsch. Math.-Ver. 34 (1925), page 158 German.
[16] Rademacher, H.: Aufgabe 30. Lösung von A. Brauer. Jahresber. Dtsch. Math.-Ver. 35 (1926), 92-94 German \99999JFM99999 52.0139.03.
[17] Sander, J. W., Sander, T.: Adding generators in cyclic groups. J. Number Theory 133 (2013), 705-718. DOI 10.1016/j.jnt.2012.08.021 | MR 2994382 | 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. MR 3291084 | Zbl 1321.11041
Search
Partner of
