Base Rules

Theo Schiminovich

Introduction

For the most part, we use base \(10\). We have \(10\) digits in our numbering system. This stems from the fact that we have \(10\) fingers to count with. There are many numbering systems we could use. In fact, there is an infinite amount of them; one for each natural number. However, we for the most part stick with base \(10\) in our everyday lives. Clocks utilize base \(60\), and base \(2\) and base \(16\) are common when working with computers, but base \(10\) is used in most cases. Because we are so familiar with base \(10\), we may find other bases to be cumbersome. It is usually most convenient to just convert numbers into base \(10\) and work with them there. However, if you accustom yourself to other bases, they can have many interesting properties.

Divisibility Rules

The divisibility rules of every base are different. Thus, we must examine different bases’ divisibility rules when determining which are the most convenient to work with. It is important to note that divisibility rules do not require a great deal of effort. It should be faster than dividing and determining the remainder.

A Review of the Divisibility Rules in Base \(10\)

Base \(10\) has a fair number of divisibility rules. For consistency, I will list them up to \(16\) for each base.

These divisibility rules fall into four major categories:

Applications to Other Bases

It turns out that many of these rules may be applied to other bases as well. In fact, they may be generalized for all integer bases. This may be proved for all the rules mentioned above.

The Last \(n\) Digits

Given a base \(b\), if a positive integer \(k\) is a factor of \(b^n\), then an integer \(x\) in base \(b\) is divisible by \(k\) if the last \(n\) digits are divisible by \(k\). Say \(y\) is \(x\)’s quotient when dividing by \(b^n\), and \(z\) is the remainder (also known as the last \(n\) digits of x). \(x=(y\cdot b^n)+z\) \((y\cdot b^n) \equiv 0 \mod{k}\) because \(k|b^n\) If \(k|z\), then \(z \equiv 0 \mod{k}\), then \(x \equiv 0+0 \equiv 0 \mod{k}\) so \(k|x\) Therefore, this rule can be applied to all bases.

Sum of the Digits

Given a base \(b\), if a number \(k\) is a factor of \(b-1\), then a number \(x\) in base \(b\) is divisible by \(k\) if the sum of the digits is divisible by \(k\). Say \(k\) divides the sum of the digits of \(x\). \(k|a_0+a_1+a_2+ ... + a_n\). \(b \equiv 1 \mod{b-1}\). Because \(1\) to any power is \(1\), \(b^k \equiv 1 \mod{b-1}\) for any \(k \ge 1\). This means \((b^k)-1 \equiv 0 \mod{b-1}\) for any \(k \ge 1\). So \(k|(b^k)-1\) for any \(k \ge 1\). \(k|a_0+a_1+a_2+ ... + a_n\). \(k|(b^1-1)\cdot a_1+(b^2-1)\cdot a_2+ ... + (b^n-1)\cdot a_n\). \(k|a_0+(b^1)\cdot a_1+(b^2)\cdot a_2+ ... + (b^n)\cdot a_n\). Therefore, \(k|x\)

Difference of Alternating Digits

Given a base \(b\), if a number \(k\) is a factor of \(b+1\), then a number \(x\) in base \(b\) is divisible by \(k\) if, when indexing the digits from 1 to \(n\) starting from the right, the difference between the sum of the odd-indexed digits and the sum of the even-indexed digits is divisible by \(k\). Say \(k\) divides the difference between the odd and even-indexed digits of of \(x\). \(k|a_0-a_1+a_2-a_3+ ... \pm a_n\). \(b \equiv -1 \mod{b+1}\). Because \(-1\) to any odd power is \(-1\), and \(-1\) to any odd power is \(1\), \(b^k \equiv -1 \mod{b+1}\) for any odd \(k \ge 1\), and \(b^k \equiv 1 \mod{b+1}\) for any even \(k \ge 1\). This means \((b^k)+1 \equiv 0 \mod{b+1}\) for any odd \(k \ge 1\), and \((b^k)-1 \equiv 0 \mod{b+1}\) for any even \(k \ge 1\). So \(k|(b^k)+1\) for any odd \(k \ge 1\), and \(k|(b^k)-1\) for any even \(k \ge 1\). \(k|a_0-a_1+a_2+ ... \pm a_n\). \(k|(b^1+1)\cdot a_1+(b^2-1)\cdot a_2+ ... + (b^n \mp 1) \cdot a_n\). \(k|a_0+(b^1) \cdot a_1+(b^2)\cdot a_2+ ... + (b^n)\cdot a_n\). Therefore, \(k|x\)

