Is a prime number still a prime when in a different base?

Solution 1:

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

Solution 2:

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.

Solution 3:

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.

Solution 4:

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!