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

Mathematica Bohemica (2021)

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

top Access to full text Full (PDF)

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

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.