Compound of Other Divisibility Rules

The compounds of other divisibility rules that work in base 10 will still work in other bases, provided divisibility rules for the numbers being compounded still exist in the new base.

A Fifth Method

There is a fifth strategy that may be used. It was not mentioned earlier, because in base \(10\), it is most applicable to much larger numbers, but it is very useful in smaller bases. One may combine pairs or groups of numbers to form a number in a higher base. With this strategy, one may convert a base \(b\) number to base \(b^k\), where \(k>1\), and use the previously mentioned sum and difference rules on it. This can be done because it is quite easy to convert a number from base \(b\) to base \(b^k\), and can be done even without paper. All you have to do is group the digits into groups of 2, 3, or more, starting from the right; those are your new digits. In base \(10\), you may do this by converting a number to base \(100\), which can be done by grouping the digits into groups of two, starting from the right. Then, you may take the difference of odd and even-indexed pairs of digits to check if a number is divisible by \(101\). You may take the sum of these pairs of digits to check if a number is divisible by \(99\), or any of its factors. This actually reveals a lesser-known way of checking if a number is divisible by \(11\). Instead of adding and subtracting alternating digits, you may group the digits into groups of two, starting from the right, and add up these groups. This can be more difficult, because the numbers are larger, but it can also allow you to avoid errors associated with adding and subtracting. For example, to check if \(19645219\) is divisible by \(11\), you may break it into groups of two. \(19+64+52+19=154\), which is divisible by \(11\), so \(19645219\) is divisible by 11. The other method works too; \(1-9+6-4+5-2+1-9=-11\).

What is the Most Convenient Base to Use?

For us, base 10 is the most convenient base to use because we’ve grown so used to it. Because of this, there are no serious plans to change our base system. However, speculation abounds. If we had chosen a different base system, how would things be different? Would it be more convenient than the one we use today?

Number of Divisibility Rules for Smaller Bases

A base that’s easy to use should have:

To try to answer this question, I examined each base’s divisibility rules. Divisibility rules are what sets bases apart; they all use the same numbers, but in some, it is easier to see if a number is divisible by 7 or 9 or 10 than others. To start, I focused on small numbers. I looked at bases from \(2\) to \(16\), and compared how many divisibility rules they had for numbers from \(2\) to \(16\). I compared how many divisibility rules could be found using each of the five aforementioned methods, and how many couldn’t be found at all. For method \(5\), I only included methods that involved working with numbers less than or equal to \(100\) in size. This is because, if you group enough digits together, you may always eventually find a divisibility rule, but it becomes inconvenient after a while.

Applications of Smaller Bases

Base \(10\) has some big advantages. It’s easy to work with numbers with factors of \(2\) and \(5\) in it. It has a convenient divisibility rule for \(3\) and \(9\). It also has a divisibility rule for \(11\), which only \(4\) out of the \(15\) bases on this list possess. However, it also has some disadvantages. It lacks a divisibility rule for \(7\), the fourth most important prime. It can also be inconvenient to work with larger powers of two. For example, to check if a number is divisible by \(16\), you have to check if the last four digits are divisible by \(16\), and there are \(625\) possibilities for that! Using this table, one may determine if there is a base that solves these problems, without bringing in worse ones.

Prime Bases

The only base that has a divisibility rule for every number from \(2\) to \(16\) is \(2\). Here’s a list of all the methods in base \(2\), as an example. A similar list can be formulated for any other base:

However, this doesn’t necessarily mean that base \(2\) is the most convenient base to use. Most of its base rules involve grouping digits, which can be difficult to perform in your head. It also requires more digits than other bases to display the same number, which is inefficient. The other prime bases under \(16\) are even more difficult to use. Base \(3\) has many divisibility rules, like base \(2\), but many of them are difficult to use, like base \(2\). The other prime bases lack many divisibility rules, and the ones they do have are typically more difficult to use than the divisibility rules in other bases.

Prime Power Bases

