Divisibility by 13 of a large number written in base 14

Question

I was given this question: suppose 123456789abcd is written in base 14. What is its remainder when divided by 13? I know the answer is zero but I had to do it using Wolframalpha. I'm wondering if there's a smart way to do it, instead of doing it by hand?

Answer 1

The number $$a_n B^n + a_{n-1} B^{n-1} + ... + a_0 B^0$$ and the number $$a_n + a_{n-1} + ... + a_0$$ have the same remainder when dividing by $B-1$. The reason is that the difference between these two numbers is $$a_n(B^n - 1) + a_{n-1}(B^{n-1} - 1) + ... a_0( B^0 - 1)$$ and each $B^k - 1$ is divisible by $B - 1$ since $x - 1$ divides the polynomial $x^k - 1$.

Use $B = 14$ in the case at hand; the remainder when dividing by $13$ will be the same as the remainder of the sum of its digits in base $14$.

Answer 2

This is a case of omega divisibility: In base $n$, a number is divisible by $n-1$ if and only if the sum of its digits is. In our usual base-ten numbering system, this gives us the rule for divisibility by 9. And in base 14, it gives us a rule for divisibility by 13.

Adding up the digits in $123456789\text{abcd}_{14}$ gives (decimal) 91, which is a multiple of 13 ($13 \times 7$). Thus, the original number is a multiple of 13.