# Occurrences of a residue when reducing the multiplication table mod $a$.

Consider the following diagram of numbers.

$$\begin{pmatrix}1 & 2 & 3 & 4 &.... & a \\ 2 & 4 & 6 & 8 & .... &2a \\ 3 & 6 & 9 & 12 & .... & 3a\\4 & 8 & 12 & 16 & .... & 4a\\.&.&.&.&.&.\\.&.&.&.&.&. \\a&2a&3a&4a&....&a^2\end{pmatrix}$$

For a given integer b, how can I figure out how many entries k in the matrix satisfy $k\equiv b \pmod a$?

-
Hint: If $k$ and $a$ are relatively prime, how many solutions are there to the equation $kx \equiv b \bmod a$? What if $k$ and $a$ share common factors? –  user7530 Dec 29 '12 at 3:12
gcd(k,a) solutions –  Ethan Dec 29 '12 at 3:29
Careful there slugger. You need something else. –  peoplepower Dec 29 '12 at 3:32
You changed my title to somthing so scary I wouldn't even look at it –  Ethan Dec 29 '12 at 9:40
Your previous title was so unspecific I wouldn't even look at it. –  joriki Dec 29 '12 at 9:43

Row $k$ with $\gcd(k,a)=d$ contains $d$ solutions if $d\mid b$ and none otherwise. Thus you're looking for

\begin{align} \sum_{d\mid b}\sum_{\gcd(k,a)=d}d&=\sum_{d\mid\gcd(b,a)}d\sum_{\gcd(k,a)=d}1\\ &= \sum_{d\mid\gcd(b,a)}d\,\phi(a/d)\;. \end{align}

Let $a=p_1^{k_1}\cdots p_n^{k_n}$ and $\gcd(b,a)=p_1^{s_1}\cdots p_n^{s_n}$; then this is

\begin{align} \sum_{r_1=0}^{s_1}\cdots\sum_{r_n=0}^{s_n}p_1^{r_1}\cdots p_n^{r_n}\phi\left(p_1^{k_1-r_1}\cdots p_n^{k_n-r_n}\right)\;. \end{align}

Since $\phi$ is multiplicative, this is

$$\prod_{i=1}^n\sum_{r_i=0}^{s_i}p_i^{r_i}\phi\left(p_i^{k_i-r_i}\right)\;.$$

Each summand is $p_i^{k_i}-p_i^{k_i-1}$ for $r_i\lt k_i$ and $p_i^{k_i}$ for $r_i=k_i$, so the result is

\begin{align} \prod_{i=1}^n\left((s_i+1)\left(p_i^{k_i}-p_i^{k_i-1}\right)+\delta_{s_ik_i}p_i^{k_i-1}\right) &= \prod_{i=1}^np_i^{k_i}\left((s_i+1)\left(1-p_i^{-1}\right)+\delta_{s_ik_i}p_i^{-1}\right) \\ &= a\prod_{i=1}^n\left((s_i+1)\left(1-p_i^{-1}\right)+\delta_{s_ik_i}p_i^{-1}\right)\;. \end{align}

-
Appreciate the help, I don't understand the notation, what are the delta symbols at the end, and does $k_n$ denote the powers of those primes? –  Ethan Dec 29 '12 at 20:33