44
$\begingroup$

Is a prime number in the decimal system still a prime when converted to a different base?

$\endgroup$
  • 3
    $\begingroup$ What do you mean exactly? 4 is divisible by 2 independently of base. $\endgroup$ – Il-Bhima Sep 4 '10 at 9:11
  • 17
    $\begingroup$ Think of representing a number as a pile of rocks. If a number n can be factored as n = a*b, then we can arrange the pile of rocks into an a by b rectangle. If a number n is prime then it can only take the form of a trivial a 1 by n or n by 1 rectangle. Notice we haven't made any mention of a base. $\endgroup$ – user899 Sep 4 '10 at 9:11
  • 10
    $\begingroup$ Developing on yjj's answer: n being a prime number is a property of the number in terms of arithmetic operations (e.g. multiplications). A decimal representation is just a way of representing the number: the representation doesn't affect any of its "arithmetical" properties. As the Bard said, "a rose by any other name would smell as sweet." $\endgroup$ – Niel de Beaudrap Sep 4 '10 at 10:17
  • 3
    $\begingroup$ On a semi-related note, Mersenne primes have the trivial but fun property that if $2^p -1$ is a Mersenne prime, then it can be represented as $p$ $1$'s in base $2$. $\endgroup$ – Joshua Shane Liberman Sep 4 '10 at 13:53
  • $\begingroup$ Suppose after conversion to another base a prime x wasn't a prime anymore (let's call it x2) at that other base. Then you'd be able to write it as say x2 = y2 * z2, with x2 being different from y2 (so obviously z2 wouldn't be 1). Then you'd be able to convert those numbers back to the original base and have x = y * z, where y obviously would be different from x (and thus z different from 1). So x wouldn't be prime anymore in the original base, which doesn't stand. Thus you could deduce that x2 was prime too at the target base (x had kept its primality after switching base) $\endgroup$ – George Birbilis Feb 8 '18 at 4:00
21
$\begingroup$

Here is the same question which has been asked at Mathforum: Here is the link

http://mathforum.org/library/drmath/view/55880.html

from the link

The fact of being prime or composite is just a property of the number itself, regardless of the way you write it. 15 and F and Roman numeral XV all mean the number, which is 3 times 5, so it is composite. That is the way it is for all numbers, in the sense that if a base ten number N has factors, you can represent those factors in Hex and their product will be the number N in Hex.

$\endgroup$
29
$\begingroup$

Alas, the accepted answer is misleading (and arguably incorrect). The reason that primality (or any other purely arithmetic property) is preserved in radix representation is simply that such representation faithfully preserves all of the arithmetic operations on integers. More precisely, $\:$ if $\rm\;n\to r(n)\;$ is the map from $\rm\:n\:$ to its radix $\rm\:d\;$ representation, then it preserves addition $\rm\;r(m+n) = r(m) + r(n),\;$ and multiplication $\rm\;r(mn) = r(m)\ r(n),\;$ and $\rm\;r\;$ has an inverse $\rm\;s\;$ that similarly also preserves addition and multiplication (technically: $\rm\:r\:$ is a ring isomorphism). This readily implies that the relation of divisibility is faithfully preserved in radix representation, because the relation of divisibility can be expressed as an equation involving only arithmetic (ring) operations (namely multiplication), and such equations are necessarily preserved by the maps $\rm\;r\;$ and $\rm\;s\;$ - indeed these maps are defined precisely so to preserve these fundamental operations.

It's instructive to examine more closely the preservation of divisibility. First, we recall the standard notation $\rm\;a\mid b\; := \: a\;$ divides $\rm\:b,\;\;$ i.e. $\rm\:\exists \:n\in\mathbb Z : \ an = b,\;$ i.e. there exists an integer $\rm\:n\:$ such that $\rm\;an = b\;$.

Lemma $\rm\ \ \ a\mid b \iff r(a)\mid r(b)\quad\quad$ (Divisibility Preservation by Isomorphisms)

Proof: $\rm\;(\;\Rightarrow\;)\quad a\mid b \;\Rightarrow\; \exists\:n\in\mathbb Z: \: an = b \;\Rightarrow\; r(a)\ r(n) = r(an) = r(b) \;\Rightarrow\; r(a)\mid r(b)$

