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

  • 0
    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?2012-12-29
  • 0
    gcd(k,a) solutions2012-12-29
  • 1
    Careful there slugger. You need something else.2012-12-29
  • 0
    You changed my title to somthing so scary I wouldn't even look at it2012-12-29
  • 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