3 ms·

As a non mathematician the most surprising for me is that 1 is not a prime number. It still feels like a kludge because it produces inconvenient results to have

by SeanDav 13y ago

As a non mathematician the most surprising for me is that 1 is not a prime number. It still feels like a kludge because it produces inconvenient results to have 1 a prime - so let's just exclude it.

wl 13y ago
One has properties that are significantly different than the primes. Doesn't it make sense that if it behaves differently than the primes that it isn't a prime, but something else?
- gizmo686 13y ago
  One also has the properties that are iconic of primes: its only factors are one and itself. We went out of are way to exclude it, by using a less natural definition of prime numbers, because of how often we would have to say primes greater than 1.
btilly 13y ago
Actually mathematicians have gone back and forth on whether 1 should be considered a prime number.
- omra 13y ago
  No notable mathematician has considered one prime since the early 20th century (of course, I'm oversimplifying, see [1] for more information). [1]: https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.html https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.h...
  - btilly 13y ago
    You are oversimplifying more than you know. In a number theory course around 1990, I remember reading papers from the 60s which would explicitly note whether the counts of primes that they were using were starting from 1 or 2. You can define them as not notable mathematicians, but working mathematicians in number theory still had not completely standardized 50 years ago. Now for more fun, sit down with a group of mathematicians and ask whether they consider 0 to be a natural number. :-) (The answer you get will vary by field. But none will consider it a particularly important question.)
    - tel 13y ago
      cperciva answered this according to the modern algebraic understanding in response to the parent. 1 is definitely not prime when you more fully categorize the elements of sets by their algebraic properties: the existence of units is a less singular phenomenon in other algebraic structures.
      - btilly 13y ago
        Yes. More abstractly, prime numbers are those that generate prime ideals. This is a definition which generalizes to much more complex algebraic structures. However the last vestiges of the question about what definition was most natural didn't get settled until surprisingly recently.
        tel 13y ago
        Oh, sorry for being presumptuous then. I'm not aware of the recent history.
calhoun137 13y ago
One reason to not have 1 be prime, is otherwise the prime factorization of natural numbers would not be unique. This property of unique prime factorization is not simply "convenient", it is used to derive a large number of other important results. Do remember that math is a bunch of rules that are made up by people to capture certain abstract concepts, and to understand patterns and relationships between those abstract concepts. So although it might feel like a "kludge" to you, that's just the way math is. You can make up whatever rules you like, and some rules exclude "inconvenient results", leading to a deeper understanding, and thus are more widely adopted by other mathematicians.
mjw 13y ago
This isn't a surprising result though, it's a surprising (to you) definition. You could redefine "prime" to include 1 if you wanted to without changing the fundamental truth of important results about the natural numbers. It would just mean you'd have to phrase many of them in a slightly more roundabout way, e.g. with "suppose x is a prime number not equal to 1" needing to appear in key theorems where before "suppose x is prime" sufficed. (Perhaps some other theorems might be more concise, although I'd be surprised if there were a net benefit -- the community has probably had this debate a bunch of times before settling on the current consensus.) Definitions are chosen to be convenient for the purposes of communication, there's nothing inherently true or false about them. An argument for one definition being better than another might involve demonstrating that mathematical results people care about can be stated more clearly, concisely and efficiently using your alternative definition. The recent tau vs pi controversy providing an amusing example :)
- mjw 13y ago
  As a programming analogy: imagine mathematics is a big codebase and "prime" is a commonly-used function defined within that codebase. You could refactor "prime" to allow 1, provided you refactor all the call sites to work with that new definition too. Consensus seems to be that this refactoring would add LOC and reduce code readability, probably leading to someone submitting a patch soon after with a "prime-but-not-one" function and using that everywhere.
