A general way to determine whether two numbers are divisible is by using the Euclidean algorithm (which is fairly efficient (O((log a + log b)2 )) at determining the greatest common divisor) and checking if the result equals the smaller number.
This has been reformulated to only require subtraction and division by 2 (and iteration and powers of 2 (likely to be small powers)) as follows (the Binary GCD Algorithm):
Input values a and b to check.
0) Define auxiliary variable d = 0
1) While a and b are both even (easy to tell), divide both by 2 and increment d by 1.
2) While a is not equal to b
2.1) If a is even, then half it (a = a / 2)
2.2) Otherwise if b is even, then half it (b = b / 2)
2.3) Otherwise take their difference divided by two and set that as the value for the larger of a and b (so if a > b, then set a = (a - b) / 2). Their difference (and sum!) is guaranteed to be even because the preceding clauses imply that a and b are both odd.
3) Return a * 2d, the greatest common divisor (remember that the value of a has been modified by the algorithm).
4) Compare this result to the smaller of the input values of a and b (your numbers to check). If they are equal, your answer is "yes". Otherwise the greatest common divisor which you just found will be smaller than both a and b.
If the gcd is 1, that means the two numbers are coprime.