Why it works: Suppose d = mn where m and n are relatively prime. If d divides a, then clearly m divides a and n divides a. Conversely, suppose that m and n each divide a. Then a = mr for some integer r. But if n divides mr, where m and n are relatively prime, one can consider the prime factorization of both sides and see that n must divide r; that is, r = nx for some integer x. So, a = m(nx) = (mn)x and thus mn divides a.
Running total: We now have divisibility tests for all the numbers from 2 to 102!