Note that powers of 10:  1, 10, 100, 1000, 10000, 100000, ...

when converted to mod 13 go through a cycle of period 6:

[1,10,9,12,3,4], which mod 13 is equivalent to [1,-3,-4,-1,3,4]

Curiously, mod(n,13) = -mod(1000n,13)

Another equivalent  list of 6 factors is: [1,10,100,-1,-10,-100] and it is this fact that explains why one of the known divisibility tests for 13 works.

ALGORITHM:  

1. Convert integer (N) to list of single digits of type integer

2. Proceed stepwise through list in reverse order (right to left)

3. At each step multiply digit by multiplier factor and keep running sum

4. The final running sum is divisible by 13 if and only if N is div by 13

5. The multiplier factors are recycled: [1,-3,-4,-1,3,4]

6. This algorithm is independent of the number of digits; it does require a large list but does not require any large number math.  Because the multiplier factors are small and balanced between negative and positive, the running sum will tend to stay small.

7. This particular function returns both a True/False and the Remainder

        

----------  Python code  ----------

def div13(n):

    """ n can be integer or a list of individual base 10 digits

    output is a 2 member list, the first element is a boolean depending on if n is divisible by 13 or not  and the second is the remainder

        """

    if type(n) == int:

        n = [int(a) for a in str(n)]

    if type(n) != list:

        print('input must be integer or a list of single digit integers')

        return None

    for i in n:

        if not (type(i) == int and i >= 0 and i <= 9):

            print('input must be integer or a list of single digit integers')

            return None

    

    temp = 0

    factors = [1,-3,-4,-1,3,4]

    for i,c in enumerate(reversed(n)):

        multiplier = factors[i%6]

        temp += multiplier * int(c)

    if temp%13 == 0:

        return [True, temp%13]

    else:

        return [False, temp%13]