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