| Title:
|
A formula for the number of solutions of a restricted linear congruence (English) |
| Author:
|
Namboothiri, K. Vishnu |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
146 |
| Issue:
|
1 |
| Year:
|
2021 |
| Pages:
|
47-54 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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). (English) |
| Keyword:
|
restricted linear congruence |
| Keyword:
|
generalized gcd |
| Keyword:
|
generalized Ramanujan sum |
| Keyword:
|
finite Fourier transform |
| MSC:
|
11A25 |
| MSC:
|
11D79 |
| MSC:
|
11L03 |
| MSC:
|
11P83 |
| MSC:
|
42A16 |
| idZBL:
|
07332741 |
| idMR:
|
MR4227310 |
| DOI:
|
10.21136/MB.2020.0171-18 |
| . |
| Date available:
|
2021-03-12T16:18:58Z |
| Last updated:
|
2021-04-19 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148746 |
| . |
| Reference:
|
[1] Apostol, T. M.: Introduction to Analytic Number Theory.Undergraduate Texts in Mathematics. Springer, New York (1976). Zbl 0335.10001, MR 0434929, 10.1007/978-1-4757-5579-4 |
| Reference:
|
[2] Bibak, K., Kapron, B. M., Srinivasan, V.: On a restricted linear congruence.Int. J. Number Theory 12 (2016), 2167-2171. Zbl 1353.11066, MR 3562020, 10.1142/S179304211650130X |
| Reference:
|
[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, MR 3556678, 10.1016/j.jnt.2016.07.018 |
| Reference:
|
[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, MR 3799234, 10.1142/S0129054118500089 |
| Reference:
|
[5] Cohen, E.: An extension of Ramanujan's sum.Duke Math. J. 16 (1949), 85-90. Zbl 0034.02104, MR 0027781, 10.1215/S0012-7094-49-01607-5 |
| Reference:
|
[6] Cohen, E.: An extension of Ramanujan's sum. II. Additive properties.Duke Math. J. 22 (1955), 543-550. Zbl 0067.02205, MR 0072163, 10.1215/S0012-7094-55-02260-2 |
| Reference:
|
[7] Cohen, E.: A class of arithmetical functions.Proc. Natl. Acad. Sci. USA 41 (1955), 939-944. Zbl 0066.29203, MR 0075230, 10.1073/pnas.41.11.939 |
| Reference:
|
[8] Dixon, J. D.: A finite analogue of the Goldbach problem.Can. Math. Bull. 3 (1960), 121-126. Zbl 0093.25902, MR 0123519, 10.4153/CMB-1960-013-5 |
| Reference:
|
[9] Lehmer, D. N.: Certain theorems in the theory of quadratic residues.Am. Math. Monthly 20 (1913), 151-157 \99999JFM99999 44.0248.09. MR 1517830, 10.2307/2972413 |
| Reference:
|
[10] Liskovets, V. A.: A multivariate arithmetic function of combinatorial and topological significance.Integers 10 (2010), 155-177. Zbl 1230.11007, MR 2601316, 10.1515/INTEG.2010.012 |
| Reference:
|
[11] McCarthy, P. J.: The generation of arithmetical identities.J. Reine Angew. Math. 203 (1960), 55-63. Zbl 0101.28002, MR 0111712, 10.1515/crll.1960.203.55 |
| Reference:
|
[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, MR 2378655, 10.1017/cbo9780511618314 |
| Reference:
|
[13] Namboothiri, K. V.: On the number of solutions of a restricted linear congruence.J. Number Theory 188 (2018), 324-334. Zbl 06855850, MR 3778637, 10.1016/j.jnt.2018.01.013 |
| Reference:
|
[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, MR 0063399, 10.1073/pnas.40.9.825 |
| Reference:
|
[15] Rademacher, H.: Aufgabe 30.Jahresber. Dtsch. Math.-Ver. 34 (1925), page 158 German. |
| Reference:
|
[16] Rademacher, H.: Aufgabe 30. Lösung von A. Brauer.Jahresber. Dtsch. Math.-Ver. 35 (1926), 92-94 German \99999JFM99999 52.0139.03. |
| Reference:
|
[17] Sander, J. W., Sander, T.: Adding generators in cyclic groups.J. Number Theory 133 (2013), 705-718. Zbl 1353.11018, MR 2994382, 10.1016/j.jnt.2012.08.021 |
| Reference:
|
[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, MR 3291084 |
| . |
