Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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
1  
Your previous title was so unspecific I wouldn't even look at it. –  joriki Dec 29 '12 at 9:43
add comment

1 Answer

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.