Is a prime number in the decimal system still a prime when converted to a different base?
Here is the same question which has been asked at Mathforum: Here is the link
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.
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 . 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
 F. Faltin, N. Metropolis, B. Ross, G.-C. Rota,
The real numbers as a wreath product.
Advances in Math. 16 (1975), 278-304
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!
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.