A formula for the number of solutions of a restricted linear congruence
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 positi...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute of Mathematics of the Czech Academy of Science
2021-04-01
|
| Series: | Mathematica Bohemica |
| Subjects: | |
| Online Access: | http://mb.math.cas.cz/full/146/1/mb146_1_4.pdf |
| _version_ | 1819158149741936640 |
|---|---|
| author | K. Vishnu Namboothiri |
| author_facet | K. Vishnu Namboothiri |
| author_sort | K. Vishnu Namboothiri |
| collection | DOAJ |
| description | 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 (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
\frac1{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). |
| first_indexed | 2024-12-22T16:20:04Z |
| format | Article |
| id | doaj.art-141c4dbb28ca482ba703e306e71fbbf6 |
| institution | Directory Open Access Journal |
| issn | 0862-7959 2464-7136 |
| language | English |
| last_indexed | 2024-12-22T16:20:04Z |
| publishDate | 2021-04-01 |
| publisher | Institute of Mathematics of the Czech Academy of Science |
| record_format | Article |
| series | Mathematica Bohemica |
| spelling | doaj.art-141c4dbb28ca482ba703e306e71fbbf62022-12-21T18:20:16ZengInstitute of Mathematics of the Czech Academy of ScienceMathematica Bohemica0862-79592464-71362021-04-011461475410.21136/MB.2020.0171-18MB.2020.0171-18A formula for the number of solutions of a restricted linear congruenceK. Vishnu NamboothiriConsider 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 (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 \frac1{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).http://mb.math.cas.cz/full/146/1/mb146_1_4.pdf restricted linear congruence generalized gcd generalized ramanujan sum finite fourier transform |
| spellingShingle | K. Vishnu Namboothiri A formula for the number of solutions of a restricted linear congruence Mathematica Bohemica restricted linear congruence generalized gcd generalized ramanujan sum finite fourier transform |
| title | A formula for the number of solutions of a restricted linear congruence |
| title_full | A formula for the number of solutions of a restricted linear congruence |
| title_fullStr | A formula for the number of solutions of a restricted linear congruence |
| title_full_unstemmed | A formula for the number of solutions of a restricted linear congruence |
| title_short | A formula for the number of solutions of a restricted linear congruence |
| title_sort | formula for the number of solutions of a restricted linear congruence |
| topic | restricted linear congruence generalized gcd generalized ramanujan sum finite fourier transform |
| url | http://mb.math.cas.cz/full/146/1/mb146_1_4.pdf |
| work_keys_str_mv | AT kvishnunamboothiri aformulaforthenumberofsolutionsofarestrictedlinearcongruence AT kvishnunamboothiri formulaforthenumberofsolutionsofarestrictedlinearcongruence |