2
$\begingroup$

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

  • 1
    Your previous title was so unspecific I wouldn't even look at it.2012-12-29

1 Answers 1

1

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

  • 0
    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?2012-12-29