Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
What do you mean exactly? 4 is divisible by 2 independently of base. –  Il-Bhima Sep 4 '10 at 9:11
10  
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. –  yjj Sep 4 '10 at 9:11
6  
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." –  Niel de Beaudrap Sep 4 '10 at 10:17
2  
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$. –  Joshua Shane Liberman Sep 4 '10 at 13:53

4 Answers 4

up vote 10 down vote accepted

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

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

share|improve this answer
    
It would have been helpful if you quoted the answer here in addition to the link. –  Sniper Clown May 14 '12 at 4:45

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|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\;\quad a|b \iff r(a)|r(b)\quad\quad$ (Divisibility Preservation by Isomorphisms)

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

$\rm\;(\Leftarrow)\quad r(a)|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|a\;$ or $\rm\;p|b\;$ and $\rm\;p\;$ is not a unit, i.e. not $\rm\;p|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

share|improve this answer
5  
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. –  Robin Chapman Sep 4 '10 at 18:23
4  
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). –  Robin Chapman Sep 4 '10 at 18:43
    
@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. –  Bill Dubuque Sep 4 '10 at 18:51
3  
@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. –  Bill Dubuque Sep 4 '10 at 19:33
4  
+1 for not just being a link. –  grieve Jan 30 '11 at 0:21

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.

share|improve this answer
    
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. –  Optionparty Sep 29 '12 at 7:45

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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