Linear congruences and a conjecture of Bibak

Babu, Chinnakonda Gnanamoorthy Karthick ; Bera, Ranjan ; Sury, Balasubramanian

Czechoslovak Mathematical Journal, Tome 74 (2024) no. 4, pp. 1185-1206

Abstract (VO)

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.

Détail

DOI : 10.21136/CMJ.2024.0151-24

Classification : 11A25, 11D79, 11P83, 11T24, 11T55
Keywords: system of congruence; restricted linear congruence; Ramanujan sum; discrete Fourier transform

Bibliographie

[1] Bibak, K.: Order-restricted linear congruences. Discrete Math. 343 (2020), Article ID 111690, 4 pages. | DOI | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[5] Bibak, K., Kapron, B. M., Srinivasan, V., Tauraso, R., Tóth, L.: Restricted linear congruences. J. Number Theory 171 (2017), 128-144. | DOI | MR | JFM

[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 | MR | JFM

[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

[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 | MR | JFM

[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 | MR | JFM

[11] Cohen, E.: A class of arithmetical functions. Proc. Natl. Acad. Sci. USA 41 (1955), 939-944. | DOI | MR | JFM

[12] Dickson, L. E.: History of the Theory of Numbers. II. Diophantine Analysis. Chelsea Publishing, New York (1966). | MR | JFM

[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 | MR | JFM

[14] Grynkiewicz, D. J., Philipp, A., Ponomarenko, V.: Arithmetic-progression-weighted subsequence sums. Isr. J. Math. 193 (2013), 359-398. | DOI | MR | JFM

[15] Gupta, H.: Partitions - a survey. J. Res. Natl. Bur. Stand., Sect. B 74 (1970), 1-29. | DOI | MR | JFM

[16] Hull, R.: The numbers of solutions of congruences involving only $k$th powers. Trans. Am. Math. Soc. 34 (1932), 908-937. | DOI | MR | JFM

[17] Ireland, K., Rosen, M.: A Classical Introduction to Modern Number Theory. Graduate Texts in Mathematics 84. Springer, New York (1990). | DOI | MR | JFM

[18] Jacobson, D., Williams, K. S.: On the number of distinguished representations of a group element. Duke Math. J. 39 (1972), 521-527. | DOI | MR | JFM

[19] Lehmer, D. N.: Certain theorems in the theory of quadratic residues. Am. Math. Mon. 20 (1913), 148-157 \99999JFM99999 44.0248.09. | DOI | MR

[20] Li, J., Wan, D.: On the subset sum problem over finite fields. Finite Fields Appl. 14 (2008), 911-929. | DOI | MR | JFM

[21] Li, J., Wan, D.: Counting subset sums of finite Abelian groups. J. Comb. Theory, Ser. A 119 (2012), 170-182. | DOI | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[27] Riordan, J.: Enumerations for permutations in difference form. Proc. Am. Math. Soc. 13 (1962), 107-110. | DOI | MR | JFM

[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 | MR | JFM

[29] Stangl, W. D.: Counting squares in $\Bbb{Z}_n$. Math. Mag. 69 (1996), 285-289. | DOI | MR | JFM

[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 | JFM