How many products of two single digits $x,y$ end in a specific digit $n$ in a given base $b$?

Question

While one can use brute force (i.e. counting a multiplication table) to see that e.g. in base ten there are 27 combinations yielding zero ($0\cdot n, 2n\cdot 5$ and the other way around, counting $0^2$ only once), 4 for 1, 12 for 2 and so on,

is there a general formula for the amount $\phi_n(b)$ of products $n\equiv x\cdot y \pmod b$ with $n,x,y\in\{0,1,2,...,b-1\}$?

---

To add some numbers (from http://oeis.org/A095026) $\newcommand{\p}{\color{green}}$:

$$\begin{array}{r|rrrrrrrrrrr} b\backslash n& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& \\\hline 1& 1& \\ \p2& \p3& \p1& \\ \p3& \p5& \p2& \p2& \\ 4& 8& 2& 4& 2& \\ \p5& \p9& \p4& \p4& \p4& \p4& \\ 6& 15& 2& 6& 5& 6& 2& \\ \p7&\p{13}& \p6& \p6& \p6& \p6& \p6& \p6& \\ 8& 20& 4& 8& 4& 12& 4& 8& 4& \\ 9& 21& 6& 6& 12& 6& 6& 12& 6& 6& \\ 10& 27& 4& 12& 4& 12& 9& 12& 4& 12& 4& \\\p{11}&\p{21}&\p{10}&\p{10}&\p{10}&\p{10}&\p{10}&\p{10}&\p{10}&\p{10}&\p{10}&\p{10}& \\ 12& 40& 4& 8& 10& 16& 4& 20& 4& 16& 10& 8& 4 \\\p{13}&\p{25}&\p{12}&\p{12}&\p{12}&\p{12}&\p{12}&\p{12}&\p{12}&\p{12}&\p{12}&\p{12}&\p{12}&\p{12} \end{array}$$

As Thomas Andrews commented, investigating upon prime bases and powers thereof looks like a good starting point, as the table shows $N(0)=2p-1$ and $N(n\neq0)=p-1$ for primes $p\le13$, while prime powers (4 and 9) show some periodic behaviour and general composites get more complicated.

Answer 1

Define $\phi_n(b)$ to be the number of distinct solutions, modulo $b$, to $xy\equiv n\pmod b$. This notation is justified because $\phi_1(b)=\phi(b)$, the usual Euler totient function.

By Chinese Remainder theorem, we see that if $b=b_1b_2$, with $(b_1,b_2)=1$, then:

$$\phi_n(b)=\phi_n(b_1)\phi_n(b_2)$$

So $\phi_n$ is a multiplicative function.

If $(n,b)=1$, we can quickly see that $\phi_n(b)=\phi(b)$. Also, if we have $(m,b)=1$ then $\phi_{mn}(b)=\phi_n(b)$.

This means that we only need to solve $\phi_{p^i}(p^k)$ for $1\leq i\leq k$.

I can prove that $$\phi_{p^i}(p^k)=(i+1)\phi(p^k), \,0\leq i<k$$

The case $i=k$ is messier. It is easy to show that $\phi_p(p)=2p-1$. Experimental data seems to indicate that we have:

$$\phi_{p^k}(p^k) = \phi(p^k)(k+1) + p^{k-1}$$ I haven't had time to try to prove this.

Answer 2

Ok, here's an approach that hopefully complements Thomas Andrews' one:

Observing the sequence $k\cdot l \bmod b$ for fixed $k,b$, i.e. $$0, k, 2k\bmod b, 3k\bmod b, ..., (b-1)k\bmod b$$ notice that it has a period of $b/\gcd(k,b)$ (since $b|(bk/(b,k))$) and therefore repeats the digits $$0,k,2k\bmod b,...,\left(\frac{b}{(k,b)}-1\right)\cdot k\bmod b$$ $(k,b)$ times, while the other digits do not occur for that $k$. So by defining $$\mu_{k,n}(b)=\begin{cases}1 & (k,b)\mid n \\ 0 & \text{else} \end{cases}$$ to denote whether there exists an $l<b$ for which $k\cdot l\equiv n\pmod b$, we therefore obtain $$\boxed{\begin{align} \phi_n(b) &= \sum\limits_{k=1}^b \mu_{k,n}(b)\cdot(k,b) \\ &\stackrel{\text{T.A.}}= \sum_{d\mid (n,b)} d\cdot \phi\left(\frac bd\right) \end{align}}$$ where the latter form is courtesy of Thomas Andrews. As he also showed, this function is multiplicative, i.e. $$\phi_n(b_1\cdot b_2) = \phi_n(b_1)\cdot\phi_n(b_2)\quad\text{for }(b_1,b_2)=1.$$

Note how this especially yields the mentioned identities

$$\begin{align}\phi_1(b) &= \sum\limits_{k=1 \\ (k,b)=1}^b 1 = \text{"the" } \phi(b), \\\phi_0(b) &= \sum\limits_{k=1}^b (k,b),\quad(\mu_{k,0}\equiv1\text{ since anything divides zero})\end{align}$$ i.e. $\phi_0(b)$ is Pillai's arithmetical function while $\phi_1(b)$ is Euler's totient function.

For prime bases $p$, one obtains aforementioned $$\begin{align} \phi_0(p) &= \sum_{k=1}^p\underbrace{(k,p)}_{=\begin{cases}1 & k\neq p\\p & k=p\end{cases}} = 2p-1, \\\phi_{n\neq0}(p) &= \phi(p) = p-1 \end{align}$$

For prime powers refer to Thomas Andrews' answer.