# Counting the number of pairs $(a,b)$ such that $M \mid a+b$ with $a, b \in [N]$

We have been given first $N$ natural numbers and asked to count all distinct pairs $(a,b)$ where, $a < b$ such that $a+b$ is divisible by a given number $M$.

Example: Given $N = 4$, i.e. $\{1,2,3,4\}$

$M = 3$

Only possible pairs satisfying above conditions are $(1,2)$ and $(2,4)$.

Since, $1 < 2$ and $1+2 = 3$ is divisible by $M$.

$2 < 4$ and $2+4 = 6$ is divisible by $M$.

Values $M$ and $N$ can be very large (of the order of $10^9$), so simply generating pairs and dividing won't work.

My Idea: We need to generate pairs which sum up to multiple of $M$. Since, there is a strict ordering between $a$ and $b.$ (i.e. $a < b$) so, for generating any number $x$ which lies in the range $1$ to $N$ there are $\frac{(x-1)}{2}$ possible pairs. So, we need to sum up these values over multiples of $M$. But when the value of $x$ goes beyond $N$, this idea doesn't work (as number of pairs decrease).

I can't proceed any further. Kindly guide me if I am in a wrong direction. Or suggest any other alternative to efficiently calculate the same.

-
An exact duplicate of this question deleted by Qiaochu. Note that this is an open contest question, and someone seeking a full solution from outsiders might be considered cheating by that forum. – anon May 7 '12 at 15:05
@anon: Thanks for pointing that out! I thought at first that it was a duplicate as well, but couldn't find the earlier question, and I thought I was probably mistaken, as there are other similar but non-identical questions around. – Tara B May 7 '12 at 15:11
@anon Thanks for pointing that out. I think that is the best that can be done in these cases, since that allows each person to make there choice how to vote, answer, etc. Some members feel strongly that rules stemming from the source of the problem should not be our concern (whether it be tests, online contests, etc). – Bill Dubuque May 7 '12 at 15:13
I'm really not sure that deleting such questions is helpful. If the question had not been deleted, then I would have found it in my search for a duplicate, and then I would have known it was a contest question already before providing a partial answer. – Tara B May 7 '12 at 15:19

Hint: Think of it as finding pairs $(a,b)$ such that $a+b\equiv 0 \mod M$.
We can write $N = Mq + r$ for some integers $q\geq 0$ and $0\leq r < M$. Now partition the integers from $1$ to $N$ into equivalence classes modulo $M$. For $0\leq a\leq M-1$, let $S_a = \{i\in [N] \mid i\equiv a \mod M\}$. Then $S_a$ contains $q+1$ elements for $0\leq a\leq r$, and $q$ elements for $r+1\leq a\leq M-1$.
Now, given $a\in [N]$, how many choices for $b$ are there such that $a+b\equiv 0 \mod M$?
(I believe you mean $\bmod M$ in the definition of $S_a$.) And if $M>N$? – anon May 7 '12 at 15:10