cperciva 13y ago
The problem arises when people make the mistake of thinking that number theory naturally lives in the non-negative integers; its natural embodiment is the entire ring of integers. Within this ring, the integers are divided into four sets: Zero, a (unique) value which when multiplied by anything yields itself; the Units {1, -1}, which are the elements with multiplicative inverses; the Primes {2, 3, 5, 7, ...}, which are the elements which cannot be written as the product of two non-Zero non-Units; and the Composites {4, 6, 8, 9, ...} consisting of everything else.
- anatoly 13y ago
  Units also have the property that they cannot be written as the product of two non-zero non-units. There's no important reason for Units and Primes to be disjoint sets. Units could be considered primes. It would make some things more convenient and others less convenient. For example, a prime decomposition of an element would really be a prime decomposition and not "up to a unit"; on the other hand, a proper statement of its uniqueness would be more bulky. Ultimately mathematicians decided that it's much more convenient to not consider units to be prime. It does seem to be a matter of convention, with no deep significance to it.
  - cperciva 13y ago
    The property of being invertible is very important. It may seem trivial in the context of the integers, but it's far more significant when you broaden your outlook to other rings.
i_c_b 13y ago
There are lots of ways to approach this topic, but here's my favorite, because it doesn't rely on definitions, just arithmetic... Javascript: function q(n,k){ var t = 0; for( var j = 2; j <= n; j++ )t += 1/k - q(Math.floor(n/j),k+1); return t; } function p(n){ return q(n,1) - q(n-1,1);} If you check out values of p(n) for n = 1...16, you'll see you get 0,1,1,.5,1,0,1,.3333333,.5,0,1,0,1,0,0,.25 So notice what p returns here - if n is prime, p(n) is 1. If n is a prime power p^a, its 1/a (hence 16 = 2^4 -> 1/4). And if n is 1? Then p(n) is 0. In fact, q(n,1) is a tidy (but slow to compute) expression of the Riemann Prime Counting Function: http://mathworld.wolfram.com/RiemannPrimeCountingFunction.html http://mathworld.wolfram.com/RiemannPrimeCountingFunction.ht.... This doesn't prove anything about the "definition of prime numbers", of course - definitions are social things. But 1 does behave differently from the primes in this function that seems to do nothing at all but explicitly identify primes. Nothing rigorous here, of course, but I think it's a fun, quick-to-code-and-play-with example.

by SeanDav 13y ago

As a non mathematician the most surprising for me is that 1 is not a prime number. It still feels like a kludge because it produces inconvenient results to have 1 a prime - so let's just exclude it.

wl 13y ago

One has properties that are significantly different than the primes. Doesn't it make sense that if it behaves differently than the primes that it isn't a prime, but something else?

gizmo686 13y ago
One also has the properties that are iconic of primes: its only factors are one and itself. We went out of are way to exclude it, by using a less natural definition of prime numbers, because of how often we would have to say primes greater than 1.

btilly 13y ago

Actually mathematicians have gone back and forth on whether 1 should be considered a prime number.

omra 13y ago
No notable mathematician has considered one prime since the early 20th century (of course, I'm oversimplifying, see [1] for more information). [1]: https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.html https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.h...
- btilly 13y ago
  You are oversimplifying more than you know. In a number theory course around 1990, I remember reading papers from the 60s which would explicitly note whether the counts of primes that they were using were starting from 1 or 2. You can define them as not notable mathematicians, but working mathematicians in number theory still had not completely standardized 50 years ago. Now for more fun, sit down with a group of mathematicians and ask whether they consider 0 to be a natural number. :-) (The answer you get will vary by field. But none will consider it a particularly important question.)
  - tel 13y ago
    cperciva answered this according to the modern algebraic understanding in response to the parent. 1 is definitely not prime when you more fully categorize the elements of sets by their algebraic properties: the existence of units is a less singular phenomenon in other algebraic structures.
    - btilly 13y ago
      Yes. More abstractly, prime numbers are those that generate prime ideals. This is a definition which generalizes to much more complex algebraic structures. However the last vestiges of the question about what definition was most natural didn't get settled until surprisingly recently.
      - tel 13y ago
        Oh, sorry for being presumptuous then. I'm not aware of the recent history.

calhoun137 13y ago