$\rm\;(\Leftarrow)\quad r(a)\mid r(b) \;\Rightarrow\;\exists\:c\in r(\mathbb Z): \: r(a)\: c = r(b)\;\Rightarrow\; r(a)\ r(n) = r(b) \;\Rightarrow\; a n = b\;$

The final $\;\Rightarrow\;$ above is by applying $\rm\;r\:$'s inverse $\rm\:s\:$ so to cancel the $\rm\;r\:$'s using $\rm\;\: sr = 1 =\;$ identity map.
Note: this employs $\rm\:s\:$'s preservation of multiplication, $\:$ viz. $\rm\:s(r(a)\: r(n)) \:=\: sr(a)\: sr(n) \:=\: a\: n\;$

As a corollary, we conclude that primes (i.e. irreducibles) are also preserved, since they are definable purely in terms of divisibilty, viz. $\rm\,p\,$ is prime $\, :=\ \rm p = ab \Rightarrow p\mid a\;$ or $\rm\;p\mid b\;$ and $\rm\;p\;$ is not a unit, i.e. not $\rm\;p\nmid 1\;$.

So your question reduces to the more fundamental why is radix representation a ring isomorphism, i.e. why really does radix representation preserve the addition and multiplication operations? This is a very good question that deserves a thoughtful answer. It's a serious pedagogical oversight that this topic is rarely discussed in algebra textbooks. Although most students understand this fact subconsciously, many have difficulty providing a rigorous proof (or, worse, they overlook the fact that it does require a rigorous proof). Your question would attract much more interest and receive much more interesting replies if you rephrase it in this manner. Thus I propose the following:

Suggestion: Edit the title of your question to say "Why is radix representation a ring isomorphism, i.e. why does it preserve addition and multiplication?". Include in your question a brief description of your knowledge level so to help set the proper level for replies, e.g. do you already know any abstract algebra or elementary number theory? Unaccept the currently accepted answer so that the software will continue to bump up the question till it gets a number of good answers. IMPORTANT: Wait at least a week before accepting any answer so that everyone has a chance to see the question. This helps serve to maximize its exposure and hence maximize your potential of receiving insightful answers. If all goes well this should result in an interesting thread that will help serve as a future reference for many similar frequently asked questions.

Note to much more experienced readers: this problem is not as trivial as you might think at first glance (and certainly less trivial for novices). For example, the analogous problem for real numbers (or p-adics) is the subject of a famous paper [1]. For an introduction see e.g. here. Its closing line is quite apropos:

This is very much in keeping with Rota’s thinking that mathematics is not just a quest to solve problems, it is also a quest to understand the mathematical universe as clearly and as deeply as possible

[1] F. Faltin, N. Metropolis, B. Ross, G.-C. Rota,
The real numbers as a wreath product.
Advances in Math. 16 (1975), 278-304

$\endgroup$
  • 14
    $\begingroup$ Bill, the accepted answer is just a link. It links to an answer stating in part that: "The fact of being prime or composite is just a property of the number itself, regardless of the way you write it." This answers the OP's question succinctly and accurately. $\endgroup$ – Robin Chapman Sep 4 '10 at 18:23
  • 8
    $\begingroup$ Fine, Bill, let us agree to disagree. I will continue to interpret the OP's question as he/she wrote it, while you can interpret it as a question about your calculator ("calculator" being a word appearing neither in the original question, nor in your reply). $\endgroup$ – Robin Chapman Sep 4 '10 at 18:43
  • 1
    $\begingroup$ @Robin: I interpret the question less trivially, e.g. "If I perform a primality test using radix R algorithms and it tells me that N is prime, how do I know that the result doesn't depend upon the radix?" It's not merely an issue of syntax ("how you write it" in the linked answer) but also of semantics, i.e. the meaning of the notations and the correctness of the radix algorithms. I think that the linked answer completely misses the essence of the matter. $\endgroup$ – Bill Dubuque Sep 4 '10 at 18:51
  • 4
    $\begingroup$ @Robin: Perhaps our different interpretations reflect our different backgrounds. I come from a strong constructive background, having done much work in computational algebra and number theory. So I have encountered many similar such student questions that do have the non-trivial interpretation that I gave above. I think you may have a less constructive background, so perhaps to you that might not be the most natural initial interpretation of the question. $\endgroup$ – Bill Dubuque Sep 4 '10 at 19:33
  • 10
    $\begingroup$ The problem with changing the question to "Why is radix representation a ring isomorphism, i.e. why does it preserve addition and multiplication?" then people like me who weren't familiar with the terms "radix" or "ring isomorphism" would never find it when trying to google if prime numbers are still prime numbers in other bases. I'm glad the OP didn't take that suggestion. $\endgroup$ – Frank Shmrank Nov 10 '15 at 15:12
