These algorithms all reduce the division problem into some fixed range. For instance, in the case of 3, we are able to reduce the divisibility of an arbitrary integer by 3 into the divisibility of a single digit number by 3. In the 13 case described in the article, we reduce the problem to a 3 digit number. The base case can then just be a lookup table.

As for how to generate the base table, recall that we say a divides n provided there exists some b such that ab = n. In this case we're talking about integers, although this is the definition for any ring.

Therefore, proving 3 divides 9 is as simple as noting that 3 * 3 = 9, and likewise we can prove 3 divides 6 by noting that 3 * 2 is 6.

Proving a lack of divisibilty is a little bit trickier. For this, you'll want to first prove the division algorithm which, in the case of the integers, says that for any two integers a and n, there exists unique integers b and r with abs(r) < abs(a) such that ab + r = n.

Given this, we can then note that, for instance, 7 = 3 * 2 + 1. Therefore 7 cannot be divisible by 3 as that would imply there exists some other integer b such that 7 = 3 * b + 0 contradicting that the integers from the division algorithm are unique.

You might then wonder: well, how do we know 3 * 2 is 6? Well, to stop these questions from recursing endlessly, we need to define the integers. One reasonable definition is "the initial element in the ring category" which gives us that the integers are a ring by definition. As such, we have axiomatically that there are integers 0 and 1, a commutative operation + with identity 0 that is closed under inverses, an associative operation * with identity 1, and that * distributes over +. If we then define 2 to be 1 + 1, 3 to be 1 + 1 + 1, and 6 to be 1 + 1 + 1 + 1 + 1 + 1, we can use distributivity to prove that 3 * 2 = 3 * (1 + 1) = (3 * 1) + (3 * 1) = 3 + 3 = 6.