A sum involving mod(n) arithmetic

Question

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

Answer 1

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