Geodesic
A formula for the number of solutions of a restricted linear congruence
Mathematica Bohemica, Tome 146 (2021) no. 1, pp. 47-54
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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).
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).
DOI : 10.21136/MB.2020.0171-18
Classification : 11A25, 11D79, 11L03, 11P83, 42A16
Keywords: restricted linear congruence; generalized gcd; generalized Ramanujan sum; finite Fourier transform 
@article{10_21136_MB_2020_0171_18,
     author = {Namboothiri, K. Vishnu},
     title = {A formula for the number of solutions of a restricted linear congruence},
     journal = {Mathematica Bohemica},
     pages = {47--54},
     year = {2021},
     volume = {146},
     number = {1},
     doi = {10.21136/MB.2020.0171-18},
     mrnumber = {4227310},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2020.0171-18/}
}
TY  - JOUR
AU  - Namboothiri, K. Vishnu
TI  - A formula for the number of solutions of a restricted linear congruence
JO  - Mathematica Bohemica
PY  - 2021
SP  - 47
EP  - 54
VL  - 146
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2020.0171-18/
DO  - 10.21136/MB.2020.0171-18
LA  - en
ID  - 10_21136_MB_2020_0171_18
ER  - 
%0 Journal Article
%A Namboothiri, K. Vishnu
%T A formula for the number of solutions of a restricted linear congruence
%J Mathematica Bohemica
%D 2021
%P 47-54
%V 146
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2020.0171-18/
%R 10.21136/MB.2020.0171-18
%G en
%F 10_21136_MB_2020_0171_18
Namboothiri, K. Vishnu. A formula for the number of solutions of a restricted linear congruence. Mathematica Bohemica, Tome 146 (2021) no. 1, pp. 47-54. doi: 10.21136/MB.2020.0171-18

[1] Apostol, T. M.: Introduction to Analytic Number Theory. Undergraduate Texts in Mathematics. Springer, New York (1976). | DOI | MR | JFM

[2] Bibak, K., Kapron, B. M., Srinivasan, V.: On a restricted linear congruence. Int. J. Number Theory 12 (2016), 2167-2171. | DOI | MR | JFM

[3] 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

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

[5] Cohen, E.: An extension of Ramanujan's sum. Duke Math. J. 16 (1949), 85-90. | DOI | MR | JFM

[6] Cohen, E.: An extension of Ramanujan's sum. II. Additive properties. Duke Math. J. 22 (1955), 543-550. | DOI | MR | JFM

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

[8] Dixon, J. D.: A finite analogue of the Goldbach problem. Can. Math. Bull. 3 (1960), 121-126. | DOI | MR | JFM

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

[10] Liskovets, V. A.: A multivariate arithmetic function of combinatorial and topological significance. Integers 10 (2010), 155-177. | DOI | MR | JFM

[11] McCarthy, P. J.: The generation of arithmetical identities. J. Reine Angew. Math. 203 (1960), 55-63. | DOI | MR | JFM

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

[13] Namboothiri, K. V.: On the number of solutions of a restricted linear congruence. J. Number Theory 188 (2018), 324-334. | DOI | MR | JFM

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

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

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

Cité par Sources :