I want to know how to compute this function:
$f : \mathbb{Z}_m \rightarrow \mathbb{N}$
$f(z) = |\{ (x, y) \in \mathbb{Z}_m^2 \mid xy \equiv z \}|$
$\begingroup$
$\endgroup$
15
-
$\begingroup$ What is the sum over in the last line? $\endgroup$– Igor RivinCommented Mar 24, 2017 at 23:26
-
$\begingroup$ Crap @IgorRivin I have to change that, its for a more general question but I wrote it in that form here... $\endgroup$– Samuel SchlesingerCommented Mar 24, 2017 at 23:30
-
1$\begingroup$ By the Chinese Remainder Theorem, it suffices to compute this function when $m$ is a prime power, in which case the task is easy. $\endgroup$– GH from MOCommented Mar 25, 2017 at 0:01
-
1$\begingroup$ If $z$ is coprime to $m$, you have $f(z) = \varphi(m)$. If not, it's more complicated. $\endgroup$– Robert IsraelCommented Mar 25, 2017 at 0:09
-
1$\begingroup$ Well, I told you what to do. Find out the (easy) answer when $m$ is a prime power, and then apply the Chinese Remainder Theorem. $\endgroup$– GH from MOCommented Mar 25, 2017 at 0:24
|
Show 10 more comments
1 Answer
$\begingroup$
$\endgroup$
3
Although this is by far not research level, I cannot keep myself from posting a very simple solution which somehow has not been mentioned in the comments above.
I use the basic fact that the congruence $ax\equiv b\pmod m$ has exactly $(a,m)$ solutions if $(a,m)\mid(b,m)$, and does not have any solutions otherwise. As a result, $$ f(z) = \sum_{y\in{\mathbb Z_m}\colon (y,m)\mid(z,m)} (y,m) = \sum_{d\mid(z,m)} d\varphi(m/d) $$ (the number of those $y\in\mathbb Z_m$ with $(y,m)=d$ is $\varphi(m/d)$). This can be further re-written, for instance, as $$ f(z) = m \sum_{d\mid(z,m)} \prod_{p\mid m/d} \Big(1-\frac1p\Big). $$
-
-
$\begingroup$ Thanks so much! Misplaced the question on here, didn't read the rules $\endgroup$ Commented Mar 28, 2017 at 2:10
-
$\begingroup$ Confused about the notation in the product at the end, could you or someone else perhaps clarify @Seva? Edit: figured it out, was associating the divides symbol before the division sign but it makes sense now. $\endgroup$ Commented Mar 28, 2017 at 2:32