Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
4  
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
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 '13 at 17:55
    
Question also posted to m.se, math.stackexchange.com/questions/299752/… –  Gerry Myerson Feb 12 '13 at 0:05

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.