There are four prime power bases from base \(2\) to base \(16\): base \(4\), base \(8\), base \(9\), and base \(16\). Base \(4\) and base \(8\) have more divisibility rules than the other two. Of these two, base \(8\) is likely easier to use, because fewer of its methods require converting to a higher power, and its numbers are more compact.

Other Numbers

The remaining bases are the ones that contain multiple primes in their prime factorization: \(6\), \(10\), \(12\), \(14\), and \(15\). These bases typically have many numbers who divide \(x\) if they divide the last \(n\) digits of \(x\). Any number for which the set of unique primes in its prime factorization is a subset of the set of unique primes in the prime factorization of the base number can be found in this way. This can be convenient, but it can also be cumbersome, because sometimes there are a lot of possibilities. For example, there are \(625\) possibilities for the last \(4\) digits to be a multiple of \(16\) in base \(10\), while there are \(81\) possibilities in base \(6\), and \(2401\) possibilities in base \(14\). Base \(6\) and base \(12\) are similar because both \(6\) and \(12\) contain \(2\) and \(3\) in their prime factorizations. Also, each base has two primes for which a divisibility rule cannot be applied. However, for \(6\) these primes are \(11\) and \(13\), while for \(12\) these numbers are \(5\) and \(7\); since \(5\) and \(7\) are more commonly worked with, base \(6\) is probably the easier one to work with of the two. Base \(14\) and base \(15\) are similar because they are both semiprime (the product of two prime numbers). They also each lack divisibility rules for two numbers between \(2\) and \(16\). Of these two, Base \(14\) is probably easier to use, because \(14\) is even, which makes it easier to divide by \(2\). However, it’s difficult to check if a number is a multiple of \(3\), which makes base \(14\) more difficult to use than base \(6\).

Overall

The most promising alternatives to base \(10\) are base \(6\) and base \(8\). Base \(6\) has easy-to-use divisibility rules for multiples of \(2\) and \(3\), as well as \(5\) and \(7\), while base \(8\) has divisibility rules for a variety of numbers, and the added advantage of being a power of \(2\), which makes it useful for computers as well.

Analysis of Larger Bases

Currently, our numbering system does not have many digits (only \(10\)). Therefore, I started by focusing on other numbering systems with few digits. However, there are many bases with more digits (in fact, an infinite amount). Next, I decided to look at bases larger than \(16\), and see if any of them could have advantages over base \(10\). Specifically, I looked at bases from \(17\) to \(256\), because it seems like it would be extremely difficult to keep track of more than \(256\) different digits. I decided to look for bases that have the following properties:

There are actually very few bases that satisfy these conditions. Here’s a list:

This shows that base \(6\) is rather unique among small bases. Given that base \(36\) is just base \(6\) with pairs of digits grouped together, the next base that satisfies these conditions is base \(90\).

An Example Problem

The question of which base is the most convenient to use is incredibly unlikely to come up in a competition math. However, the knowledge that the same divisibility rules we use in base \(10\) can be applied to other bases can be helpful. An example of this is in this problem: For any integer \(n \ge 2\), let \(b_n\) be the least positive integer such that, for any integer \(N\), \(m\) divides \(N\) whenever \(m\) divides the digit sum of \(N\) written in base \(b_n\), for \(2 \ge m \ge n\). Find the integer nearest to \(b_{36}/b_{25}\). (PUMaC NT #4 2017) We have shown above that, given a number written in a certain base, \(m\) divides \(N\) whenever \(m\) divides the digit sum of \(N\) if \(m\) divides \(b^n-1\). This means every number from \(2\) to \(36\) must divide \(b_{36}-1\), and every number from \(2\) to \(25\) must divide \(b_{25}-1\). The smallest such number for each can be found by determining the largest quantity of each prime factor in the numbers in the set. Therefore, \(b_{36}-1=2^5 \cdot 3^3 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31\). And, \(b_{25}-1=2^4 \cdot 3^2 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23\). Because both numbers are so large, \({b_{36}}/{b_{25}}\) is roughly equal to \(\dfrac{b_{36}-1}{b_{25}-1}\). So it is roughly equal to \(2 \cdot 3 \cdot 29 \cdot 31\), which equals 5394.

Citations

  1. “Divisibility: Rules and Recipes for Testing Divisibility in Different Number Bases.” Dozenal Society, www.dozenalsociety.org.uk/pdfs/divisibility.pdf.