# A formula for the number of solutions of a restricted linear congruence

Mathematica Bohemica (2021)

• Issue: 1, page 47-54
• ISSN: 0862-7959

top

## Abstract

top
Consider the linear congruence equation ${x}_{1}+...+{x}_{k}\equiv b\phantom{\rule{4.44443pt}{0ex}}\left(mod\phantom{\rule{0.277778em}{0ex}}{n}^{s}\right)$ for $b\in ℤ$, $n,s\in ℕ$. Let ${\left(a,b\right)}_{s}$ denote the generalized gcd of $a$ and $b$ which is the largest ${l}^{s}$ with $l\in ℕ$ dividing $a$ and $b$ simultaneously. Let ${d}_{1},...,{d}_{\tau \left(n\right)}$ be all positive divisors of $n$. For each ${d}_{j}\mid n$, define ${𝒞}_{j,s}\left(n\right)=\left\{1\le x\le {n}^{s}:{\left(x,{n}^{s}\right)}_{s}={d}_{j}^{s}\right\}$. 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 _{d\mid n}{c}_{d,s}\left(b\right)\prod _{j=1}^{\tau \left(n\right)}{\left({c}_{n/{d}_{j},s}\left(\frac{{n}^{s}}{{d}^{s}}\right)\right)}^{{g}_{j}}$ where ${g}_{j}=|\left\{{x}_{1},...,{x}_{k}\right\}\cap {𝒞}_{j,s}\left(n\right)|$ for $j=1,...,\tau \left(n\right)$ and ${c}_{d,s}$ denotes the generalized Ramanujan sum defined by E. Cohen (1955).

## How to cite

top

Namboothiri, K. Vishnu. "A formula for the number of solutions of a restricted linear congruence." Mathematica Bohemica (2021): 47-54. <http://eudml.org/doc/297195>.

@article{Namboothiri2021,
abstract = {Consider the linear congruence equation $x_1+\ldots +x_k \equiv b\hspace\{4.44443pt\}(\@mod \; 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) = \lbrace 1\le x\le n^s\colon (x,n^s)_s = d^s_j\rbrace$. 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 = |\lbrace x_1,\ldots , x_k\rbrace \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).},
author = {Namboothiri, K. Vishnu},
journal = {Mathematica Bohemica},
keywords = {restricted linear congruence; generalized gcd; generalized Ramanujan sum; finite Fourier transform},
language = {eng},
number = {1},
pages = {47-54},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A formula for the number of solutions of a restricted linear congruence},
url = {http://eudml.org/doc/297195},
year = {2021},
}

TY - JOUR
AU - Namboothiri, K. Vishnu
TI - A formula for the number of solutions of a restricted linear congruence
JO - Mathematica Bohemica
PY - 2021
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
IS - 1
SP - 47
EP - 54
AB - Consider the linear congruence equation $x_1+\ldots +x_k \equiv b\hspace{4.44443pt}(\@mod \; 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) = \lbrace 1\le x\le n^s\colon (x,n^s)_s = d^s_j\rbrace$. 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 = |\lbrace x_1,\ldots , x_k\rbrace \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).
LA - eng
KW - restricted linear congruence; generalized gcd; generalized Ramanujan sum; finite Fourier transform
UR - http://eudml.org/doc/297195
ER -

## References

top
1. Apostol, T. M., 10.1007/978-1-4757-5579-4, Undergraduate Texts in Mathematics. Springer, New York (1976). (1976) Zbl0335.10001MR0434929DOI10.1007/978-1-4757-5579-4
2. Bibak, K., Kapron, B. M., Srinivasan, V., 10.1142/S179304211650130X, Int. J. Number Theory 12 (2016), 2167-2171. (2016) Zbl1353.11066MR3562020DOI10.1142/S179304211650130X
3. Bibak, K., Kapron, B. M., Srinivasan, V., Tauraso, R., Tóth, L., 10.1016/j.jnt.2016.07.018, J. Number Theory 171 (2017), 128-144. (2017) Zbl1353.11067MR3556678DOI10.1016/j.jnt.2016.07.018
4. Bibak, K., Kapron, B. M., Srinivasan, V., Tóth, L., 10.1142/S0129054118500089, Int. J. Found. Comput. Sci. (2018), 357-375. (2018) Zbl1391.94730MR3799234DOI10.1142/S0129054118500089
5. Cohen, E., 10.1215/S0012-7094-49-01607-5, Duke Math. J. 16 (1949), 85-90. (1949) Zbl0034.02104MR0027781DOI10.1215/S0012-7094-49-01607-5
6. Cohen, E., 10.1215/S0012-7094-55-02260-2, Duke Math. J. 22 (1955), 543-550. (1955) Zbl0067.02205MR0072163DOI10.1215/S0012-7094-55-02260-2
7. Cohen, E., 10.1073/pnas.41.11.939, Proc. Natl. Acad. Sci. USA 41 (1955), 939-944. (1955) Zbl0066.29203MR0075230DOI10.1073/pnas.41.11.939
8. Dixon, J. D., 10.4153/CMB-1960-013-5, Can. Math. Bull. 3 (1960), 121-126. (1960) Zbl0093.25902MR0123519DOI10.4153/CMB-1960-013-5
9. Lehmer, D. N., 10.2307/2972413, Am. Math. Monthly 20 (1913), 151-157 9999JFM99999 44.0248.09. (1913) MR1517830DOI10.2307/2972413
10. Liskovets, V. A., 10.1515/INTEG.2010.012, Integers 10 (2010), 155-177. (2010) Zbl1230.11007MR2601316DOI10.1515/INTEG.2010.012
11. McCarthy, P. J., 10.1515/crll.1960.203.55, J. Reine Angew. Math. 203 (1960), 55-63. (1960) Zbl0101.28002MR0111712DOI10.1515/crll.1960.203.55
12. Montgomery, H. L., Vaughan, R. C., 10.1017/cbo9780511618314, Cambridge Studies in Advanced Mathematics 97. Cambridge University Press, Cambridge (2007). (2007) Zbl1142.11001MR2378655DOI10.1017/cbo9780511618314
13. Namboothiri, K. V., 10.1016/j.jnt.2018.01.013, J. Number Theory 188 (2018), 324-334. (2018) Zbl06855850MR3778637DOI10.1016/j.jnt.2018.01.013
14. Nicol, C. A., Vandiver, H. S., 10.1073/pnas.40.9.825, Proc. Natl. Acad. Sci. USA 40 (1954), 825-835. (1954) Zbl0056.04001MR0063399DOI10.1073/pnas.40.9.825
15. Rademacher, H., Aufgabe 30, Jahresber. Dtsch. Math.-Ver. 34 (1925), page 158 German. (1925)
16. Rademacher, H., Aufgabe 30. Lösung von A. Brauer, Jahresber. Dtsch. Math.-Ver. 35 (1926), 92-94 German 9999JFM99999 52.0139.03. (1926)
17. Sander, J. W., Sander, T., 10.1016/j.jnt.2012.08.021, J. Number Theory 133 (2013), 705-718. (2013) Zbl1353.11018MR2994382DOI10.1016/j.jnt.2012.08.021
18. Tóth, L., Counting solutions of quadratic congruences in several variables revisited, J. Integer Seq. 17 (2014), Article 14.11.6, 23 pages. (2014) Zbl1321.11041MR3291084

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.