Question about counting within a congruence

Question

Say I have quantity $z$ times $(z-1)$ and I know that $x$ divides it. For how many values of $z$ is this true?

Answer 1

It is simpler to allow $z=0$. We can always throw it away later.

Suppose that $x\gt 1$ has prime power factorization $$x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}.$$ where as usual the $p_i$ are distinct.

Our modified problem is equivalent to finding the number of solutions of the systems of congruences of the shape $z\equiv \epsilon_i \pmod{p_i^{a_i}}$, where for any $i$ we have $\epsilon_i=0$ or $\epsilon_i=1$. For the only solutions of the congruence $z(z-1)\equiv 0\pmod{p_1^{a_i}}$ are $z\equiv 0\pmod{p_i^{a_i}}$ and $z\equiv 1\pmod{p_i^{a_i}}$.

Note that any such system has a unique solution $z$ modulo $x$, by the Chinese Remainder Theorem, and that $z(z-1)\equiv 0\pmod{x}$, that is, $x$ divides $z(z-1)$.

There are $2^k$ such systems, since for each $i$ we have $2$ choices, $\epsilon_i=0$ or $\epsilon_i=1$. It follows that there are $2^k$ solutions $x$, $2^k-1$ if we do not allow $z=0$.

Remark: Previous versions of the answer, and possibly even this one, had "typos" caused by the unusual letters $x$ and $z$. It would be easier if the modulus were called $m$ instead of $x$.