This problem is one based on number theory. After solving this problem, I found it very beautiful in mathematics.

Here are some facts that holds for all cases. Proof is ignored for each fact. If you are interest on it, just try to prove that using number theory.

Fact.1 For any (a, b), where a = 1 and GCD(b, m) = 1, it is always the solution.
(The most trivial fact...)
Let's denote the set: B = {b | GCD(b, m) = 1}.

Fact.2 For any a0 != 1, if there exists some b0 such that (a0, b0) is a solution, then:
(1) b0 is an element of B, and
(2) for all b in B, (a0, b) is a solution.
(Hence, to check some a0 for validity, you need only to check (a, 1). But it will still cost you O(N) time for a single a0, and O(N^2) for a0 in the range [0, m - 1].)

Fact.3 For any m, factorize it into product of primes. There exists some solution (a0, 1), where a0 != 1, iff one of the power of primes in m is larger than 1 (at least 2). Specially, if the prime is 2, the power must be at least 3.
e.g. for this fact:
4 = 2^2 -- No solution for a != 1.
8 = 2^3 -- Exists solution for a != 1 (a = 5).
15 = 3 * 5 -- No solution for a != 1.
20 = 2^2 * 5 -- No solution for a != 1.
18 = 2 * 3^2 -- Exists solution for a != 1 (a = 7, 13).

Fact.4 For any m, denote A = {a | there exists solution for a}. Then all the numbers in A form an arithmetic sequence. The common difference of the sequence, d, equals to m, divided by all the redundant power of the factorized primes. Here, redundant power is 1 for those primes p (p != 2) with power at least 2, and is 2 for prime 2 with power at least 3. For those primes without enough power, the redundant power is 0.
e.g. for this fact:
8 = 2^3 -- d = 2^1 = 2.
18 = 2 * 3^2 -- d = 2 * 3 = 6.
100 = 2^2 * 3^2 -- d = 2^2 * 5 = 20.
72 = 2^3 * 3^2 -- d = 2^2 * 3 = 12.

Obviously, Fact.3 and Fact.4 could be combined together. For those m without solutions that a != 1, the common difference, d, for m, is m itself.

Now, the problem could be solved quickly. The only work remaining is to factorize m, which is very easy in practise. However, proving these facts in number theory could be more interesting than solving this problem itself.

Good luck.