## A sum involving mod(n) arithmetic

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Hi there, I have been studying the following set (in order to investigate the average of products of Ramanujan sums with some weights):

$$A=\lbrace (n,m) \in \mathbb{Z}/q\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} \mid \text{ }nm\equiv a \mod{q},\text{ } n \equiv 1 \mod{d_{1}}, \text{ } m \equiv 1 \mod{d_{2}} \rbrace$$

where $q$ is any positive integer, $d_{1}$ and $d_{2}$ are proper divisors of $q$ and $(a,q)=1$.

For the case $a=1$, using a bit algebra I have deduced the elementary formula

$$\sum_{\substack{n_{1}n_{2}\equiv 1\mod{q}, \\ n_{1} \equiv 1 \mod{d_{1}}, \\ n_{2} \equiv 1 \mod{d_{2}}}}=\frac{\phi(q)}{\mathrm{lcm}(\phi(d_{1}),\phi(d_{2}))}.$$

Is it possible to derive a formula for $|A|$?

-

4
The sum of WHAT, and what exactly is your question? – Seva Feb 11 at 16:17
Actually we want to count a set, which we abbreviate by summing 1s and putting constraints as indexes. – Egeselazuzyan Feb 11 at 17:49
There are no 1s in your question. And what is $k$ in the right hand side of the second formula? – Max Alekseyev Feb 11 at 17:53

2
Then the WHAT is 1, and you need to put it in the expression. Gerhard "Or Suffer The Community Wrath" Paseman, 2013.02.11 – Gerhard Paseman Feb 11 at 17:55
Question also posted to m.se, math.stackexchange.com/questions/299752/… – Gerry Myerson Feb 12 at 0:05

## 1 Answer

I believe the formula $|A|=\frac{\varphi(q)}{\mathrm{lcm}(\varphi(d_1),\varphi(d_2))}$ is not quite correct. In particular, for $q=15$, $d_1 = 3$, $d_2=5$, $a=1$, this formula gives $|A|=2$, while, in fact, $A = \{ (1,1) \}$ with $|A|=1$. Below I derive a correct formula.

First, it is clear that if $a\not\equiv1\pmod{\gcd(d_1,d_2)}$, then $|A|=0$. For the rest assume that $a\equiv1\pmod{\gcd(d_1,d_2)}$.

Let $p$ be a prime dividing $q$ and $t=\nu_p(q)>0$ (i.e., $t$ is the valuation of $q$ w.r.t. $p$) and $s_1 = \nu_p(d_1)$, $s_2 = \nu_p(d_2)$. It is easy to see that the number of elements modulo $p^t$ in $A$ is indeed $$\frac{\varphi(p^t)}{\mathrm{lcm}(\varphi(p^{s_1}),\varphi(p^{s_2}))} = \begin{cases} (p-1)p^{t-1},& \text{if}\ s_1=s_2=0\\ p^{t-\max\{s_1,s_2\}},&\text{otherwise}. \end{cases}$$

Now, for any $a$ such that $\gcd(a,q)=1$ and $a\equiv1\pmod{\gcd(d_1,d_2)}$, we have (thanks to CRT) $$|A| = \prod_{p|q} \frac{\varphi(p^{\nu_p(q)})}{\mathrm{lcm}(\varphi(p^{\nu_p(d_1)}),\varphi(p^{\nu_p(d_2)}))} = \frac{\varphi(q)}{\prod_{p|q} \mathrm{lcm}(\varphi(p^{\nu_p(d_1)}),\varphi(p^{\nu_p(d_2)}))}.$$ Notice that this product does not collapse into $\frac{\varphi(q)}{\mathrm{lcm}(\varphi(d_1),\varphi(d_2))}$.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 33, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9233505725860596, "perplexity_flag": "head"}