# A sum involving mod(n) arithmetic

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|$?

• The sum of WHAT, and what exactly is your question? – Seva Feb 11 '13 at 16:17
• Actually we want to count a set, which we abbreviate by summing 1s and putting constraints as indexes. – Egeselazuzyan Feb 11 '13 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 '13 at 17:53
• 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 '13 at 17:55
• Question also posted to m.se, math.stackexchange.com/questions/299752/… – Gerry Myerson Feb 12 '13 at 0:05

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