One reason to not have 1 be prime, is otherwise the prime factorization of natural numbers would not be unique. This property of unique prime factorization is not simply "convenient", it is used to derive a large number of other important results. Do remember that math is a bunch of rules that are made up by people to capture certain abstract concepts, and to understand patterns and relationships between those abstract concepts. So although it might feel like a "kludge" to you, that's just the way math is. You can make up whatever rules you like, and some rules exclude "inconvenient results", leading to a deeper understanding, and thus are more widely adopted by other mathematicians.

mjw 13y ago

This isn't a surprising result though, it's a surprising (to you) definition. You could redefine "prime" to include 1 if you wanted to without changing the fundamental truth of important results about the natural numbers. It would just mean you'd have to phrase many of them in a slightly more roundabout way, e.g. with "suppose x is a prime number not equal to 1" needing to appear in key theorems where before "suppose x is prime" sufficed. (Perhaps some other theorems might be more concise, although I'd be surprised if there were a net benefit -- the community has probably had this debate a bunch of times before settling on the current consensus.) Definitions are chosen to be convenient for the purposes of communication, there's nothing inherently true or false about them. An argument for one definition being better than another might involve demonstrating that mathematical results people care about can be stated more clearly, concisely and efficiently using your alternative definition. The recent tau vs pi controversy providing an amusing example :)

mjw 13y ago
As a programming analogy: imagine mathematics is a big codebase and "prime" is a commonly-used function defined within that codebase. You could refactor "prime" to allow 1, provided you refactor all the call sites to work with that new definition too. Consensus seems to be that this refactoring would add LOC and reduce code readability, probably leading to someone submitting a patch soon after with a "prime-but-not-one" function and using that everywhere.

cperciva 13y ago

The problem arises when people make the mistake of thinking that number theory naturally lives in the non-negative integers; its natural embodiment is the entire ring of integers. Within this ring, the integers are divided into four sets: Zero, a (unique) value which when multiplied by anything yields itself; the Units {1, -1}, which are the elements with multiplicative inverses; the Primes {2, 3, 5, 7, ...}, which are the elements which cannot be written as the product of two non-Zero non-Units; and the Composites {4, 6, 8, 9, ...} consisting of everything else.

anatoly 13y ago
Units also have the property that they cannot be written as the product of two non-zero non-units. There's no important reason for Units and Primes to be disjoint sets. Units could be considered primes. It would make some things more convenient and others less convenient. For example, a prime decomposition of an element would really be a prime decomposition and not "up to a unit"; on the other hand, a proper statement of its uniqueness would be more bulky. Ultimately mathematicians decided that it's much more convenient to not consider units to be prime. It does seem to be a matter of convention, with no deep significance to it.
- cperciva 13y ago
  The property of being invertible is very important. It may seem trivial in the context of the integers, but it's far more significant when you broaden your outlook to other rings.

i_c_b 13y ago

There are lots of ways to approach this topic, but here's my favorite, because it doesn't rely on definitions, just arithmetic... Javascript: function q(n,k){ var t = 0; for( var j = 2; j <= n; j++ )t += 1/k - q(Math.floor(n/j),k+1); return t; } function p(n){ return q(n,1) - q(n-1,1);} If you check out values of p(n) for n = 1...16, you'll see you get 0,1,1,.5,1,0,1,.3333333,.5,0,1,0,1,0,0,.25 So notice what p returns here - if n is prime, p(n) is 1. If n is a prime power p^a, its 1/a (hence 16 = 2^4 -> 1/4). And if n is 1? Then p(n) is 0. In fact, q(n,1) is a tidy (but slow to compute) expression of the Riemann Prime Counting Function: http://mathworld.wolfram.com/RiemannPrimeCountingFunction.html http://mathworld.wolfram.com/RiemannPrimeCountingFunction.ht.... This doesn't prove anything about the "definition of prime numbers", of course - definitions are social things. But 1 does behave differently from the primes in this function that seems to do nothing at all but explicitly identify primes. Nothing rigorous here, of course, but I think it's a fun, quick-to-code-and-play-with example.