Non-Decimal Primes

[ptomb]

I've looked around for a bit to see if anyone has discussed primes existing in all numeric systems (binary, octal, hexadecimal, etc.) or if there are some that do not yield primes. It's a bit late here and I'm a bit foggy headed, so I'm not in a state where I can deeply think on this, so I ask it in a forum rather than think for myself. Anyone care to educate me?

[antonfire]

Binary, octal, hexadecimal and decimal are all just different conventions for writing down natural numbers. Whether you happen to write 13 as 1101₂, or as 15₈, or as d, it's prime. You might as well ask if there are any languages in which an apple doesn't have seeds.

[Meteoric]

Prime-ness comes from the actual properties of numbers, not the properties of the symbols we use to write them. If I hand you 13 objects, you cannot arrange them into equal groups with none left over, except by making 1 group of 13, or 13 groups of 1. Thus, 13 is prime. It doesn't matter whether you convert that number into octal, hexadecimal, sexagesimal, binary, or tally marks.

[Qaanol]

What might be interesting to know is that “prime” refers to the property that, if x divides yz, then x divides at least one of y and z. (Where x is not 0, and there is no v satisfying xv=1.)

On the other hand, irreducibility refers to the property that, if x=yz, then there is some w such that at least one of yw=1 or zw=1. (Again, where x is not 0, and there is no v satisfying xv=1.)

In the case of integers, a number x is prime if and only if it is irreducible, but the two properties are not necessarily equivalent in other structures.

[skullturf]

To expand on Qaanol's point, this is related to the question of unique factorization.

In the usual integers, factorization into primes is unique. (Except, of course, for the order of the factors.)

Something interesting to think about: How can we prove, starting from first principles, that (1) every integer can be factored into primes, and (2) when we factor an integer into primes, the factorization is unique?

It's relatively easy to give a brief self-contained proof of (1) starting from scratch. But proving (2) from first principles is more subtle.

(An example of a system where unique factorization doesn't hold is the set of numbers of the form a+b*sqrt(-5), where a and b are integers. The number 6 can be factored as 2*3 but also as (1+sqrt(-5))*(1-sqrt(-5)), and one can show that neither of those factorizations can be broken down further.)

[PM 2Ring]

The fact that integers have unique prime factorization is rather fundamental. Interestingly, the Gaussian integers, complex numbers of the form a +bi where both a and b are integers, also have unique prime factorization. (FWIW, I've just written a Python program that factorizes Gaussian integers; such factorizations can be used to generate Machin-like formulae).

Although primeness is unaffected by the base used to represent integers, the choice of base does affect the form of simple digit-based divisibility tests. Thus in base 10 we can easily see if an integer is even, or divisible by 5, and there are simple tests for divisibility by 3 and 11. There is a digit-based test for divisibility by 7 in base 10, but it is a bit complicated, whereas in base 7 this is much easier to see, since all multiples of 7 must end in 0.

It can easily be shown that all primes greater than 3 are of the form 6n ± 1, so in base 6, all primes greater than 3 must end in 1 or 5. Similarly, all primes greater than 5 are of the form 30n + r, where r is one of {1, 7, 11, 13, 17, 19, 23, 29}, so in base 30 all primes greater than 5 must end in one of those digits. Unfortunately, things get a little more complicated for higher primorials, since 7# = 210 and 11² and 13² are both less than 210.

[Qaanol]

Along those lines, in base 12 there are easy tests for divisibility by 2, 3, 11, and 13, a nearly-as-simple test for divisibility by 5 and 29, and a slightly more complicated test for 7 and 19. Meanwhile 17 and 23 remain annoying.

[mfb]

Tests for divisions (with a number expressed in a given base b=\prod p_i^{a_i} with distinct primes p_i) are always easy for divisors d=\prod p_i^{b_i} which are a product of (only) prime factors present in the base, and quite easy for (base+1) and (base-1).
In the former case, you just have to check the last n digits, where n=\max_i{\left[\frac{b_i}{a_i}\right]}, unless I made a mistake here.
For base-1, calculate the digit sum, and for base+1, calculate the alternating digit sum and check whether they are 0 or not.

With all other divisors, there is an equivalent to the digit sum, but with different weights for each digit. Needs a bit more calculations, but it is easy to do in linear time (with the length of the number).

[Qaanol]

Tests for divisions (with a number expressed in a given base b=\prod p_i^{a_i} with distinct primes p_i) are always easy for divisors d=\prod p_i^{b_i} which are a product of (only) prime factors present in the base, and quite easy for (base+1) and (base-1).
In the former case, you just have to check the last n digits, where n=\max_i{\left[\frac{b_i}{a_i}\right]}, unless I made a mistake here.
For base-1, calculate the digit sum, and for base+1, calculate the alternating digit sum and check whether they are 0 or not.

With all other divisors, there is an equivalent to the digit sum, but with different weights for each digit. Needs a bit more calculations, but it is easy to do in linear time (with the length of the number).

Right. Additionally, a number written in base k is trivially already written in base k² by looking at pairs of digits. Therefore, it is just as easy to check divisibility by k²-1 and k²+1, and similarly with higher exponents by considering more digits together. The sum-of-digits and alternating-sum-of-digits give more than just a boolean test for divisibility, they actually give the exact remainder modulo k-1 and k+1 respectively.

So, for a number in base 12, you can look at pairs of digits and treat it as being written in base 144. Now you can easily find the remainder modulo 143 or 145. As it happens, 145=5*29, so to test an arbitrary base-12 number for remainder mod 5, it suffices to take the alternative sum of digit-pairs, repeat as necessary, then check the remainder mod 5 of a 2-digit base-12 number. Ditto for 29.

Along the same lines, 12³+1=7*13*19, meaning a similar approach can be used with groups of three digits for remainder mod 7 and 19 (it would work for 13 too, but you can do that directly from base 12.)