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

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 -