Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
system of congruence; restricted linear congruence; Ramanujan sum; discrete Fourier transform
system of congruence; restricted linear congruence; Ramanujan sum; discrete Fourier transform
Summary:
We address three questions posed by K. Bibak (2020), and generalize some results of K. Bibak, D. N. Lehmer and K. G. Ramanathan on solutions of linear congruences $\sum _{i=1}^k a_i x_i \equiv b \pmod n$. In particular, we obtain explicit expressions for the number of solutions, where $x_i$'s are squares modulo $n$. In addition, we obtain expressions for the number of solutions with order restrictions $x_1 \geq \cdots \geq x_k$ or with strict order restrictions $x_1> \cdots > x_k$ in some special cases. In these results, the expressions for the number of solutions involve Ramanujan sums and are obtained using their properties.
References:
[1] Bibak, K.: Order-restricted linear congruences. Discrete Math. 343 (2020), Article ID 111690, 4 pages. DOI 10.1016/j.disc.2019.111690 | MR 4040063 | Zbl 1447.11003
[2] Bibak, K., Kapron, B. M., Srinivasan, V.: Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT. Nucl. Phys., B 910 (2016), 712-723. DOI 10.1016/j.nuclphysb.2016.07.028 | MR 3535838 | Zbl 1345.81096
[3] Bibak, K., Kapron, B. M., Srinivasan, V.: Unweighted linear congruences with distinct coordinates and the Varshamov-Tenengolts codes. Des. Codes Cryptography 86 (2018), 1893-1904. DOI 10.1007/s10623-017-0428-3 | MR 3816205 | Zbl 1411.11035
[4] Bibak, K., Kapron, B. M., Srinivasan, V.: A generalization of Schönemann's theorem via a graph theoretic method. Discrete Math. 342 (2019), 3057-3061. DOI 10.1016/j.disc.2019.06.016 | MR 3996744 | Zbl 1420.11006
[5] 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
[6] 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. 29 (2018), 357-375. DOI 10.1142/S0129054118500089 | MR 3799234 | Zbl 1391.94730
[7] Bibak, K., Milenkovic, O.: Explicit formulas for the weight enumerators of some classes of deletion correcting codes. IEEE Trans. Commun. 67 (2019), 1809-1816. DOI 10.1109/TCOMM.2018.2886354
[8] Brauer, A.: Lösung der Aufgabe 30. Jahresber. Dtsch. Math.-Ver. 35 (1926), 92-94 German \99999JFM99999 52.0139.03.
[9] Calderón, C., Grau, J. M., Oller-Marcén, A. M., Tóth, L.: Counting invertible sums of squares modulo $n$ and a new generalization of Euler's totient function. Publ. Math. Debr. 87 (2015), 133-145. DOI 10.5486/PMD.2015.7098 | MR 3367916 | Zbl 1363.11004
[10] Cheng, Q., Murray, E.: On deciding deep holes of Reed-Solomon codes. Theory and Applications of Models of Computation Lecture Notes in Computer Science 4484. Springer, Berlin (2007), 296-305. DOI 10.1007/978-3-540-72504-6_27 | MR 2374319 | Zbl 1198.94189
[11] 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
[12] Dickson, L. E.: History of the Theory of Numbers. II. Diophantine Analysis. Chelsea Publishing, New York (1966). MR 0245500 | Zbl 1214.11002
[13] Grau, J. M., Oller-Marcén, A. M.: Fast computation of the number of solutions to $x_1^2 + \cdots +x_k^2 \equiv \lambda \pmod n$. J. Number Theory 200 (2019), 427-440. DOI 10.1016/j.jnt.2018.09.015 | MR 3944446 | Zbl 1418.11056
[14] Grynkiewicz, D. J., Philipp, A., Ponomarenko, V.: Arithmetic-progression-weighted subsequence sums. Isr. J. Math. 193 (2013), 359-398. DOI 10.1007/s11856-012-0119-8 | MR 3038556 | Zbl 1316.11010
[15] Gupta, H.: Partitions - a survey. J. Res. Natl. Bur. Stand., Sect. B 74 (1970), 1-29. DOI 10.6028/jres.074B.001 | MR 0271055 | Zbl 0203.30701
[16] Hull, R.: The numbers of solutions of congruences involving only $k$th powers. Trans. Am. Math. Soc. 34 (1932), 908-937. DOI 10.1090/S0002-9947-1932-1501668-0 | MR 1501668 | Zbl 0005.34501
[17] Ireland, K., Rosen, M.: A Classical Introduction to Modern Number Theory. Graduate Texts in Mathematics 84. Springer, New York (1990). DOI 10.1007/978-1-4757-2103-4 | MR 1070716 | Zbl 0712.11001
[18] Jacobson, D., Williams, K. S.: On the number of distinguished representations of a group element. Duke Math. J. 39 (1972), 521-527. DOI 10.1215/S0012-7094-72-03959-2 | MR 0302464 | Zbl 0248.20018
[19] Lehmer, D. N.: Certain theorems in the theory of quadratic residues. Am. Math. Mon. 20 (1913), 148-157 \99999JFM99999 44.0248.09. DOI 10.1080/00029890.1913.11997942 | MR 1517830
[20] Li, J., Wan, D.: On the subset sum problem over finite fields. Finite Fields Appl. 14 (2008), 911-929. DOI 10.1016/j.ffa.2008.05.003 | MR 2457537 | Zbl 1189.11058
[21] Li, J., Wan, D.: Counting subset sums of finite Abelian groups. J. Comb. Theory, Ser. A 119 (2012), 170-182. DOI 10.1016/j.jcta.2011.07.003 | MR 2844090 | Zbl 1229.05289
[22] Li, S., Ouyang, Y.: Counting the solutions of $\lambda_1 x^{k_1}_1 + \dots + \lambda_t x_t^{k_t} \equiv c$ mod $n$. J. Number Theory 187 (2018), 41-65. DOI 10.1016/j.jnt.2017.10.017 | MR 3766901 | Zbl 1430.11047
[23] 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
[24] 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
[25] Rademacher, H.: Über den Vektorenbereich eines konvexen ebenen Bereiches. Jahresber. Dtsch. Math.-Ver. 34 (1925), 64-79 German \99999JFM99999 51.0592.01.
[26] Ramanathan, K. G.: Some applications of Ramanujan's trigonometrical sum $C_m(n)$. Proc. Indian Acad. Sci., Sect. A 20 (1944), 62-69. DOI 10.1007/BF03048959 | MR 0011093 | Zbl 0063.06402
[27] Riordan, J.: Enumerations for permutations in difference form. Proc. Am. Math. Soc. 13 (1962), 107-110. DOI 10.1090/S0002-9939-1962-0148562-2 | MR 148562 | Zbl 0101.25106
[28] Schönemann, T.: Theorie der symmetrischen Functionen der Wurzeln einer Gleichung: Allgemeine Sätze über Congruenzen nebst einigen Anwendungen derselben. J. Reine Angew. Math. 19 (1839), 231-243 German. DOI 10.1515/crll.1839.19.231 | MR 1578210 | Zbl 019.0617cj
[29] Stangl, W. D.: Counting squares in $\Bbb{Z}_n$. Math. Mag. 69 (1996), 285-289. DOI 10.2307/2690536 | MR 1424442 | Zbl 1055.11500
[30] Tóth, L.: Counting solutions of quadratic congruences in several variables revisited. J. Integer Seq. 17 (2014), Article ID 14.11.6, 23 pages. MR 3291084 | Zbl 1321.11041
Search
Partner of