8
$\begingroup$

Is a prime number in the decimal system still a prime when converted to a different base?

The base is a numbers symbology (display representation).

A prime number is a prime by defination, irrespective of base.

$\endgroup$
  • 2
    $\begingroup$ Sorry for such an abrupt answer. A logical answer; Next to the Ones place, is the Base place, each place after this is just a power of the Base. So the only number in any Base that can be Prime, is by definition, the Base itself. Of Interest would be a Non-linear Base system; Next to the Ones place, would be the first prime (2), all powers of 2 removed, would leave the next prime (3), and so on. Like a sieve program eliminating all powers of each Base. Each place becomes waited, by its own Base. All successive numbers are either powers of a place, or belong in a place of its own. $\endgroup$ – Optionparty Sep 29 '12 at 7:45
3
$\begingroup$

We should distiguish between numbers, on the one hand, and numerals , on the other, which are used to represent numbers. So, e.g., 13 = 15(octal) = D hexadecimal = XIII = treize, in French word(s) = τρισκαίδεκα. It is prime, no matter how you represent it. Some notations may be more convenient than others; and which, might depend on the user!

$\endgroup$
  • $\begingroup$ "τρισκαίδεκα"? is this some math/verbal constant? it reads as Greek text but in modern Greek it would be "δεκατρία", not "τρις-και-δέκα" (3+10) $\endgroup$ – George Birbilis Feb 8 '18 at 4:07
0
$\begingroup$

Do you like omelettes? I like them for breakfast once in a while, not everyday. You might have an egg-laying hen or two in your backyard. Me, I have to go to the store and buy eggs a dozen at a time.

They almost always come a dozen to a carton, arranged in two rows of six (or six columns of two, if you prefer). It would also be possible to arrange them in three rows of four.

However, yesterday, I neglected to check a carton before buying it. It was missing one egg, so it was one short of a dozen. I'm pretty sure I wasn't robbed, there was more valuable stuff to take than an odd egg. But I can't tell you whether it was at packaging that the deficit occurred, or at some point prior to my purchase.

Don't worry, I still had more than enough eggs for my omelette. So at that point, the number of eggs I had was a prime number. In the carton, I had one row of six eggs and one row of five eggs. If the carton was arranged for three rows of four eggs each, I'd have two rows with four eggs each and one row with three eggs. Or maybe three rows of three eggs each and one row with two eggs.

If you want to line up one egg short of a dozen in more than one row such that each row has the same number of eggs, well, that's impossible. Unless you figure out some way to neatly divide some of the eggs. Maybe if you hard-boil them first...

What I'm getting at here is the different representations of one short of a dozen in a few different bases. One short of a dozen in decimal is 11. That's 102 in ternary, 33 in base 4, 15 in base 6, B in duodecimal.

If $p$ is a positive prime, given some integer $b > 1$, there is no way the base $b$ representation of $p$ ends in 0 unless $b = p$, in which case the base $b$ representation is 10. And given any integer $b < -1$, it is also impossible for the base $b$ representation of $p$ to end in 0, unless $b = -p$, in which case the base $b$ representation is 1?0 (replace the "?" with the digit for $p - 1$).


There is a related question that might be causing you confusion (or may have caused you confusion), and that is: can a string of digits represent a prime in one base but a composite number in another base?

The answer to that question is absolutely yes. Suppose a string of three digits represents a positive prime $p$ in a given base $b$, where $b$ is an integer greater than 1. Obviously $p$ must be an odd prime.

If we change $b$ to $b + 1$, then the string of three digits that represented an odd prime now represents a positive even number greater than 2, which must therefore be composite.


In case anyone's wondering, I think I thought a new question was a duplicate, but then I wasn't able to find what it was a duplicate of, so maybe the new question really was a new question afterall.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.