10101 and 11011 are never prime

One particularly tricky aspect of number sense is being able to separate the abstract notion of value from more concrete visual representations of numbers, and the even more concrete notion of countability. For instance, some people get caught up on zero not being a value because there’s no point in counting zero of everything; after all, zero is a relatively new concept in the mathematical scheme of things.

In this entry, I want to talk about our place value system, with an eye towards seeing bases algebraically. This relies on separating the notion of value from its visual (mathematical) representation. For instance, “10” is not a unique value. In base 10, it represents this many objects: xxxxxxxxxx. In base 5, it represents this many objects: xxxxx. This is clearly not the same number of objects.

So let’s start in base 10. It turns out that 10101, 11011, and 10201 are all non-prime. The prime factors of 10101 are 3, 7, 13, and 17; the prime factors of 11011 are 7, 11, and 13; the prime factor of 10201 is 101. Well, so what? There’s nothing particularly interesting about noting the prime factors of a specific number.

These three numbers are actually prime in all bases in which they’re valid numbers. The proof involves seeing numbers written in a place value system algebraically. That’s how our base systems work, although we tend to not think of it that way very much, if at all.

Working from right to left, each digit in a place value represents the digit shown multiplied by $$b^{k-1}$$, where $$b$$ represents the base and $$k$$ represents how many place away that digit is from the decimal point. For instance, 12,345 in base 10 is shorthand for $$5\cdot 10^0 + 4\cdot 10^1 + 3\cdot 10^2 + 2\cdot 10^3 + 1\cdot 10^4$$.

Generally, it’s not worth seeing numbers in terms of their longer versions. However, there are some fun puzzles, such as the one at hand.

For instance, consider 10201. In base 5, for instance, $$2 \cdot 2 \cdot 23 \cdot 23 = 10201$$. In base 8, $$5 \cdot 5 \cdot 15 \cdot 15 = 10201$$ (158 is prime). We want to prove that this number is non-prime in any base above 2.

Writing 10201 algebraically gives us: $$1\cdot b^4 + 0\cdot b^3 + 2\cdot b^2 + 0\cdot b^1 + 1\cdot b^0 = b^4 + 2b^2 + 1$$. We can factor this expression: $$b^4 + 2b^2 + 1 = (b^2 + 1)^2$$. 10201 will always have 101 as a factor, regardless of the base. In base 10, 101 is prime; in base 5, $$101 = 2 \cdot 23$$; in base 8, $$101 = 5 \cdot 15$$. 1020157 (10,562,50010) has 10157 or 325010 as factors.

Writing 10101 algebraically gives us: $$1\cdot b^4 + 0\cdot b^3 + 1\cdot b^2 + 0\cdot b^1 + 1\cdot b^0 = b^4 + b^2 + 1$$. We can factor this expression: $$b^4 + b^2 + 1) = (b^2 + b + 1)(b^2 – b + 1) = (b^2 + b + 1)(b(b – 1) + 1)$$. 10101 will always have two factors: 111 and x1, where x is one less than the base. For instance, $$10101_{10} = 111_{10} \cdot 91_{10}$$ while $$10101_5 = 111_5 \cdot 41_5 = 31_{10} \cdot 21_{10} = 651_{10}$$.

Writing 11011 algebraically gives us: $$1\cdot b^4 + 1\cdot b^3 + 0\cdot b^2 + 1\cdot b^1 + 1\cdot b^0 = b^4 + b^3 + b + 1$$, which we can factor: $$b^4 + b^3 + b + 1 = (b^3)(b + 1) + (1)(b + 1) = (b^3 + 1)(b + 1)$$. Hence, no matter what the base, 11011 will have factors of 1001 and 11. This is perhaps the least surprising, when we think about it: 11011 is plainly divisible by 11.

We can use this technique to create other “never prime” numbers. For instance, $$(b^2 + b + 2)(b^2 – b + 2) = b^4 + 3b^2 + 4$$, so 10304 is non-prime in all bases over 4. As long as the expanded polynomial only has positive coefficients less than b, the resulting number will be prime in bases greater than and equal to b. Play around and see what other “never prime” numbers you can create.

Clio Corvid

This site uses Akismet to reduce spam. Learn how your comment data is processed.