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

Namboothiri, K. Vishnu

Mathematica Bohemica, Tome 146 (2021) no. 1, pp. 47-54.

Résumé

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).

Détail

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