Talk:Prime number/Draft: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>D. Matt Innis
imported>Barry R. Smith
(reapprove to fix "error"?)
 
(85 intermediate revisions by 16 users not shown)
Line 1: Line 1:
==Approval area==
{{subpages}}
<!--{{ToApprove
|url = http://en.citizendium.org/wiki?title=Prime_number/Draft&oldid=100099326
|now = 09:59, 9 May 2007 (CDT)
|editor=Jitse Niesen
|editor2=Michael Hardy
|editor3=
|editor4=
|group=Mathematics
|group2=
|group3=
|date =May 10, 2007
}}-->


Commented out V1 To approve tag
==What kind of number==
<!--
The first sentence doesn't specify what kind of numbers we are dealing with. [[User:Andres Luure|Andres Luure]] 22:26, 5 November 2007 (CST)
{{ToApprove|editor=Greg Martin|editor2=Jitse Niesen|url=http://en.citizendium.org/wiki?title=Prime_number&oldid=100097398|group=Mathematics|date=May 6, 2007}}-->


Creating [[Prime number/Draft]] [[User:David Tribe|David Tribe]] 20:04, 6 May 2007 (CDT)
: It says "A prime number is a number that can be evenly divided by exactly two positive whole numbers, namely 1 and itself."  The word "itself" implies it must be a positive whole number.  (But maybe it could be more explicit.) [[User:Michael Hardy|Michael Hardy]] 14:03, 20 December 2007 (CST)
Approved and locked nominated version Approved V 1. About to move talk page of approved to Talk/Draft [[User:David Tribe|David Tribe]] 20:16, 6 May 2007 (CDT)


Approval date for v 1.1 arrives without objection. I see one editor nominating who has only made a small grammar change with a second editor approving as well.  I see no dissentionsThis article can be re-approved using the Individual Editor approval rules. There are two edits after the approval date shown that appear to be important content issuesApproval Editor okays approval of these two editsApproval commencing. --[[User:D. Matt Innis|Matt Innis]] [[User talk:D. Matt Innis|(Talk)]] 18:53, 10 May 2007 (CDT)
:: And why not be more explicit? It seems much clearer to me, a number theorist even, if you say "a prime number is a positive whole number that can be evenly divided by exactly two positive whole numbers, namely 1 and itself"In the original version, I didn't immediately return to the beginning of the sentence and think, "oh, that IMPLIES that the original number was a positive whole number"If the only concern is that repeating the same phrase twice might be a turn off, let me quote from Strunk and White's "Elements of Style", one of the guides to style that we are supposed to take advice from (see section 19) "The likeness of form enables the reader to recognize more readily the likeneses of content and function...the unskilled writer often violates this principle mistakenly believing in the value of constantly varying the form of expression.  When repeating a statement to emphasize it, the writer may need to vary its formOtherwise, the writer should follow the principle of parallel construction." It seems to me that the repetition in our case is not for emphasis, and after the repetition, it will be firmly fixed in the reader's mind that all numbers begin considered are positive whole numbers.[[User:Barry R. Smith|Barry R. Smith]] 20:40, 29 March 2008 (CDT)


----
I am not sure it is even clear to say "exactly two" when it could be "two and only two." --[[User:Thomas Simmons|Thomas Simmons]] 19:56, 8 November 2007 (CST)


{{checklist
: In mathematics, at least, the phrases "there are exactly two" and "there are precisely two" are understood to express the same statement as "there are two, and only two" (for instance, see the discrete math text I taught out of this past term, or the Wiki page on if and only if).  I have considered these as equivalent for many years, so it is hard for me to put myself in the shoes of someone who might be seeing this for the first time.  The issue that you are concerned with is that someone might accidentally confuse "exactly two" with the idea that it has at least two, but possibly more, positive divisors.  I cannot see how even people with very little mathematical experience would interpret "exactly two" in this manner, the word "exactly" being inserted exactly (hehe) to let you know that this is the precise number. Furthermore, I think it is hard to argue against "exactly two" being the more elegant phrase.  I much prefer the phrasing of the first sentence of the approved article to the first sentence of the current draft.  Any rebuttals?[[User:Barry R. Smith|Barry R. Smith]] 20:40, 29 March 2008 (CDT)
|                abc = prime number
|                cat1 = Mathematics
|                cat2 =
|                cat3 =
|          cat_check = n
|              status = 1
|        underlinked = n
|            cleanup = y
|                  by = [[User:Greg Woodhouse|Greg Woodhouse]] 10:58, 22 April 2007 (CDT)
}}


STOP!! Michael, you cannot approve an article that you have authored BY YOURSELF. The changes between the approved version that is up and the one you are nominated are largely your own changes as author. In that case, You need THREE EDITORS in MATH to do that. So- all 3 have to put up an approval for TODAY. sorry- but as you are the only editor who has worked on the changes since approval as author, you certainly cannot nominate the changed article for  new approval. If there are copyedits, then either one of the two nominating editors can contact me. You were not a nominating editor.Please contact the other editors and work together.[It is true that ANOTHER math editor-solo- who has NOT authored in this revision could nominate the revision for approval. Basically, an editor cannot push through approval for something that his or her own work. Greg Martin could nominate for the first approval because he edited a developed article written by others, and Jitse could second because it was a second.If another editor nominates this revision for approval- you could second . )[[User:Nancy Sculerati|Nancy Sculerati]] 20:53, 8 May 2007 (CDT)
:: I agree. Even to naive readers "exactly two" cannot possibly mean "at least two". [[User:J. Noel Chiappa|J. Noel Chiappa]] 22:12, 29 March 2008 (CDT)


Mike, not that she needs my support here, but Nancy is correct. If you have contributed significantly to an article, you must first have agreement from two other math editors before it can be nominated for approval by any of you. Please review [[CZ:Approval Process|Approval Process]]. --[[User:Larry Sanger|Larry Sanger]] 21:07, 8 May 2007 (CDT)
Footnotes versus links to stubs: Until many of the terms are explained with their own articles, the use of footnotes to explain terms and analogies should continue. Otherwise we will have dead links in red letters for a long time to come. This will also mean that the article can reach a broader population as it is written. The chemistry metaphor is another example, that comparisons might be lost on anyone who is not up to speed on freshman level chemistry. So for ease of use and market appeal and just plain educational focus, explaining terms in footnotes would be a good idea. The high school students using CZ today will be the grad students referring to it in future.--[[User:Thomas Simmons|Thomas Simmons]] 19:56, 8 November 2007 (CST)


:It's rather vague what "contributed significantly" means. For instance, compare with Nancy's comment dated 22:59, 29 April 2007 on this page. Greg Martin's changes were bigger than Michael's. As I see it, Michael's changes were more than copyediting, but this is a matter of definition, and it is possible to see them as mere copyediting.
== What i miss ==
:A bigger problem in my mind is that the date-of-approve was set to be the date that the ToApprove template was actually added. [[CZ:Approval Process]] says that there should at least be 24 hours in between, and that makes sense to me. People should have time to review the article. We're all learning the process as we go along so things will go wrong sometimes.
:Anyway, as it happens, I support the changes that Michael made so I put the ToApprove template back up. I don't think I'm considered to be an author in this case: I wrote some parts, but they were approved in V1.0, and my only change since then was definitely a copyedit. I think a short period (one day) is justified because the changes are not big and quite important; the approved version is definitely misleading. -- [[User:Jitse Niesen|Jitse Niesen]] 21:25, 8 May 2007 (CDT)


Actually, I don't think the mention of Euler's result that the sum of the reciprocals of the primes diverges can be considered a "copy edit".  But the \scriptstyle changes certainly could be.
There are some things, that are not in thearticle:
:
I do think it is important to alter the very misleading statement about "unique factorization" in the currently approved version. [[User:Michael Hardy|Michael Hardy]] 22:09, 8 May 2007 (CDT)


::Michael, if you are happy with the version that Jitse has nominated above- add your name to the template. That's the way to show your approval as editor. If you are ''not'' happy with it - if that version is not satisfactory- remove the template. That's how you can show that you -as a math editor- feel so strongly that the version being nominated is inadequate for approval. We are all pretty awkward at this (me especially) but we do manage to make the approvals process work. This way- as long as that template is there -on May 10- a constable will approve that version. [[User:Nancy Sculerati|Nancy Sculerati]] 22:35, 8 May 2007 (CDT)
*Prime numbers and Pseudoprimes ([[Fermat pseudoprime]], [[Euler pseudoprime]], [[Carmichael number]], ...)
*Properties of Prime numbers
**p is a Prime number <=> p|(p over n) for 1<n<p
**Prime numbers and Perrin sequence
**Prime numbers aund Lucas sequence
--[[User:Karsten Meyer|arbol01]] 05:04, 1 January 2008 (CST)


== Primes and their generalizations ==
: I don't understand the first comment under "Properties of prime numbers"
: As for prime divisors of elements of those two particular sequences, it seems to me that these are far too specialized to be included in this page, and would be better placed on the "Perrin sequence" and "Lucas sequence" pages separately.  Otherwise, one would need to enumerate ALL named recursively defined sequences, and the divisibility properties in each case.  I would imagine that just this task would encompass many pages in itself.[[User:Barry R. Smith|Barry R. Smith]] 00:20, 30 March 2008 (CDT)


After some thought, I added a clarification to the introductory material. The reason is that while the rational primes (i.e., primes in <math>\mathbb{Z}</math>) are very important in cryptographic applications, other engineering applications (notably error detecting and correcting codes, where linear codes are very important) depend upon properties of primes and factorization in other rings (such as <math>\mathbb{F}_2[x]</math>). It may seem like a small thing, but I do want to be sure that the claims made in the introductory section are correct. [[User:Greg Woodhouse|Greg Woodhouse]] 05:41, 5 April 2007 (CDT)
::**p is a Prime number <=> p|(p over n) for 1<n<p
:: Iff p is a prime number, than p divides (p over n) [Binomialcoeffizient] for every n between 1 and p.


== Just delete this? ==
:: If p is a prime number, than p divides P<sup>p</sup> and p divides U(P,Q)<sup>p</sup> - P


I noticed that someone removed the hyperlinks from the latter part of the introductory paragraph, and I agree that this was a good idea. To be honest, I wouldn't mind just deleting
::are properties, that belongs to the Prime numbers. It belongs to the Perrin sequence respectively to the Lucas requence respectively to the binomialcoefficence too. --[[User:Karsten Meyer|Karsten Meyer]] 02:45, 19 May 2008 (CDT)


<blockquote>
== 1 revisited ==
Understanding properties of prime numbers and their generalizations is essential to modern cryptography, and to public key ciphers that are crucial to Internet commerce, wireless networks, telemedicine and, of course, military applications. Less well known is that other computer algorithms also depend on properties of prime numbers. These algorithms allow computers to run faster, computer networks to carry more data with a greater degree of reliability, and are basic to the operation of many consumer electronics devices, such as television sets, DVD players, GPS devices, and more. Life as we know it today would not be possible without an understanding of prime numbers.
</blockquote>


I put it in there to provide some motivation for the study of prime numbers, but I'm not so sure I don't find it distracting (or just plain too long) ''without'' the hyperlinks. [[User:Greg Woodhouse|Greg Woodhouse]] 10:14, 5 April 2007 (CDT)
Regarding my above comment in "What kind of number" above, I personally feel that the first sentence should read something like, "A prime number is a whole number greater than 1 that can be evenly divided by exactly two positive whole numbers, namely 1 and itself".  It seems that the main argument above against saying a prime must be bigger than 1 from the outset is the need for clarity in the first sentence, but I feel that currently this clarity comes at the price of correctness.  As written, I feel the that first sentence is plain wrong, and I personally wouldn't put my stamp of approval on it.


:I think it's a bit too much; especially the last sentence. However, don't throw out the baby with the bath water. We do need some motivation. A simple solution would be to retain only the first sentence (personally, I'd also delete telemedicine).
I don't want to sound TOO dismissive. I didn't just go edit the draft, because I understand that their was some discussion about this above. Apparently, the status of 1 seems to have been problematic even when the fundamental of arithmetic were laid down in Euclid's "Elements". However, it seems to me that the tone of the approved version suggests that the typical modern "choice" to label 1 as neither prime nor composite is a result of whimsy or chance. This is a false impression.
:I had some other comments when I read through the article. I'll just jot them down here for you to consider or ignore as you see fit. You already resolved one of them (in Euclid's proof, explain why it's impossible that no prime divides ''N'') by adding a discussion on unique factorization.
:* The aside on notation. I think the definition of prime number without symbols works perfectly fine, making me wonder why you praise the virtues of notation at that place. Incidentally, you need to explain the notation ''a'' | ''b''.
:* The equivalence of the two definitions for prime numbers is in fact quite important (unique factorization depends on it), and should perhaps be stressed more.
:* What do you have in mind when you say that the second definition is preferred in advanced number theory? It's a long time ago that I looked at number theory, but I thought both were used (they are called irreducible and prime elements, respectively).
:* On a first reading, the proof of unique factorization looks a bit messy, though I can't articulate exactly what the problem is. I'll try to have a look at it later.
:-- [[User:Jitse Niesen|Jitse Niesen]] 19:52, 5 April 2007 (CDT)


*I deleted the last sentence of the introduction, along with the reference to telemedicine.  
In a sense, I guess, defining 1 as special can seem as arbitrary as defining 0 factorial to be 1.  But with the invention of the gamma function and the recognition of its canonical properties, can there be any dispute as to the correct definition of 0 factorial?  Similarly, there are very sound reasons that 1 has been given special status over the last century or so. The easiest to explain is that the Fundamental Theorem of Arithmetic is just false if 1 is considered prime:  considere, 6 = 2*3 = 2*3*1 -- two different prime factorizations.  (By the way, I also think that the words "Fundamental Theorem of Arithmetic" should appear somewhere on the "prime number" page -- can't remember if I saw it anywhere). A second reason is that with the development of algebraic number theory, the units in algebraic number fields were found to play a very special and important role. Within the integers, 1 and -1 are the only units, so it is hard to get a feel for the special role they play only within this context. Nevertheless, the fact that 1 is the unique multiplicative identity within the integers should make a strong impression. (For more about 1, see this website http://mathforum.org/kb/message.jspa?messageID=1379707, and especially the comments by John Conway, a world-renown number theorist.)
*What I think I was trying to do with the notation for "divides" (not that I really planned it out in advance) is inrouce the notation by using it, and then step back and explain what it means. I'll add something there.
*The comment about the latter definition of "prime" being more characteristic of advanced work was inappropriate (and probably wrong). It's gone now. As I'm sure you realize, what I had in mind is that the concepts prime and irreducible just happen to coincide in '''Z''' because it's a PID. Right now, you're seeing my thoughts in rather raw form, and I guess I was thinking that I didn't want to get involved with a discussion of primes vs. irreducible elements, but I wanted to at least note that there is a difference.
*I don't like what I wrote about unique factorization, either. I didn't really want to dwell on it too much, but by the time I had written it out, the argument was just too long, and a bit awkward sounding. I'll see what I can do. [[User:Greg Woodhouse|Greg Woodhouse]] 23:49, 5 April 2007 (CDT)


Okay, I've rewritten the proof of prime factorization and filled in Euler's proof that there are infinitely many primes. [[User:Greg Woodhouse|Greg Woodhouse]] 08:26, 6 April 2007 (CDT)
In summary, although the status of 1 might have fluctuated in the past, I believe the consensus of the vast majority of working mathematicians at present is that it should not be considered prime, and this is reflected in todays high-school textbooks.  Furthermore, I do not see any indication that this will change soon.  Thus, it seems that the proper definition should make it clear that 1 is not prime from the first sentence.  Otherwise, we will be spreading disinformation to those casual learners who wonder, "hmm, I wonder if 1 is a prime", look at the first line of the Citizendium page, and then wander off to tell their friends what they learned.[[User:Barry R. Smith|Barry R. Smith]] 01:31, 30 March 2008 (CDT)


== What to include? ==
: Dude, you're the expert! I (at least, can't speak for everyone) defer to your clear familiarity. So I'd go for it. Plus to which, your point about the Fundamental Theorem of Arithmetic is good (and so easily understandably by all that it should probably be mentioned in the article as a reason why 1 is not considered by mathematicians as being part of the set of prime numbers, even though by the simplistic definition of 'prime', it seems to be prime). [[User:J. Noel Chiappa|J. Noel Chiappa]] 11:40, 30 March 2008 (CDT)


The topic of this article is obviously a big subject. When I picked up this article (from the "most requested" list on the WG page), I wasn't sure how much I wanted to cover, though some of the basics are clear. I at least want to state the prime number theorem, and But what about, say, say something about unsolved problems about prime numbers.But what about, say primality testing? I haven't even talked about the sieve of Eraosthenes yet! I thought about covering, say, the primes in the rings of Gaussian and Eisenstein integers, but that should probably be left to another article. What do you think? [[User:Greg Woodhouse|Greg Woodhouse]] 08:41, 6 April 2007 (CDT)
:Barry, the first sentence currently says "A prime number is a positive whole number that can be evenly divided by exactly two positive whole numbers, namely 1 and itself." I believe this does say that 1 is not prime, just as you want, as the number 1 has only one divisor, namely 1 itself. So I'm not sure what your point is.
:I agree with all the rest you wrote (for what it's worth, as you know of course more number theory than I do). -- [[User:Jitse Niesen|Jitse Niesen]] 16:00, 30 March 2008 (CDT)


:I've added a section on primality testing. I'd say: include full descriptions of both trial division and the sieve of Eratosthenes, but leave out detailed discussion of optimizations and complexity analysis (leave those aspects for subarticles). Mention that there are faster algorithms such as the Miller-Rabin test, but don't describe them in this article. I agree that generalizations of primes in other rings should largely be left to another article.
:: Someone careful and analytic might draw that conclusion, but not all our readers might fit that definition. Baldly saying '1 is not a prime number' is probably what they need. Without in any way intended to be demeaning to them, I am always mindful of that wonderful George Carlin line: "Think of how dumb the average person is - and then realize that half of them are dumber than ''that''."
:Looking at the Wikipedia article for inspiration:
:: (Adding "different" - as in "two different positive whole numbers" - might make the definition cast-iron, though). But it might still be useful to have a section on 'why 1 is not a prime number'; the point about the Fundamental Theorem of Arithmetic could go there. [[User:J. Noel Chiappa|J. Noel Chiappa]] 23:31, 30 March 2008 (CDT)
:* We should definitely have a section on the distribution of primes (PNT, prime counting function), on the general problem of finding patterns in the primes (mentioning Ulam's spiral, etc)
:* We should describe applications of prime numbers in some more detail. This could look similar to the section in the Wikipedia article.
:* We don't need trivia lists like Wikipedia's "Properties of primes" and "Primes in popular culture" and "Trivia" sections. That's not to say all of the content of those sections would be inappropriate here, but I'm sure we can come up with a more coherent article structure.
:*There are lots and lots of special classes/categorizations/subsequences of primes. Except for perhaps twin primes and Mersenne primes, I think these are mostly trivia and should be left to another article.
:[[User:Fredrik Johansson|Fredrik Johansson]] 10:06, 6 April 2007 (CDT)


::I'll largely be echoing Fredrik here. PNT is important as a standard non-trivial result. Riemann hypothesis is worth a million bucks; need I say more? Twin prime conjecture is accessible and drives home the point that not everything in maths has been done centuries ago. I'm reserving judgement about Ulam's spiral. Primality testing, beyond Eratosthenos, should probably be kept brief: something about the quest for the largest known prime number, and the polynomial algorithm found recently by the Indians (AKS?). Generalizations should also be briefly mentioned. Perhaps a paragraph about Gaussian integers as an example. And applications; can be contrasted with Hardy's "number theory is beautiful because it's useless". All that will probably be enough. -- [[User:Jitse Niesen|Jitse Niesen]] 12:22, 6 April 2007 (CDT)
::: Yes, Jitse, it seems that after all of that, I understand 1 okay but I still have trouble counting to 2 :-). Anyway, my own error emphasizes the point that inferring information about the prime number from information presented at the END of the sentence is not my own thought process, and probably not a lot of other people's. (I suppose if I still kept up my German, I would be used to that sort of thing :-) ).  For instance, the end of the sentence in the approved version is where you find that the prime in question is a positive whole number, but I prefer the draft version where it comes right out and tells you that. I think a similar modification to clarify that the whole number is bigger than 1 from the outset, "baldly" saying it, as Noel suggested, is also in order.  I also like your suggestion, Noel, of providing clearer reasons for 1's unique position. Would that be better as a new subsection, a footnote, or a link to a page about the arithmetic properties of 1?[[User:Barry R. Smith|Barry R. Smith]] 22:31, 31 March 2008 (CDT)


:I had never heard of Ulam's spiral, but looking at the article in Mathworld, I see Athur C. Clarke mentioned it in "The City and the Stars". It seem to be a popular culture connection (which has nothing to do with whether or not it's mathematically interesting, of course!) I'd leave it out of this article, at least for now. I'm trying to think of a good way to handle the PNT (and the Riemann hypothesis). Simply stating these results without giving any indication of their significance or how they fit in to number theory in general hardly seems enough. In my opinion, just stating results or definitions is where we move from being an encyclopedia to being a dictionary, at least so far as mathematics is concerned. [[User:Greg Woodhouse|Greg Woodhouse]] 16:28, 6 April 2007 (CDT)
:::: I'd say a new subsection, not a footnote. Although I don't know where it would fit... hmmmmm (cogitates). Maybe take the third para of the intro, about factorization, and move it to a new section immediately after the intro, titled something like "Factorization and primes"; I think that's a sufficiently important aspect of primes that it's worth of a section on its own. Mention of the Fundamental Theorem of Arithmetic would go there, after which it would be natural to flow from that into your point about the FToA ruling out 1 as a prime. The existing text about "(although this is a matter of [the] definition [of a prime], and mathematicians in the past often did consider 1 to be a prime)" would naturally fit in there too. In fact, maybe a sub-section of that "Factorization and primes" section would cover the primality of 1, and although it would start with the FToA point, etc, you could add your other points above about algebraic number theory, etc. [[User:J. Noel Chiappa|J. Noel Chiappa]] 00:38, 1 April 2008 (CDT)


== Prime Number Theorem ==
::::: Yes, counting is hard ;) I added "greater than 1" to the first sentence, so that's settled for now.
::::: Noel's suggestion to have a new section on the Fundamental Theorem of Arithmetic looks like a good idea. We probably don't want to write too much on it, I think details should go at [[unique prime factorization]] or some other article, but I agree that it's important enough in this context to get a section. Indeed, the primality of 1 can covered there, though I'm not sure it should be a sub-section; how much should we say about it? -- [[User:Jitse Niesen|Jitse Niesen]] 08:10, 1 April 2008 (CDT)


I just added a formal statement of the theorem. Obviously, more exposition is needed.
:::::: Since I'm not a mathematician, and the article is intended (mostly!) for non-mathematicians, would you like me to try the layout I suggested; you all can then check it to make sure I didn't commit any math howlers? [[User:J. Noel Chiappa|J. Noel Chiappa]] 10:32, 1 April 2008 (CDT)


== The Sieve of Eratosthenes ==
::::::: Sounds good to me Noel [[User:Barry R. Smith|Barry R. Smith]] 11:40, 1 April 2008 (CDT)


I just added a verbal description of the algorithm. I'm not at all good with diagrams, so if you have ideas for making it look better, by all means do!
OK, I've taken a crack at it. I hope you will all find the result (mostly :-) satisfactory; it seems to me (at least :-) to flow well, and in a natural progression. A couple of things where I don't have enough math knowledge to really fill in, and you all need to backstop: i) explain some about ''why'' and ''how'' the FToA is so important, ii) some of the more advanced stuff about why 1 is not a prime (in Barry's original comments in this section above) was way over my head, so I just cut-n-pasted the brief allusion here, which you all ought to expand a teensy bit (and make sure my copyediting didn't produce bogosities). Oh, also, the section on factorization should include a sentence or two about how factorization of very large numbers is a key in the crypto-system stuff we alluded to in the intro. I'm too lazy to do that - off to other things! [[User:J. Noel Chiappa|J. Noel Chiappa]] 12:53, 1 April 2008 (CDT)


== The Riemann Hypothesis ==
: I think it looks great, Noel.  The only concern I have is the statement that the Fundamental Theorem of Arithmetic is an important building block in many areas of number theory.  Historically, the Fundamental Theorem appeared in Euclid's "Elements", the most influential math book of all time, as Proposition 14 in Book IX (This is from a secondary source).  Actually, this proposition only shows that if a number n factors as n = p_1 x p_2 x p_3 x ... x p_r, where p_1, ..., p_r are DISTINCT prime numbers (i.e., n could be 30 = 2 x 3 x 5, but not 12 = 2 x 2 x 3, since 2 appears twice), then then those are the only prime numbers that appear in its factorization.  Thus, this says significantly less than the Fundamental Theorem of Arithmetic, and only says something about very special types of numbers.
:It wasn't until about 2000 years after Euclid that the Fundamental Theorem was codified and decisively proved, by Carl Friedrich Gauss (I have seen this claim many times, but don't have a math historian to use as a source).  It seems generally believed that earlier people understood the principle of unique factorization, but perhaps there had never been a reason to try to prove it.  It wasn't until larger number systems than the integers began to be considered that it was realized that the Fundamental Theorem describes a particular property of the integers.  In fact, in other number systems, the analog of unique factorization FAILS to be true, which is what Gauss realized and motivated him to prove the theorem for integers.  So in a sense, it is the failure of the Fundamental Theorem to be an important result in these other number systems (i.e., it's just not true) that prompted its formulation.
:  Does this make sense?  If so, then maybe I will just stick a brief mention of some of this information in place of the statement that I objected to.  In any case, besides being an assumed property of the integers that is used to build up many of the important results in Arithmetic, I suppose an answer to your question of why FToA is important is that it fails in other number systems.  In response to your other question, I don't see any "bogosities" :). <small>...said</small> [[User:Barry R. Smith|Barry R. Smith]] ([[User_talk:Barry R. Smith|talk]]) {{#if:17:42, 1 April 2008|17:42, 1 April 2008|}} (<small>''Please sign your talk page posts by simply adding four tildes, ''</small><nowiki>~~~~</nowiki>.)


Okay, I know the Riemman hypothesis is central to the study of prime numbers, but I'm really struggling with this section. I don't see any easy ways to motivate it. In fact, you have to grapple with the idea of analytic continuation before the staement even makes sense. Now, I know that one thing that has always intrigued me is how function fields (in positive characteristic) are so much easier to analyze. But that's not an answer, and it's certainly not something that can be discussed in this article. On the other hand, I'm really loathe to say, "Well there's this mysterious thing out there that's really exciting, but it just can't be explained in layman's terms". Any ideas? [[User:Greg Woodhouse|Greg Woodhouse]] 17:55, 9 April 2007 (CDT)
:: Got it. My text about ''the Fundamental Theorem of Arithmetic, which is a key building block in many important areas of number theory'' was in large part a reaction to the very name - I figured anything called the Fundamental Theorem of Arithmetic had to be important! But I notice you say "besides being an assumed property of the integers that is used to build up many of the important results in Arithmetic", so perhaps I wasn't so far wrong? :-)
:: So, I'll change the text to say "Fundamental Theorem of Arithmetic, which is used to build up many of the important results in the area of arithmetic", and you can further tweak that to your satisfaction, to be perfectly accurate.
:: After thinking about it, I would suggest that this article probably isn't the place to mention how the FToA is not true in other number systems, because it's one further step removed from the article's focus, which is primes. It would also intrude into the flow from i) the mention of FToA to ii) how the FToA makes it desirable to exclude 1 from the set of primes. That observation would of course be a perfect fit in the [[Fundamental Theorem of Arithmetic]] article, though.
:: I'll also add that remark about how factorization is what's important in public-key crypto work. And then I leave it to you all... :-) [[User:J. Noel Chiappa|J. Noel Chiappa]] 19:28, 1 April 2008 (CDT)


:I had a quick go at it and did some major restructuring in the process:
:::I do have some remarks and questions.
:* I removed the bit on extending the list in the sieve of Eratosthenes. It doesn't seem that important.
:::# You added the word "different" to the first sentence, so that it reads: "A prime number is a whole number greater than 1 that can be evenly divided by only two different positive whole numbers, namely 1 and itself." Is this necessary? Is there really a chance that if we remove the word "different", somebody will think that 7 is not a prime because it has three divisors, namely 1, 7 and 1?
:* Added an introduction to PNT to smoothen the transition.
:::# We have an article about [[unique factorization]]. Do we need a different article about the [[Fundamental Theorem of Arithmetic]]?
:* Moved the discussion of the zeta function further down because it is rather tricky.
:::# You say that the Fundamental Theorem of Arithmetic "is used to build up many of the important results in the area of arithmetic." I would replace "arithmetic" by "number theory". Arithmetic can mean number theory, but I think this meaning is disappearing. Barry, would do you think?
:* Removed the discussion about elementary proof of PNT, because I couldn't make it fit.
:::# Finally, I have my doubts about "a more general trend in mathematics over the past century, which is to recognize that 0 and 1 are very special numbers". I thought mathematicians always recognized this. I think the point in the posts you refer to is that mathematicians are getting more careful to make sure that their proofs are really correct.  
:* Removed the details about the Riemann Hypothesis. It's impossible to explain properly without mentioning analytic continuation. It can be explained in layman's terms (at least, we can try to), but it will take up quite a bit of space and perhaps this article is the proper place to do it.
:::I'd write longer paragraphs, but that's personal I guess. I have a maths history book which says that Gauss proved the Fundamental Theorem. I think earlier proofs exist, but they are nowadays deemed incomplete. I didn't know that the Elements contains a more restricted result. -- [[User:Jitse Niesen|Jitse Niesen]] 14:18, 3 April 2008 (CDT)
:As I said, it was a quick job and only meant as a possible suggestion of where to go. In my experience it's good to have at least a rough idea of the possible ways to structure the article instead of discussing it in abstracto. In particular, I wrote from memory that Hadamard and de la Vallee Poussin use the location of zeros of the Riemann zeta function, but I may well be mistaken here.
:By the way, Euler's proof needs more explanation (why are the sum and the product equal?). -- [[User:Jitse Niesen|Jitse Niesen]] 22:58, 9 April 2007 (CDT)


I think that your reorganization has improved the article, and certainly agree that the section on the sieve of Eratosthenes was too long. I made a few attempts last night to be more explicit about the Euler product (other than noting, as I always have, that it follows from unique factorization), but it just came across as pedantic, so I cancelled both edits. I'm not sure how to fit in either, but the elementary proof of the prime number theorem was a major achievement, and something that can hardly be omitted from an article on prime numbers. Finally, the section on Euler's proof is starting to take on a less significant role in the article (for example, I had intended to use it to establish that <math>\sum 1/p</math> diverges). Perhaps that section should be omitted? [[User:Greg Woodhouse|Greg Woodhouse]] 11:46, 10 April 2007 (CDT)
:::: Reponses:
::::# I agree, the word different is superfluous.
::::# No, we don't need two separate articles.  However, if the main article is going to be "unique factorization", then "FToA" should be given as a synonym in the first sentence.  Furthermore, typing "FToA" into CZ's main search box should deposit one on that page.  Right now, if one searches for "FToA", he just gets a list of search hits, and the first one is actually the prime number page draft, not the unique factorization page. It needs to be redirected -- is this easy?  I'll look into it... (Interestingly, typing "unique factorization" into the Wikipedia search box deposits you on a page about unique factorization domains -- a bad choice of redirection IMO).
::::#  Noel originally wrote "number theory", and my long winded response boiled down to my thinking "arithmetic" was the more apt word.  Perhaps it should say "elementary number theory".  The problem is that number theory these days is big, and for instance, it seems hard to me to draw a direct connection between unique factorization and major results in analytic number theory (although Euler's factorization of the zeta function involves it).  Also, it is precisely the failure of unique factorization that spurred the invention of rings and ideals and algebraic number theory in general (although unique factorization into prime IDEALS is an important building block in this area).  Certainly, if you stick to elementary number theory, working with integers and congruences, then it is important, although even here it is hard to gauge how much.  Very few proofs seem to come out and say, "and this next step follows from unique factorization".  It is more "fundamental" in its importance, since much structure would be absent if it were false.  For instance, statements that "such and such type of number has a prime factor of this type" would be silly, if you could have different prime factorizations. Also, security of certain cryptosystems is based on the assumption that the product of two large primes is hard to factor.  If there were other factorizations, some that maybe involved small primes, these would no longer be viable cryptosystems.  There must be a pithy way to summarize this type of fundamental importance accurately, and if someone thinks of one, that would be great.  Maybe a nice allusion to that atoms/molecules metaphor again?  I'll try to figure one out myself.
::::# I agree that even mathematical noobs probably have always realized that 0 and 1 are "special" numbers right away. However, even important number theorists as late as the 1900's would sometimes list 1 as a prime number.  No one found a real need for a proof of FToA until Gauss, so I wouldn't say necessarily that the problem was that proofs were incorrect.  I would guess that once Gauss proved this result, he did not consider 1 to be prime (I'd hope so, at least).    Perhaps a lot of the time, people didn't realize the appropriate definitions until enough of the theory had been developed, like the general theory of rings and the FToA in this case  ("appropriate" definitions being ones that make the theory and theorems as simple and elegant as possible).
::::I get worried about repeating something like "Gauss was the first to prove this theorem".  I have been tempted to write sentences like this several times now, and even if I see one in a history book, there never seems to be a source.  How could there be?  Someone would have had to comb every extant reference to make sure no one else had proved it earlier, an impossible task.  So every statement like this seems to beg the question, "how many old primary sources did you consult before you decided that Gauss was the first?"  It certainly seems to happen regularly that some new source is discovered that proves such a statement false.[[User:Barry R. Smith|Barry R. Smith]] 22:04, 3 April 2008 (CDT)


:I admit that I was surprised to see Euler's proof. It relies on the divergence of the harmonic series and the sum of the infinite geometric series, both of which are fairly advanced topics (in comparison with what precedes and follows). On the other hand, it ties in nicely with unique prime factorization and the Riemann zeta function (it explains why this function could give information on the distribution of primes). Therefore, I decided not to remove it immediately.
:::: A few addtional bits:
:Perhaps it's better to explain the sum=product stuff where we introduce the Riemann zeta function. At that point, we can assume some more mathematical sophistication on the part of the reader, so it will be easier to explain why the sum and product are equal. We can then make a short remark there that <math>\zeta(1)=\infty</math> because the harmonic series diverges, which implies that there is an infinite number of primes. -- [[User:Jitse Niesen|Jitse Niesen]] 07:24, 15 April 2007 (CDT)
::::# I added that "different" after thinking for a while of how to make the intro sentence as clear ''and'' consise as possible for ''non-mathematician'' readers; i.e. I only added words where I thought they really helped. Yes, ''technically'' it's superfluous (to the likes of us :-) - but I believe it will increase the likelihood of correct comprehension for the 'average' reader.
::::# For what it's worth, Wikipedia has a separate article on the {{WP|Fundamental Theory of Mathematics}}. Not saying we need one, that's y'all's call, just providing data. I have set up the redirects as you suggest.
::::# I believe I can find a way to say exactly what Barry wants - that although the FToA is not called out specifically, what it says is important, and the basic idea/attribute of the integers (unique factorizability) which it talks about is used throughout "elementary number theory" (which I will also put in).
::::# That was my (not very good, sigh) attempt to capture the essence of what Conway said in one of his posts in that thread ("Mathematicians this century are generally much more careful about exceptional behavior of numbers like 0 and 1 than were their predecessors: we nowadays take care to adjust our statements so that our theorems are actually true. It's easy to find lots of statements in 19th century books that are actually false with the definitions their authors used"). I tried to capture the jist of what he said in a concise way that would make sense to non-experts, although you're right, my words went further than what he said - I will look at it again.
:::: Thanks for being so patient with this non-mathematician! :-) [[User:J. Noel Chiappa|J. Noel Chiappa]] 23:02, 3 April 2008 (CDT)


::This sounds like a better approach. [[User:Fredrik Johansson|Fredrik Johansson]] 10:43, 15 April 2007 (CDT)
:::: OK, fixed #'s 3 and 4. See what you think. [[User:J. Noel Chiappa|J. Noel Chiappa]] 23:20, 3 April 2008 (CDT)


:::I implemented my suggestion. I see that my writing style is rather bland, especially when juxtaposed with Greg's lively writings, so it does need some rewriting (apart from fixing the mistakes which probably crept in). -- [[User:Jitse Niesen|Jitse Niesen]] 11:09, 19 April 2007 (CDT)
::::: Yes, perhaps I am not well-suited to decide how useful the word "different" is.  If it makes it clearer to the non-expert, like explicitly clarifying that 1 is not prime, then perhaps it is better to include it.  I like having the main page titled "unique factorization" rather than FToA, since the former is the more descriptive term. I definitely like the change to "elementary number theory".  However, that sentence now seems wordy to me.  Do you like this  better: "Unique factorization into prime numbers is formalized as the Fundamental Theorem of Arithmetic, being the foundation for much of the structure of the integers described by elementary number theory."?  Also, I will go ahead and divide the first paragraph of the section on 1 into two sentences -- it seems too long for one sentence.  I understand now where your comment on 0 and 1 came from -- I had already forgotten precisely what Conway had written (absent-minded professorism!).  I like that sentence now. Can I cut the last statement in that section now? It can appear on some more advanced page, and the words "the Fundamental Theorem is a good example" above it seem to obviate the need for having this second more obscure example. 
::::: Also, thanks for wading through my windiness to help make this fundamental page correct but accessible to a broad readership.[[User:Barry R. Smith|Barry R. Smith]] 10:58, 4 April 2008 (CDT)


== Some comments ==
:::::: Hi, sorry about the slow reply - been on travel.
:::::: I will take a look at that sentence; I already trimmed it once to be less wordy.
:::::: The two-sentence form looks better to me.
:::::: The "last statment in that section" (i.e. "At a more advanced level ... not visible in the context of integers.") could definitely move to a more advaced page.
:::::: Hey, we're all here to make a better encyclopaedia, right? :-) [[User:J. Noel Chiappa|J. Noel Chiappa]] 16:19, 10 April 2008 (CDT)


The article ends by mentioning "&pi;(''n'')". I don't think this function was mentioned earlier in the article, so a definition is needed. (Something to do with the density of primes in the integers?)
:::::: OK, I took a crack at that section. I split that sentence you were asking about into two, but made no other changes to it because it didn't seem that bad. I did make a number of other changes to improve the overall readability, though.
:::::: First, I had placed that long sentence at the end of the section, so that it would flow into the opening of the next section (why 1 is not a prime). I decided that the advantages of that flow were not worth the overall non-optimal ordering of content within this section, so I moved it up. When I did that, I could run that 'widow' short para about the atom analogy into it, so that analogy was no longer just hanging about on its own (and I could cut some duplicate verbiage at the same time).
:::::: Finally, I reworded the last sentence in the first para; the old version was crisp and exact 'mathematicsese', but I think my new (slightly longer) version will be more accessible to 'average' readers.
:::::: Anyway, see what you think. [[User:J. Noel Chiappa|J. Noel Chiappa]] 16:48, 10 April 2008 (CDT)


I wasn't able to follow the Euler proof of infinite number of primes as it stoodI got help from elsewhere, and have added some words to help others over the same hurdleI also rearranged the equation to put the product on the left and the harmonic series on the right, because I can figure out that the two are equal by starting with the product and manipulating it, but I can't if I start with the harmonic series.  
: ''Reset indentation''
: I like your changes, with two comments:  your rewording of the last sentence in the first para of the approved version is fine, except that some mathematicians encourage avoidance of the word "any", as it can mean different things to different people and in different contextsWhen someone says, "if x is any number", do they mean that they are making a statement that is true for ALL possible values of x, or do they mean that they have singled out ONE particular value of x, whose identity has not yet been revealed, and are making a statement about that one value?  I don't know if this type of confusion can arise in your new sentencePerhaps a statement about use of the word "any" should be on the style guidelines for the math workgroup, if it isn't there already?  The second comment is that to me, at least, the sentence suggesting the analogy to atoms/molecules seems to show up abruptly at the end of the paragraph, with not enough connection to the earlier sentences in the paragraph. Good work though.[[User:Barry R. Smith|Barry R. Smith]] 23:54, 18 May 2008 (CDT)


In Euclid's proof, I took out the q-hat notation, which I found confusing.
:: I get your point about 'any': I had thought that the wording there ("Every number N >1 ... for any particular N") made it clear that if referred, one at a time, to any (all) N in that set. The problem is that I want the reader to, in their mind, single out one particular N, so I can make a statement about the set of factorizations of ''that'' N (i.e. make it is simple as possible to understand) - and also indicate that that statement is true of all N in the set N > 1. What word(s) do mathematicians use when they want the 'all' meaning of "any"? Or should I reorder it (which will make it a tiny bit longer), and explicitly say something like 'Considering any N > 1, it can be written as a product of prime factors, and all such expressions for N will contain the same factors, differing only in the sequence in which they are listed; this is true for all N > 1.'? That's probably slightly more rigorous, but somehow seems to not flow as well. Or maybe I'm being too picky? Is there some other alternative fix (an added modifier, or something) you can suggest, that removes the possible lack of rigour, while retaining the current form?
:: As to the analogy to atoms/molecules (and associated footnote), I agree with you! I didn't introduce any of that; I wasn't too thrilled by it, but out of deference to whoever wrote it, didn't want to simply toss it. I struggled to find a place for it where it ''did'' fit, and following onto the text about "critical building block in many of the important results in the area of elementary number theory" seemed the best I could find. One possibility is to transplant it up into the intro section, placing it in a para of its own, after the para about odd numbers, where I think it would fit a bit better (in terms of overall flow). That would make an awfully short one-sentence para, though. I suppose we could move some (or all?) of the text in the footnote up there, to bulk it up, but if so, I should probably rewrite the whole thing from scratch, to come up to the standards we have reached everywhere else (preen, preen :-). Let me ask this: is the thought it is trying to express accurate, and worth retaining? If so, I can set to and try and write it better, and would suggest that location in the intro for it. Reaction? [[User:J. Noel Chiappa|J. Noel Chiappa]] 10:25, 19 May 2008 (CDT)


I made a few other relatively minor changes.
==Primes of special forms subsection==


:Thanks for your comments and input! Yes, <math>\pi(x)\scriptstyle</math> does have to do with the distribution of primes (I thought I defined it?) Anyway <math>\pi(x)\textstyle</math> is the number of primes <math>\le x\scriptstyle</math>. [[User:Greg Woodhouse|Greg Woodhouse]] 13:01, 15 April 2007 (CDT)
The third type of prime considered in this section seems out of place to me.  As far as I know, primes of the form n^2+1 are mostly a curiosity, and uninteresting for anything else.  It would be easy to find many other types of "primes" of this form.  Any one object to me removing them?  As consolation, I am going to insert a bullet about primes in arithmetic sequences, which seem much more important to me.[[User:Barry R. Smith|Barry R. Smith]] 17:50, 1 April 2008 (CDT)


::I apologize;  the definition was right there in the article the whole time;  I'd just read it.  Maybe it would be easier to notice, though, if the same variable were used.  I mean, is there a reason why in one place it's given as <math>\pi(x)\textstyle</math> and in another place as <math>\pi(n)\textstyle</math>?  Would it be OK to change the <math>n\textstyle</math> to an <math>x\textstyle</math>?  It also helps that "textstyle" or "scriptstyle" have been put in so it doesn't display in a tiny script -- I hadn't known how to do that.
: <s>I might suggest leaving them because Mersenne primes are a major source of "largest prime" values. I know, I know, to most true mathematicians this is probably boring juvenile crap, but some people enjoy it (like some people enjoy tiddliwinks) - see, for instance, [http://www.mersenne.org GIMP] so an article on primes ought to at least ''mention'' Mersenne primes!</s> Blast, wrote that whole section, then realized you were talking about ''N^2+1'', not ''2^N-1''! On thinking about it, they seem rather obscure to me, so we can probably lose them. I'd just comment them out, rather than discard the text completely; that way, if someone makes a case for them, it's trivial to put them back. [[User:J. Noel Chiappa|J. Noel Chiappa]] 19:40, 1 April 2008 (CDT)
::Re the Euler formula:  good, there's a lot more guidance for the reader now in following this proof. I suggest inserting something to let the reader know where they're heading:  I would insert, just before ''"Using the formula for the sum of a geometric series,"'' a phrase which tells the reader that we're about to prove the Euler formula as opposed to assuming it's true and based on that prove something else.  I would insert something like ''"Euler established this result as follows."'' or ''"It can be seen as follows that this sum is equal to this product."'' or ''"This can be established by ..."'' or another phrase which accomplishes this purpose.  (I don't know how Euler actually did it.)  Comments?  --[[User:Catherine Woodgold|Catherine Woodgold]] 09:21, 22 April 2007 (CDT)


:I went ahead and changed the language a bit. The notation <math>\pi(x)</math> vs. <math>\pi(n)</math> is a bit more problematic, though, because it's important that <math>\pi</math> is a function of a ''real'' variable, and using ''n'' as a parameter would tend to obscure that fact. [[User:Greg Woodhouse|Greg Woodhouse]] 10:49, 22 April 2007 (CDT)
==Alternative definition==


::What about using <math> x\scriptstyle</math> in both places? Is there a reason why <math> n\scriptstyle</math> has to be used? This is not a terribly important point, anyway--[[User:Catherine Woodgold|Catherine Woodgold]] 18:47, 23 April 2007 (CDT)
I am interested in having a non-mathematician perspective on the last part of this section. It seems to me to ramp up in sophistication very quickly, starting with mention of the word "ideal", and then moving into sentences about "rings" and "generation" of "ideals". Certainly, if this page is intended for non-specialists, then those terms should at least be linkedBut would they be better placed in a page about prime ideals in rings, and a much simplified discussion put in its place on this page?[[User:Barry R. Smith|Barry R. Smith]] 17:50, 1 April 2008 (CDT)


== Request for approval ==
: I couldn't make heads or tails of it most of it. I would just move everything past the Euclid's Lemma thing to an /Advanced subpage (see [[Quantum mechanics/Advanced]] for what such pages look like). The first couple of paras I would leave, as they are comprehensible to us mortals, and mildly interesting - but I will rewrite them a bit to make them clearer. [[User:J. Noel Chiappa|J. Noel Chiappa]] 19:48, 1 April 2008 (CDT)


Editors: Could you take a look at this article and, if you think it's ready, initiate the approval process? [[User:Greg Woodhouse|Greg Woodhouse]] 13:31, 22 April 2007 (CDT)
==Fermat primes==
The current discussion of Fermat primes says that one can construct a regular p-gon if p is a Fermat prime.  Perhaps more surprising is that these are the ONLY primes for which you can construct a regular p-gon, so I am going to add this.


== Large primes ==
The above unsigned comment isn't by me (though I agree with it). [[User:Peter Jackson|Peter Jackson]] 17:12, 24 November 2008 (UTC)


I think the article needs to discuss in some more detail the state of the art in primality testing (a lot of readers would probably be interested in knowing what the largest known prime is) and the use of prime numbers in cryptography. [[User:Fredrik Johansson|Fredrik Johansson]] 21:14, 23 April 2007 (CDT)
MUCH MORE IMPORTANT. There's an error in the article. It says Fermat primes are 2↑n + 1. That should be 2↑2↑n + 1. [[User:Peter Jackson|Peter Jackson]] 17:10, 24 November 2008 (UTC)


:Yes, that's a good point. We don't talk much about primality testing, but we might start out with, say, Mersenne primes. [[User:Greg Woodhouse|Greg Woodhouse]] 23:05, 23 April 2007 (CDT)
==Other types of primes==
I think that if we are going to discuss other types of primes, obvious choices include Wieferich and Wilson primes.  But where do we draw a line about which special types of primes to include?  Wieferich primes showed up in work on Fermat's Last Theorem.  Perhaps a criterion would be to include any special forms for which a significant result is known?  I like this better than the criterion of including any forms of primes with "names".[[User:Barry R. Smith|Barry R. Smith]] 18:15, 1 April 2008 (CDT)


== Prime number records ==
: Write articles on them, and link to those articles from the "Related Articles" subpage. As you suggest, I'd only put really important ones here. That's probably where to put Fermat primes, now that I think of it. I'll leave that to you all too. [[User:J. Noel Chiappa|J. Noel Chiappa]] 19:48, 1 April 2008 (CDT)


I've been thinking about what to do here. Paulo Ribenboim's ''The Little Book of Bigger Primes'' (see the references) has all kinds of prime numbert records in it, but it hardly seems interesting to just quote results from another source hardly seems that interesting (and I'm not so sure it isn't plagiarism). Where do we draw the line? [[User:Greg Woodhouse|Greg Woodhouse]] 18:01, 24 April 2007 (CDT)
== Reapproval needed ==


:You'll find much more up-to-date records on the web, for example at [http://primes.utm.edu/largest.html the prime pages]. In any case, I think it would be sufficient to mention the current largest Mersenne prime, as well as outline (in a few sentences) the history of computing large prime numbers (maybe we should have a separate [[prime number records]] or even [[mathematical records]] article?). Then mention somewhere that in cryptographical applications, primes need "only" be a few hundred digits long in which case primality testing on a PC is dirt cheap (while semiprime factorization is not). [[User:Fredrik Johansson|Fredrik Johansson]] 02:23, 25 April 2007 (CDT)
As pointed about by Peter Jackson above, the definition of Fermat prime should be a prime of the form <math>2^{2^n}+1</math>, not one of the form <math>2^n+1</math>.  Actually, the primes of the first type ''are precisely'' the primes of the second type. (Proof:  If n=kt with k an odd prime, then
2^n+1 has 2^t+1 as a factor other than 1 and itself).  But as written, the definition is certainly nonstandard and somewhat misleading.  As such, I think reapproval of this page should be expedited.


::I agree with Fredrik Johansson here.  A list of records would be too much, I think, but mentioning a couple of interesting and important records in the article somewhere would enhance the article. --[[User:Catherine Woodgold|Catherine Woodgold]] 09:56, 29 April 2007 (CDT)
Issues:   


== uh oh - suggestions for changes ==
* Noel suggests that Fermat primes should appear just on the "related articles" page.  I think it is appropriate to have something in the main article about special types of primes, mentioning a few types.  Fermat prime is certainly one of the most popular.  But there should be agreement -- the problem could be fixed just by linking to pages about a few types of special primes without defining any of them in the "prime number" page.


It's super to see a lot of quality work being put into this article, which will be one of the most important ones in the Mathematics section. I do have several suggestions for altering and improving the article. All of them are (of course) debatable.
* It is technically correct as written, so if reapproval is an arduous process (I haven't done it myself), then perhaps it is not worth it just to fix this one problem.


; My suggestion for the first sentence - ''"A prime number is a whole number that can be evenly divided by exactly two numbers, namely 1 and itself."''
The current draft is rather different than the approved version, so if there is agreement that the draft is better than the current version, or could be made better than it, then perhaps we should work to reapprove now even if the process is difficult.[[User:Barry R. Smith|Barry R. Smith]] 21:22, 27 November 2008 (UTC)
: Most readers' default reaction to "number" is to think of whole numbers, so I think the existing parenthetical comment is more distracting than helpful. The changes to the second part of the sentence are motivated by wanting the definition to be simple enough while still not admitting 1 as a prime number. (In fact not calling 1 a prime number is a relatively recent development, something like a hundred years old. To me the two most important reasons why 1 shouldn't be a prime number are (a) the annoyance it would cause when stating the unique factorization property of integers and (b) the modern understanding of the difference between "units" and "irreducibles" in other rings. Maybe this is worth mentioning briefly in an appropriate part of the article.)
; Move all the details of the Riemann zeta function, the proof of the prime number theorem, and the Riemann hypothesis to (a) newly created article(s) devoted to those topics.
: In other words, most of the "Distribution of prime numbers" section. This echoes one of my [[Talk:Complex_number#Can_we_make_it_even_better.3F|comments about the ''Complex number'' article]], namely that an introductory article on prime numbers should mention what we know but should be careful about putting in too much detail about how we know it. Mentioning these three things, particularly the prime number theorem, is a great idea - this is important folklore surrounding the primes - but formal descriptions and proofs are probably more suitable for articles more directly concerning them. ''We should keep the statement of the prime number theorem and perhaps a bit of commentary; it might also be helpful to add a description of the prime number theorem for arithmetic progressions, the most concrete example of which is the fact that roughly a quarter of all prime numbers end in each of the digits 1, 3, 7, and 9 - thus tying into a remark in the primality testing section. Perhaps these two results can be grouped in a section called "Solved problems" or something like that, to partner with the section on "Unsolved problems" ... the "Solved problems" section can include Bertrand's Postulate, that there's always a prime between n and 2n.''
; Add a section early on that addresses the question "Why is this random definition of 'prime number' at all worthwhile?"
: Two answers: one, that every number has at least two divisors, namely 1 and itself (yes, 1 is weird), and so numbers with no other divisors are special; and two, the statement of unique factorization. (Other answers?) ''I always find it useful to make an analogy with physical chemistry: if integers are the molecules, then prime numbers are the atomic elements, and unique factorization is analogous to the statement that particlar molecules always have the same atomic structure. This can then lead into the desire to understand the distribution of primes, and the unhappy(?) fact that the answer is nowhere near as simple and patterned as the periodic table of elements.''
; Take out the proof of unique factorization, and either take out the "Definition" section or else move it much to much later in the article.
: Same reasoning as above. Most non-mathematicians are confused by the simple assertion that there's anything to prove in the statement of unique factorization! As for "Definition", the difference between "prime" and "irreducible" in general rings is nuanced enough - and it doesn't even manifest itself in the integers! - and I don't think the layperson will get too much out of it. At the very least, put it much later, once the more accessible facts surrounding prime numbers have been laid out.
; Keep Euclid's proof that there are infinitely many prime numbers.
: I know that's not a suggestion for a change! Here, not only is the fact itself incredibly important, but Euclid's proof is an amazingly great example of a proof - known in antiquity, sleek and elegant, rigorous and logically sophisticated (a proof by contradiction, after all) yet one of the few rigorous mathematical proofs totally accessible to a layperson. In fact I think we should take great care in crafting this proof to be as clear and accessible as possible. One suggestion already is to take out the notation for "does not divide", simply using those words instead (it only happens once after all). The current version is a bit on the terse side; I think moderate expansion would help it.
; Rename "Locating primes" to "Determining whether a number is prime"...
: ... and also include subsections describing Fermat's "difference of squares" method and the Fermat's Little Theorem test (necessary condition) for primality. These can be introduced by commentary to the effect that roundabout ways of testing primality can be paradoxically more effective in practice. (By the way, in the typesetting of the sieve of Eratosthenes diagrams, the horizontal strokes that indicate composite numbers are exactly the same height, on my browser at least, as the horizontal bar of the digit 4. The effect is that 4 itself doesn't look crossed off. This exact phenomenon was present in the typesetting of my Ph.D. thesis! Can another crossing-off indicator be employed?)
; In "Unsolved problems", add the old chestnut conjecture that there's always a prime number between consecutive squares.
: Another possibility, though less well-known outside of number theory circles, is the conjecture that there are infinitely many primes of the form n^2+1. (Really this can be extended to just about all irreducible polynomials.) We should also describe Mersenne primes (related to perfect numbers) and Fermat primes (related to constructible regular polygons), both of which correspond to unsolved problems about whether there are infinitely many or not (experts seem to believe yes and no, respectively). I'm unsure whether that's best done in this article or in articles created for those purposes ... maybe the latter (in which case mentions and links should still be put in this one).
; Add the following fantastic quote somewhere! (maybe in the suggested separate article on the distribution of prime numbers?)
: "It is evident that the prime numbers are randomly distributed but, unfortunately, we don't know what 'random' means." - R. C. Vaughan
 
I'm pretty sentimental about prime numbers, whence the length of the above commentary - but they're so cool, it's impossible not to want this article to be fantastic! It's well on its way; keep up the great work. - [[User:Greg Martin|Greg Martin]] 01:12, 25 April 2007 (CDT)
 
::Greg, you are able to make the changes you suggest above as editor, yourself. If you feel these are best incorporated before you can nominate the article for approval- I urge you to do so. [[User:Nancy Sculerati|Nancy Sculerati]] 09:37, 29 April 2007 (CDT)
 
:::I'm not sure about that.  An approving editor is not supposed to have been significantly involved in authoring the article, I think, so sometimes it may be worthwhile to step back and let others make the suggested changes so that one is available to approve the article.  An editor might not necessarily want to tread as close as possible to that line, either.  Or might prefer that others do it for other reasons. --[[User:Catherine Woodgold|Catherine Woodgold]] 09:48, 29 April 2007 (CDT)
 
Catherine, you bring up an important issue  that deserves explicit discussion. In this case, since Greg Martin has reviewed a highly developed article written by ''others'' - and done so consistently in the role of editor, he certainly is not only ''allowed'' to make ''editorial'' changes in the actual article in order to finalize the version needed for approval (especially in the exact manner he has done so here, after open discussion with the authors on the talk page), ''as'' an editor - he is ''expected'' to do so. That's what editors do. On the other hand, just as you insinuate, it is mandatory that an author who happens to also be an editor does ''not'' write an article in his or her workgroup and then nominate his or her own work for approval. That's the "legal theory" (if you will) behind the "nominating editor cannot be author" rule. And it is part of the quality assurance mechanism at CZ, it is not primarily an instrument that serves to ensure user participation, but one that serves the readers of the articles by disallowing an article that is not actually checked by another pair of expert eyes over the ones that constructed the article.  If all of the available mathematics editors had a major hand in the generation of this article from a stub to a developed article, then (as was true for the first approved version of the first approved article [[Biology]]), three of the primary author/editors would have to agree to nominate for approval. Since we do not ''have'' 3 active math editors, that would be trouble, and no stable version could be approved at this time, as you rightly suggest. But one reason that the position of Approvals Management Editor was created was to put judgement to work to help facilitate the approvals process. In this case, there is no doubt in my mind- '''NONE'''- that Greg Martin is acting strictly within the bounds of editor on an article that was created and extensively developed by others. In no way is this ''his'' article that he is nominating for approval, except in the sense that he has edited it - which is, of course, exactly what an editor anywhere does: edit. What this article is, by  the way, is a credit to ''all'' of you, as far as I'm concerned, and particularly to Greg Woodhouse - and, of course, to CZ.  Good work! :-) [[User:Nancy Sculerati|Nancy Sculerati]] 22:59, 29 April 2007 (CDT)
 
== Targeted audience ==
I'm not a mathmetition and wouldn't say a bad word about the fine work in the article but ..... Who does the article target?  Certainly not a grade school student, looking for reliable information about Prime Numbers.  Would a Junior High Schoool student benefit?  A high school student?  An average citizen?  Some level of education is needed to appreciate the article, who is the audience?  As the article displays itself, the first thing that attracts my eye is 12 square blocks.  12 isn't prime, 4 isn't prime, but finally I see a character, "3" which I know is prime.  So, I read the <nowiki>==Definition==</nowiki> and it is full of symbols I don't know. I stop right there but I see there are lots more symbols I don't know and have never heard of.  Impressive? '''YES'''.  Useful, user friendly ?  I'm not enthused, but I'm only one person. [[User:Terry E. Olsen|Terry E. Olsen]] 08:33, 29 April 2007 (CDT)
:I moved things around a bit, to put the part about infinitely many primes closer to the beginning of the article, because it's easier to understand than some other parts of the article, as Greg Martin pointed out.  I also added a few words to explain the notation in some places.  Maybe we need an article "mathematical notation" which lists the meanings of all the symbols used in all the math articles.
:I like what user dlehavi said in the forum:  "Keep in mind three audiences when writing an article: general readers, math students and professionals." [http://forum.citizendium.org/index.php/topic,620.0.html].  I think it's good to aim for as broad an audience as possible.  When it's possible to make it easy to understand and also provide information concisely enough that professionals don't have to wade through a lot of stuff they already know, that's the way to go in my opinion.  (Professionals don't always remember everything from school, either, though). However, it's not always possible to please everyone, and I believe Citizendium articles are supposed to be "pitched at the university student level" [http://en.citizendium.org/wiki/CZ:How_to_get_started_with_the_Citizendium_pilot].  I interpret this to mean a typical university student -- that is, math articles should not be aimed only at students specializing in math;  on the other hand, a university student who has studied a lot less math than the typical student may be left behind, but only if necessary and with regret. --[[User:Catherine Woodgold|Catherine Woodgold]] 09:35, 29 April 2007 (CDT)
 
== Conjecture ==
Greg Woodhouse added this in the conjecture section, and I changed the wording to the following to indicate that it is a conjecture (which I presume it is, based on where it was put):  ''"It has not been proved whether there are infinitely many primes of the form <math>n^2 + 1</math>.  (Not all numbers of this form are prime, but some are.)"''  Are you sure you mean <math>n^2 + 1</math> and not <math>2^n + 1</math>?  Do we say "proven" or "proved"?  --[[User:Catherine Woodgold|Catherine Woodgold]] 10:36, 29 April 2007 (CDT)
:Yes, I meant n^2 + 1, though I'm taking Greg Martin's word for it on this one. It seems strange to me that this could not be true, given that y = x^2 + 1 describes a curve of genus 0, meaning it is rationally equivalent to a line, and it's already known (Dirichlet) that there are infinitely many primes in an arithmetic progression (where a and b are coprime, of course). [[User:Greg Woodhouse|Greg Woodhouse]] 10:57, 29 April 2007 (CDT)
::The way the article now stands, the sentence "There are ininitely many primes of the form <math>n^2 + 1</math>", besides having a spelling error, is listed under "Some unsolved problems" but is stated as if it's known.  This leaves the reader wondering whether this is a statement which has been proven, or not.  Similarly for the statements about Mersenne and Fermat primes, modulo the spelling error.
::OK, I'm confused.  I said I had changed the wording, but perhaps I hadn't.  Anyway, my point is it needs to be changed:  are these statements known, or not?  --[[User:Catherine Woodgold|Catherine Woodgold]] 11:23, 29 April 2007 (CDT)
 
:No, they are all conjectures. [[User:Greg Woodhouse|Greg Woodhouse]] 11:26, 29 April 2007 (CDT)
 
I verify that n^2+1 is intended, although 2^n+1 is a separate and equally interesting conjecture. Also, my dictionary says that both "proved" and "proven" are valid. I'd probably use "proven" myself, but I don't mind either one. - [[User:Greg Martin|Greg Martin]] 19:38, 29 April 2007 (CDT)
:I like "proven".  --[[User:Catherine Woodgold|Catherine Woodgold]] 19:40, 29 April 2007 (CDT)
 
== Introduction ==
 
Personally, I don't like the introduction, because it's not an introduction. The first two paragraphs are a (well readable) definition, but should, in this length, go to the first paragraph below the contents, titled "Definitions". The third paragraph is a good start for an intro, but perhaps should be wrangled to answer the following questions short, but well readable:<BR>
1) What is a prime number?<BR>
2) Which science does it belong to and how does it fit into this science?<BR>
3) Why are prime numbers so important and well researched?<BR>
Or in other words: Why should I as a "mathematical end user" read the rest of the article?<BR>
 
Generally speaking, this article should become an example for others as, especially in nature sciences and computers, the "end user" is often forced to read encyclopedic articles that feel like science papers.--[[User:Jens Mildner|Erkenbrand]] 14:38, 2 May 2007 (CDT)<BR>(Uh, I thought Erkenbrand was my login name only??)
 
 
----
 
Found this a nice and clear article - but in the lead - "evenly divided" to me seems a rather unclear descriptor.[[User:Gareth Leng|Gareth Leng]] 04:01, 3 May 2007 (CDT)
 
== Unique factorization property ==
 
I rewrote the definition of unique factorization a bit. I think Catherine's change was on the right track, but since sets don't have repeated elements, it wasn't technically correct. There didn't seem to be a simple rewording that would work, though, so I sent ahead and rewrote the paragraph. [[User:Greg Woodhouse|Greg Woodhouse]] 21:55, 3 May 2007 (CDT)
:Good catch.  I was thinking about how it doesn't matter if you reorder things in sets, but I forgot about the repeated elements. Looks OK now. You're right, it's not easy to say.  --[[User:Catherine Woodgold|Catherine Woodgold]] 07:24, 4 May 2007 (CDT)
 
== Deletete analogy of primes and chemical elements? ==
 
This one sentence seems to be a bit of an orphan and (at least now) it disrupts the flow of the article. Can we just delete it? [[User:Greg Woodhouse|Greg Woodhouse]] 21:57, 3 May 2007 (CDT)
 
:I hope this sentence won't be deleted.  I like it (or something espressing a similar concept).  Erkenbrand said the introduction should say why prime numbers are important.  This sentence is an answer to that question.  Rather than deleting, I might expand it:  ''Because of this, prime numbers play a role in arithmetic analogous to that of atoms in chemistry:  every positive integer > 1 can be built up from the primes using multiplication."'' or something similar.  --[[User:Catherine Woodgold|Catherine Woodgold]] 07:28, 4 May 2007 (CDT)
 
Hmm... Well, I guess there are really two issues then. My original concern was that the sentence caused an unnatural break in the narrative, but that could be addressed by moving it to somewhere else. But now that I think about it, I'm not even sure that I agree with what is being said. Primes do provide a notation independent way of decomposing integers, but is that ''really'' why they are important? I need to think about that one and come back to it later, but my point of view is something a little different but close: Primes correspond to "simple" objects (like simple groups in group theory). [[User:Greg Woodhouse|Greg Woodhouse]] 09:09, 4 May 2007 (CDT)
 
:In classical chemistry, atoms were introduced (and so named, even) because they too are "simple" (i.e., indecomposable) objects. In fact there's really no difference between "a way to decompose widgets" and "a simple widget", since the former is defined in terms of the latter. ... Anyway, that being said, I agree that the atom sentence is a bit flow-disrupting. Improvements welcome! - [[User:Greg Martin|Greg Martin]] 23:40, 4 May 2007 (CDT)
 
== Another characterization ==
 
I wonder whether the beginning of this ''" Another characterization is that a prime number p cannot be factored as the product of two numbers..."'' could be changed to ''"In other words, a prime number p..."'' The two characterizations seem just about equivalent to me.  Maybe something more neutral:  ''"Another way of describing them is"'', ''"Another definition is"'' or ''"This means that..."'' or ''"Equivalently,..."''  The trouble with "another characterization" is that it raises the expectation that a significantly different definition will be given (e.g. one that might describe different objects than the other definition in some rings), and then I'm disappointed to see practically the same definition expressed in different words.  --[[User:Catherine Woodgold|Catherine Woodgold]] 07:34, 4 May 2007 (CDT)
 
:That's a good point. I changed it to "Another way of saying this..." [[User:Greg Woodhouse|Greg Woodhouse]] 08:49, 4 May 2007 (CDT)
 
::I agree that the two characterizations are very close to each other, so I'm wondering whether we really need them both. Another issue is that 1 is a prime according to the second characterization (a number which cannot be factored ...). -- [[User:Jitse Niesen|Jitse Niesen]] 09:01, 4 May 2007 (CDT)
 
::: Here's my reasoning for including both versions: The first sentence is the complete formal definition. But the "can't be unboringly factored" version is the version that's implicitly used in the rest of the introduction - read for example the reason why 9 and 15 aren't prime, or look at the caption of the rectangles figure: both refer to factorizations, not divisors. [[User:Jitse Niesen|Jitse]] raises a good point that the second version doesn't rule out 1; but (depending on the beginning of the sentence) the second version doesn't purport to be an if-and-only-if statement. Maybe starting the sentence with "In particular," would make that point clear, as well as mitigate the critique above. I'll give it a try. - [[User:Greg Martin|Greg Martin]] 23:51, 4 May 2007 (CDT)
 
"In other words" is definitely the wrong thing to say.  That the second characterization follows from the first is far too far from obvious for that.  It takes some work to prove it. [[User:Michael Hardy|Michael Hardy]] 13:22, 9 May 2007 (CDT)
 
== what's "this"? ==
 
General writing-style point: using "this" as a pronoun. In the version I'm about to edit, there are four instances of this ailment in the introduction alone:
* Another way of saying this is ...
* Because this is a bit complicated to say, ...
* Because of this, prime numbers ...
* While this used to be the case, ...
I won't assert an unbreakable rule, but in general: using "this" to refer to "an unspecified amount of stuff I just got done saying" tends to lead to vague-sounding prose - partially because of the pronoun itself, but also because we writers who allow ourselves to use this "this" are usually struggling with a concept we're having trouble phrasing well, or with a way to write a transition from one sentence to another, and the "this" lets us off the hook. - [[User:Greg Martin|Greg Martin]] 23:47, 4 May 2007 (CDT)
 
== Existence of at least one prime factorization==
There's something missing in the proof that there are infinitely many primes.  It is made to depend (unnecessarily) on the proof of unique factorization.  But the proof given on the unique factorization page proves only that there are not two different factorizations. It does not prove that every number has at least one prime factorization, which is the part of the proof that the "infinitely many primes" proof depends on.  So that part is missing from both pages. 
One way to fix this would be to replace this:
:''On the other hand, every number N > 1 is divisible by some prime (in fact, it factors completely into prime numbers, due to unique factorization).''
with something like this:
:''Now, <math>N</math> must be either prime, or divisible by some number less than itself.  That number, in turn, must be either prime or divisible by an even smaller number.  Continuing in this way, since the number of numbers between 0 and <math>N</math> is finite, we must eventually reach a prime number <math>q</math> which divides <math>N</math>. Since none of the primes <math>p_1, p_2, \cdots p_n</math> divide <math>N</math>, <math>q</math> must be a prime that was not already included in that list.  This contradicts the hypothesis, therefore proving that the list of primes is not finite.''
An alternative would be to include, on the unique factorization page, a proof that every number has at least one factorization into prime numbers. --[[User:Catherine Woodgold|Catherine Woodgold]] 07:43, 5 May 2007 (CDT)
 
:True observation. I think this would go better on the unique factorization page. - [[User:Greg Martin|Greg Martin]] 04:30, 6 May 2007 (CDT)
 
::Perhaps.  Remember, though, that this proof (infinitude of primes) is supposed to be an excellent example of a rigourous proof that's accessible to the layperson.  The unique prime factorization proof (as a whole) is more complex.  So having this proof depend on something on another page which contains a more complicated proof (or having it depend on another page at all) is not necessarily a good idea.  However, the layperson might just accept that every number has at least one prime as a factor -- maybe it wouldn't bother them.  But then maybe that's just teaching them to keep on accepting what they're told, rather than seeing how real math proofs work.  Also, if referred to another page, the reader is likely to be confused about whether there's any difference between proving uniqueness of prime factorization and proving that there is at least one prime factorization.  (Apparently we writers were confused on this point.)  On another note, I think it's good to say something like "N is either prime itself, or has at least one prime factor less than itself" i.e. mentioning the two cases of N being prime or not.  (I can't find a good way to word that, though.)  I just find that this helps to get a clearer image in the mind, though it's not necessary to break it into two cases for a rigourous proof.  All that said, the current version is OK and possibly best. --[[User:Catherine Woodgold|Catherine Woodgold]] 08:53, 6 May 2007 (CDT)
 
== Connecting up mention of the prime number theorem ==
 
In the section "There are infinitely many primes", it says ''"One mathematical milestone known as the [[Prime Number Theorem]] estimates how many of the numbers between 1 and <math>x</math> are prime numbers: approximately <math>x/\ln x</math> of them are."''  This idea is treated in much more detail, and with a different logarithm notation, in a later section.  Possible edits could include:  Append ''"(See [[Prime number#Distribution of prime numbers|below]])"'';  change the log notation to match that used below and append a footnote or parenthetic remark defining it as the natural logarithm and linking to the logarithm page;  (or append such a remark while keeping the ln x notation);  Shortening this mention to ''"One mathematical milestone known as the [[Prime Number Theorem]] estimates the distribution of prime numbers (see [[Prime number#Distribution of prime numbers|below]])"''.  --[[User:Catherine Woodgold|Catherine Woodgold]] 18:23, 5 May 2007 (CDT)
 
:You couldn't be more right! I implemented your last suggestion. - [[User:Greg Martin|Greg Martin]] 04:32, 6 May 2007 (CDT)
 
== Are we there yet? ==
 
Shall a constable place the approval tag? It is May 6, unless I hear otherwise, I will contact a constable to do so. Should the editors wish to do so, on their own, I encourage them to proceed. [[User:Nancy Sculerati|Nancy Sculerati]] 16:20, 6 May 2007 (CDT)
 
:I'm the editor, but in my opinion most of what is happening here (and over on the [[Complex number]] article) is in the nature of attempts to improve the wording or make other minor changes, nothing that needs to happen before version 1. [[User:Greg Woodhouse|Greg Woodhouse]] 16:53, 6 May 2007 (CDT)
 
==APPROVED Version 1.0==
<div class="usermessage plainlinks">Discussion for [http://en.citizendium.org/wiki?title=Prime_number&oldid=100097398 Version 1] stopped here. Please continue further discussion under this break. </div>
 
== Highly misleading phrase ==
 
The approved version of this article says:
 
:: in fact, it factors completely into prime numbers, due to unique factorization
 
That is very misleading at best.  It implies that '''uniqueness''' rather than '''existence''' of the factorization is what entails that a number factors completely into primes.  That is clearly false.  Even in structures within which factorization is not unique at all, elements still factor completely into primes.  Possibly the most well-known example is the ring of integers with a square root of &minus;5 adjoined. [[User:Michael Hardy|Michael Hardy]] 11:37, 7 May 2007 (CDT)
 
That's right. I'm not sure how the argumnt for the existence of a factorization was removed (I'm pretty sure it was there), though I imagine it may have been a casualty of the removal of proofs. But since Z is Euclidean, we really only need use induction on absolute value. [[User:Greg Woodhouse|Greg Woodhouse]] 11:47, 7 May 2007 (CDT)
 
Hmm...Now that I take a second look, the article doesn't really assert that existence follows from uniqueness, but merely notes that the factorization is, in fact, unique (citing another article). That doesn't strike me as being misleading. [[User:Greg Woodhouse|Greg Woodhouse]] 12:00, 7 May 2007 (CDT)
 
:: What does "factors completely into prime numbers" mean, if not '''existence'''?  How could "factors completely into prime numbers" follow from '''uniqueness'''? [[User:Michael Hardy|Michael Hardy]] 19:00, 7 May 2007 (CDT)
 
I think Michael Hardy has a good point.  I had raised a similar point previously, and I find the way it's expressed in the approved version somewhat unsatisfactory.  The current draft version may be somewhat better but only if the required (clear) statement and proof are actually contained in the unique factorization page; (which it isn't at the moment);  it's still not ideal even then, because it creates confusion between the two propositions (existence of a factorization, and uniqueness of it.)  How about this edit:  making the link to unique factorization a casual link rather than a "see ...":  ''"On the other hand, every number <math>N>1</math> is divisible by ''some'' prime (in fact, it [[Unique factorization|factors completely]] into prime numbers)."''  Again, the required statement and proof would have to be included on the unique factorization page.  My preference, actually, is to have the complete proof of an infinitude of primes contained on the prime page, as I argued above.  --[[User:Catherine Woodgold|Catherine Woodgold]] 18:35, 7 May 2007 (CDT)
 
:That would be my preference, too. Originally, I tried to prove everything (though I hope I didn't fall into a boring Bourbaki style, as Sébastien would say), but there semed to be a strong consensus in favor of moving the proofs out of the article. In this  case, it doesn't seem to be that the proof itself is all that daunting. Since a proper divisor must be greater than 1, if n is not irreducible, then it must have a proper divisor that is smaller in absolute value. Repeating this process, we can factor n as a product of irreducibles. Now, the point of contention, and what is not so obvious is that irreducible elements are also ''prime''. This is so because <math>\mathbb{Z}</math> is a PID (proved using the division algorithm). Certainly, we can prove that irreducibles are prime without saying anything about principal ideal domains, but it is true that this is a subtle point that appears almost immediately, and it really can't be avoided except by asking the reader to take this result on faith (at least temporarily). I'm certainly open to suggestions as to how this difficulty might be avoided. [[User:Greg Woodhouse|Greg Woodhouse]] 19:06, 7 May 2007 (CDT)
 
::Easy.  The definition of prime given in the first sentence is "A prime number is a whole number that can be evenly divided by exactly two numbers, namely 1 and itself."  I think that's what you mean by irreducible;  anyway, either the number is prime, or it is divisible by another number (which evidently must be smaller than itself).  --[[User:Catherine Woodgold|Catherine Woodgold]] 19:14, 7 May 2007 (CDT)
 
::OK, I've found a concise way to complete the proof without referring to unique factorization or to another page, and I've boldly edited it into the draft:  ''"(for example, its largest divisor greater than 1 must be a prime)"''.  Details that the reader has to fill in (if that one is astute enough to realize that they need to be filled) are that the number N must be greater than 1;  that it must have at least one divisor greater than 1 (because it divides itself);  and that if a number divides a divisor of N then it must also divide N (by associativity of multiplication).  I think it's OK to gloss over these details.  I hope the rest of you will feel free to change it again if necessary. --[[User:Catherine Woodgold|Catherine Woodgold]] 07:26, 8 May 2007 (CDT)
 
Unfortunately, that doesn't quite work (consider the case of 8). I went in an added a different argument (which you are welcome to revert), but now it occurs to me that perhaps you meant the ''smallest'' proper divisor must be prime. [[User:Greg Woodhouse|Greg Woodhouse]] 08:21, 8 May 2007 (CDT)
 
:Right:  I meant "smallest".  It now says this:  ''" (To see why, let q be the smallest divisor of N; any proper divisor of q would be a smaller divisor of N, so q must be prime.)"'' which is pretty much what I meant, but I think my version is easier for the reader to follow -- my version doesn't seem to be adding more steps.  Also, I mention "greater than 1" which is left out in that version, making it not quite rigourous.  I suggest changing to this:  ''"(for example, its smallest divisor greater than 1 must be a prime)"''. --[[User:Catherine Woodgold|Catherine Woodgold]] 20:20, 8 May 2007 (CDT)
 
:I edited in my suggestion above.  There are two problems with the current nominated version.  First of all, it is incorrect.  It says ''"To see why, let q be the smallest divisor of N; any proper divisor of q would be a smaller divisor of N, so q must be prime."''  The smallest divisor  of N is 1.  We can implicitly assume that <math>N>1</math>, but we can't say "smallest divisor" when we mean "smallest divisor greater than 1" and claim the proof is correct.  The other problem is this:  Greg Martin has called this proof "one of the few rigorous mathematical proofs totally accessible to a layperson."  Let's not mess that up.  The current nominated version uses a quick little implicit, abbreviated proof-by-contradiction in this part, making it a proof-by-contradiction within a proof-by-contradiction.  I don't think this is accessible to someone who is just being introduced to proof-by-contradiction for the first time.  I think the concise version ''"for example, its smallest divisor greater than 1 must be a prime"'' is accessible.  --[[User:Catherine Woodgold|Catherine Woodgold]] 07:30, 9 May 2007 (CDT)
 
::Good point that we have to add "greater than 1".
::I'm not very happy with the way the footnote is formulated. I moved some parts around because I found the phrase "To see why <math>N</math> has a smallest divisor greater than 1, call it <math>q</math>, which must be a prime:" too complicated. The word "then" in the last sentence seems out of place. I don't like having a remark in a footnote in a parenthetical remark; it seems a bit too much. Perhaps it's better to have it in the main text. After "We conclude that there are infinitely many prime numbers", we something like: "Actually, if we study the proof carefully, we notice that there is something missing". It's a way to show what rigour means. On the other hand, this may be better in an article about [[mathematical proof]]. Finally, I think that the proof that Catherine outlines in her 07:43, 5 May 2007 (CDT) remark.
::But this all requires more thought and discussion. Given the time pressure (and the fact that it's past midnight here), it's probably best to focus on having no mistakes.
::Oh yes, I updated the template so that the current version is nominated. -- [[User:Jitse Niesen|Jitse Niesen]] 10:19, 9 May 2007 (CDT)
 
== Historical remark regarding 1 ==
 
The introductory material says that one time mathematicians often ''did'' consider 1 a prime. I don't necessarily doubt this, but I've never heard this claim before, either. Does anyone have a reference? In any case, I think prime (as opposed to irreducible) is a relatively modern concept. [[User:Greg Woodhouse|Greg Woodhouse]] 11:55, 7 May 2007 (CDT)
 
:MathWorld [http://mathworld.wolfram.com/PrimeNumber.html says] "the number 1 used to be considered a prime (Goldbach 1742; Lehmer 1909; Lehmer 1914; Hardy and Wright 1979, p. 11; Gardner 1984, pp. 86-87; Sloane and Plouffe 1995, p. 33; Hardy 1999, p. 46)". [[User:Fredrik Johansson|Fredrik Johansson]] 12:00, 7 May 2007 (CDT)
 
:Okay, thanks. Maybe we can include a reference or two into the article. This is something that makes sense historically, but is likely to be something of a surprise to a modern reader. On second thought, maybe it would be preferably to say something along the lines of, "the modern definition of prime number requires that primes be > 1". I don't think I want to get too involved in discussing ''why'' 1 is not considered a prime, but neither do I want to give undue prominence to the idea of older mathematicians thinking of 1 as a prime, unless of course, we really want to grapple with the concepts of primes vs. irreducibles early on, and that, too, is problematic. [[User:Greg Woodhouse|Greg Woodhouse]] 19:20, 7 May 2007 (CDT)
 
Could it be that some ancient Greeks did not consider 1 a prime number for the simple reason that they did not consider 1 a number? [[User:Michael Hardy|Michael Hardy]] 18:56, 7 May 2007 (CDT)
 
:I have no clue. As I said before, the history of mathematics isn't my strong point (or even close, really). [[User:Greg Woodhouse|Greg Woodhouse]] 19:20, 7 May 2007 (CDT)
 
== Huh? ==
 
This has been added to the "draft":
 
:: ...
:: consider that if we divide there arer any divisors other than the number itself and 1,
:: ...
 
"there arer"?  I'm trying to figure out what this sentence means, but I'm stumped. [[User:Michael Hardy|Michael Hardy]] 15:13, 8 May 2007 (CDT)
 
:Ugh! I'm sure I'm responsible for that. I like Catherine's suggested proof (take a minimal divisor) better, anyway, so rather than try to reconstruct the garbled text, I've replaced it with Catherine's proposal. I just hope I got ''that'' right! [[User:Greg Woodhouse|Greg Woodhouse]] 17:20, 8 May 2007 (CDT)
 
== Scriptstyle? ==
 
I thought the more-or-less consensus on the forum was that we should not put "scriptstyle" in a lot of the TeX code to make it look nicer;  that that's not what "scriptstyle" is for.  My own opinion is that it's better to just put math tags and leave it up to the browser to decide how to display it.  I think it makes sense to decide these things by discussion and come up with guidelines to be used on all the math pages. --[[User:Catherine Woodgold|Catherine Woodgold]] 20:24, 8 May 2007 (CDT)
 
That was my understanding, too. I don't know much about the MediaWiki software, but I wonder how hard it would be to create a new tag, say <nowiki><imath>...</imath></nowiki> for inline formulas. We could use the new tag for formulas that are displayed inline, and that way the authors won't have to be concerned with the method actually used to acvhieve (some degree of) consistency in font size. To tell you the truth, the single most frustrating thing about this approval process was the controversy over <nowiki>\scriptstyle</nowiki> - one person woul come along and say "put it in", and then someone else would say "take it out". I wasn't a happy camper. Now, personally, I come down on the "use <nowiki>\scriptstyle</nowiki> for its intended purpose" side of the argument, but more importantly, I don't want to be always going back and forth. On top of that, typng isn't really that easy for me, particularly with my left hand, so having to type<nowiki> \scriptstyle</nowiki> ''over and over'', when someone else likely to come along and take it all out isn't exactly fun. [[User:Greg Woodhouse|Greg Woodhouse]] 20:45, 8 May 2007 (CDT)
 
I think this is an issue that the mathematics workgroup--meaning, mathematics editors--need to deliberate about and then ACTUALLY VOTE on.  See if you can get a quorum to discuss and vote, so that a decision can be said to be ''made'' and to have credibility.
 
I am in favor of using the best tool for the job.  If that means using tools in ways that aren't their intended purpose, big deal.  Sorry, call me a philistine.  I never cared about how H1-H6 were ''intended'' to be used in HTML, either.  I ''greatly'' prefer the aesthetics of the use of <nowiki>\scriptstyle</nowiki> in my browsers of choice.  If most browsers (IE and Firefox notably) ''don't'' display plain TeX properly, and if this problem isn't going to be fixed anytime sooner, I think we ought to be pragmatic.  I realize that this is asking a lot for certain mathematicians, who prefer simple and elegant solutions over messy and pragmatic ones, but that's my opinion, anyway.
 
This is just my own nonbinding opinion, and I think the decision ought to be left up to the mathematics workgroup. --[[User:Larry Sanger|Larry Sanger]] 20:54, 8 May 2007 (CDT)
 
P.S. Why not use cz-math (the mailing list) to ask for opinions? --[[User:Larry Sanger|Larry Sanger]] 20:56, 8 May 2007 (CDT)
 
P.P.S. Can we please have a volunteer who will corral our math editors and extract opinions/votes on the "scriptstyle" issue, and count votes? --[[User:Larry Sanger|Larry Sanger]] 21:04, 8 May 2007 (CDT)
 
Nobody has proposed \scriptstyle for "displayed" [[TeX]], but only for "inline" TeX in those cases where the font looks ridiculous when \scriptstyle is not used.  Please see [[CZ talk:Mathematics Workgroup]], where some discussion has been going on for a few weeks. [[User:Michael Hardy|Michael Hardy]] 13:26, 9 May 2007 (CDT)
 
'''I've been bold and started an article called [[CZ:Formatting_mathematics]], the purpose of which is to gather together all debates and policies related to formatting mathematics in Citizendium articles.''' I've put enough content there to suggest the format I have in mind: one main article with the statements of policies, proposed policies, and issues under discussion; and for each item, a subsidiary article with a detailed discussion of the issue, so that people will know why the policies that are (eventually) decided upon are the way they are (I fleshed out [[CZ:Formatting_mathematics/Theorem_capitalization|one such discussion article]] to give a sense of what I have in mind). I hope that this creation has value for our workgroup! If so, please feel free to develop the skeleton I put there. - [[User:Greg Martin|Greg Martin]] 16:26, 10 May 2007 (CDT)
 
==APPROVED Version 1.1==
Congratulations on V1.1!  --[[User:D. Matt Innis|Matt Innis]] [[User talk:D. Matt Innis|(Talk)]] 19:35, 10 May 2007 (CDT)
<div class="usermessage plainlinks">Discussion for [http://en.citizendium.org/wiki?title=Prime_number/Draft&direction=next&oldid=100099364 Version 1.1] stopped here. Please continue further discussion under this break. </div>

Latest revision as of 16:22, 27 November 2008

This article has a Citable Version.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
To learn how to update the categories for this article, see here. To update categories, edit the metadata template.
 Definition A number that can be evenly divided by exactly two positive whole numbers, namely one and itself. [d] [e]
Checklist and Archives
 Workgroup category Mathematics [Please add or review categories]
 Talk Archive 1, 2  English language variant British English

What kind of number

The first sentence doesn't specify what kind of numbers we are dealing with. Andres Luure 22:26, 5 November 2007 (CST)

It says "A prime number is a number that can be evenly divided by exactly two positive whole numbers, namely 1 and itself." The word "itself" implies it must be a positive whole number. (But maybe it could be more explicit.) Michael Hardy 14:03, 20 December 2007 (CST)
And why not be more explicit? It seems much clearer to me, a number theorist even, if you say "a prime number is a positive whole number that can be evenly divided by exactly two positive whole numbers, namely 1 and itself". In the original version, I didn't immediately return to the beginning of the sentence and think, "oh, that IMPLIES that the original number was a positive whole number". If the only concern is that repeating the same phrase twice might be a turn off, let me quote from Strunk and White's "Elements of Style", one of the guides to style that we are supposed to take advice from (see section 19) "The likeness of form enables the reader to recognize more readily the likeneses of content and function...the unskilled writer often violates this principle mistakenly believing in the value of constantly varying the form of expression. When repeating a statement to emphasize it, the writer may need to vary its form. Otherwise, the writer should follow the principle of parallel construction." It seems to me that the repetition in our case is not for emphasis, and after the repetition, it will be firmly fixed in the reader's mind that all numbers begin considered are positive whole numbers.Barry R. Smith 20:40, 29 March 2008 (CDT)

I am not sure it is even clear to say "exactly two" when it could be "two and only two." --Thomas Simmons 19:56, 8 November 2007 (CST)

In mathematics, at least, the phrases "there are exactly two" and "there are precisely two" are understood to express the same statement as "there are two, and only two" (for instance, see the discrete math text I taught out of this past term, or the Wiki page on if and only if). I have considered these as equivalent for many years, so it is hard for me to put myself in the shoes of someone who might be seeing this for the first time. The issue that you are concerned with is that someone might accidentally confuse "exactly two" with the idea that it has at least two, but possibly more, positive divisors. I cannot see how even people with very little mathematical experience would interpret "exactly two" in this manner, the word "exactly" being inserted exactly (hehe) to let you know that this is the precise number. Furthermore, I think it is hard to argue against "exactly two" being the more elegant phrase. I much prefer the phrasing of the first sentence of the approved article to the first sentence of the current draft. Any rebuttals?Barry R. Smith 20:40, 29 March 2008 (CDT)
I agree. Even to naive readers "exactly two" cannot possibly mean "at least two". J. Noel Chiappa 22:12, 29 March 2008 (CDT)

Footnotes versus links to stubs: Until many of the terms are explained with their own articles, the use of footnotes to explain terms and analogies should continue. Otherwise we will have dead links in red letters for a long time to come. This will also mean that the article can reach a broader population as it is written. The chemistry metaphor is another example, that comparisons might be lost on anyone who is not up to speed on freshman level chemistry. So for ease of use and market appeal and just plain educational focus, explaining terms in footnotes would be a good idea. The high school students using CZ today will be the grad students referring to it in future.--Thomas Simmons 19:56, 8 November 2007 (CST)

What i miss

There are some things, that are not in thearticle:

--arbol01 05:04, 1 January 2008 (CST)

I don't understand the first comment under "Properties of prime numbers"
As for prime divisors of elements of those two particular sequences, it seems to me that these are far too specialized to be included in this page, and would be better placed on the "Perrin sequence" and "Lucas sequence" pages separately. Otherwise, one would need to enumerate ALL named recursively defined sequences, and the divisibility properties in each case. I would imagine that just this task would encompass many pages in itself.Barry R. Smith 00:20, 30 March 2008 (CDT)
    • p is a Prime number <=> p|(p over n) for 1<n<p
Iff p is a prime number, than p divides (p over n) [Binomialcoeffizient] for every n between 1 and p.
If p is a prime number, than p divides Pp and p divides U(P,Q)p - P
are properties, that belongs to the Prime numbers. It belongs to the Perrin sequence respectively to the Lucas requence respectively to the binomialcoefficence too. --Karsten Meyer 02:45, 19 May 2008 (CDT)

1 revisited

Regarding my above comment in "What kind of number" above, I personally feel that the first sentence should read something like, "A prime number is a whole number greater than 1 that can be evenly divided by exactly two positive whole numbers, namely 1 and itself". It seems that the main argument above against saying a prime must be bigger than 1 from the outset is the need for clarity in the first sentence, but I feel that currently this clarity comes at the price of correctness. As written, I feel the that first sentence is plain wrong, and I personally wouldn't put my stamp of approval on it.

I don't want to sound TOO dismissive. I didn't just go edit the draft, because I understand that their was some discussion about this above. Apparently, the status of 1 seems to have been problematic even when the fundamental of arithmetic were laid down in Euclid's "Elements". However, it seems to me that the tone of the approved version suggests that the typical modern "choice" to label 1 as neither prime nor composite is a result of whimsy or chance. This is a false impression.

In a sense, I guess, defining 1 as special can seem as arbitrary as defining 0 factorial to be 1. But with the invention of the gamma function and the recognition of its canonical properties, can there be any dispute as to the correct definition of 0 factorial? Similarly, there are very sound reasons that 1 has been given special status over the last century or so. The easiest to explain is that the Fundamental Theorem of Arithmetic is just false if 1 is considered prime: considere, 6 = 2*3 = 2*3*1 -- two different prime factorizations. (By the way, I also think that the words "Fundamental Theorem of Arithmetic" should appear somewhere on the "prime number" page -- can't remember if I saw it anywhere). A second reason is that with the development of algebraic number theory, the units in algebraic number fields were found to play a very special and important role. Within the integers, 1 and -1 are the only units, so it is hard to get a feel for the special role they play only within this context. Nevertheless, the fact that 1 is the unique multiplicative identity within the integers should make a strong impression. (For more about 1, see this website http://mathforum.org/kb/message.jspa?messageID=1379707, and especially the comments by John Conway, a world-renown number theorist.)

In summary, although the status of 1 might have fluctuated in the past, I believe the consensus of the vast majority of working mathematicians at present is that it should not be considered prime, and this is reflected in todays high-school textbooks. Furthermore, I do not see any indication that this will change soon. Thus, it seems that the proper definition should make it clear that 1 is not prime from the first sentence. Otherwise, we will be spreading disinformation to those casual learners who wonder, "hmm, I wonder if 1 is a prime", look at the first line of the Citizendium page, and then wander off to tell their friends what they learned.Barry R. Smith 01:31, 30 March 2008 (CDT)

Dude, you're the expert! I (at least, can't speak for everyone) defer to your clear familiarity. So I'd go for it. Plus to which, your point about the Fundamental Theorem of Arithmetic is good (and so easily understandably by all that it should probably be mentioned in the article as a reason why 1 is not considered by mathematicians as being part of the set of prime numbers, even though by the simplistic definition of 'prime', it seems to be prime). J. Noel Chiappa 11:40, 30 March 2008 (CDT)
Barry, the first sentence currently says "A prime number is a positive whole number that can be evenly divided by exactly two positive whole numbers, namely 1 and itself." I believe this does say that 1 is not prime, just as you want, as the number 1 has only one divisor, namely 1 itself. So I'm not sure what your point is.
I agree with all the rest you wrote (for what it's worth, as you know of course more number theory than I do). -- Jitse Niesen 16:00, 30 March 2008 (CDT)
Someone careful and analytic might draw that conclusion, but not all our readers might fit that definition. Baldly saying '1 is not a prime number' is probably what they need. Without in any way intended to be demeaning to them, I am always mindful of that wonderful George Carlin line: "Think of how dumb the average person is - and then realize that half of them are dumber than that."
(Adding "different" - as in "two different positive whole numbers" - might make the definition cast-iron, though). But it might still be useful to have a section on 'why 1 is not a prime number'; the point about the Fundamental Theorem of Arithmetic could go there. J. Noel Chiappa 23:31, 30 March 2008 (CDT)
Yes, Jitse, it seems that after all of that, I understand 1 okay but I still have trouble counting to 2 :-). Anyway, my own error emphasizes the point that inferring information about the prime number from information presented at the END of the sentence is not my own thought process, and probably not a lot of other people's. (I suppose if I still kept up my German, I would be used to that sort of thing :-) ). For instance, the end of the sentence in the approved version is where you find that the prime in question is a positive whole number, but I prefer the draft version where it comes right out and tells you that. I think a similar modification to clarify that the whole number is bigger than 1 from the outset, "baldly" saying it, as Noel suggested, is also in order. I also like your suggestion, Noel, of providing clearer reasons for 1's unique position. Would that be better as a new subsection, a footnote, or a link to a page about the arithmetic properties of 1?Barry R. Smith 22:31, 31 March 2008 (CDT)
I'd say a new subsection, not a footnote. Although I don't know where it would fit... hmmmmm (cogitates). Maybe take the third para of the intro, about factorization, and move it to a new section immediately after the intro, titled something like "Factorization and primes"; I think that's a sufficiently important aspect of primes that it's worth of a section on its own. Mention of the Fundamental Theorem of Arithmetic would go there, after which it would be natural to flow from that into your point about the FToA ruling out 1 as a prime. The existing text about "(although this is a matter of [the] definition [of a prime], and mathematicians in the past often did consider 1 to be a prime)" would naturally fit in there too. In fact, maybe a sub-section of that "Factorization and primes" section would cover the primality of 1, and although it would start with the FToA point, etc, you could add your other points above about algebraic number theory, etc. J. Noel Chiappa 00:38, 1 April 2008 (CDT)
Yes, counting is hard ;) I added "greater than 1" to the first sentence, so that's settled for now.
Noel's suggestion to have a new section on the Fundamental Theorem of Arithmetic looks like a good idea. We probably don't want to write too much on it, I think details should go at unique prime factorization or some other article, but I agree that it's important enough in this context to get a section. Indeed, the primality of 1 can covered there, though I'm not sure it should be a sub-section; how much should we say about it? -- Jitse Niesen 08:10, 1 April 2008 (CDT)
Since I'm not a mathematician, and the article is intended (mostly!) for non-mathematicians, would you like me to try the layout I suggested; you all can then check it to make sure I didn't commit any math howlers? J. Noel Chiappa 10:32, 1 April 2008 (CDT)
Sounds good to me Noel Barry R. Smith 11:40, 1 April 2008 (CDT)

OK, I've taken a crack at it. I hope you will all find the result (mostly :-) satisfactory; it seems to me (at least :-) to flow well, and in a natural progression. A couple of things where I don't have enough math knowledge to really fill in, and you all need to backstop: i) explain some about why and how the FToA is so important, ii) some of the more advanced stuff about why 1 is not a prime (in Barry's original comments in this section above) was way over my head, so I just cut-n-pasted the brief allusion here, which you all ought to expand a teensy bit (and make sure my copyediting didn't produce bogosities). Oh, also, the section on factorization should include a sentence or two about how factorization of very large numbers is a key in the crypto-system stuff we alluded to in the intro. I'm too lazy to do that - off to other things! J. Noel Chiappa 12:53, 1 April 2008 (CDT)

I think it looks great, Noel. The only concern I have is the statement that the Fundamental Theorem of Arithmetic is an important building block in many areas of number theory. Historically, the Fundamental Theorem appeared in Euclid's "Elements", the most influential math book of all time, as Proposition 14 in Book IX (This is from a secondary source). Actually, this proposition only shows that if a number n factors as n = p_1 x p_2 x p_3 x ... x p_r, where p_1, ..., p_r are DISTINCT prime numbers (i.e., n could be 30 = 2 x 3 x 5, but not 12 = 2 x 2 x 3, since 2 appears twice), then then those are the only prime numbers that appear in its factorization. Thus, this says significantly less than the Fundamental Theorem of Arithmetic, and only says something about very special types of numbers.
It wasn't until about 2000 years after Euclid that the Fundamental Theorem was codified and decisively proved, by Carl Friedrich Gauss (I have seen this claim many times, but don't have a math historian to use as a source). It seems generally believed that earlier people understood the principle of unique factorization, but perhaps there had never been a reason to try to prove it. It wasn't until larger number systems than the integers began to be considered that it was realized that the Fundamental Theorem describes a particular property of the integers. In fact, in other number systems, the analog of unique factorization FAILS to be true, which is what Gauss realized and motivated him to prove the theorem for integers. So in a sense, it is the failure of the Fundamental Theorem to be an important result in these other number systems (i.e., it's just not true) that prompted its formulation.
Does this make sense? If so, then maybe I will just stick a brief mention of some of this information in place of the statement that I objected to. In any case, besides being an assumed property of the integers that is used to build up many of the important results in Arithmetic, I suppose an answer to your question of why FToA is important is that it fails in other number systems. In response to your other question, I don't see any "bogosities" :). ...said Barry R. Smith (talk) 17:42, 1 April 2008 (Please sign your talk page posts by simply adding four tildes, ~~~~.)
Got it. My text about the Fundamental Theorem of Arithmetic, which is a key building block in many important areas of number theory was in large part a reaction to the very name - I figured anything called the Fundamental Theorem of Arithmetic had to be important! But I notice you say "besides being an assumed property of the integers that is used to build up many of the important results in Arithmetic", so perhaps I wasn't so far wrong? :-)
So, I'll change the text to say "Fundamental Theorem of Arithmetic, which is used to build up many of the important results in the area of arithmetic", and you can further tweak that to your satisfaction, to be perfectly accurate.
After thinking about it, I would suggest that this article probably isn't the place to mention how the FToA is not true in other number systems, because it's one further step removed from the article's focus, which is primes. It would also intrude into the flow from i) the mention of FToA to ii) how the FToA makes it desirable to exclude 1 from the set of primes. That observation would of course be a perfect fit in the Fundamental Theorem of Arithmetic article, though.
I'll also add that remark about how factorization is what's important in public-key crypto work. And then I leave it to you all... :-) J. Noel Chiappa 19:28, 1 April 2008 (CDT)
I do have some remarks and questions.
  1. You added the word "different" to the first sentence, so that it reads: "A prime number is a whole number greater than 1 that can be evenly divided by only two different positive whole numbers, namely 1 and itself." Is this necessary? Is there really a chance that if we remove the word "different", somebody will think that 7 is not a prime because it has three divisors, namely 1, 7 and 1?
  2. We have an article about unique factorization. Do we need a different article about the Fundamental Theorem of Arithmetic?
  3. You say that the Fundamental Theorem of Arithmetic "is used to build up many of the important results in the area of arithmetic." I would replace "arithmetic" by "number theory". Arithmetic can mean number theory, but I think this meaning is disappearing. Barry, would do you think?
  4. Finally, I have my doubts about "a more general trend in mathematics over the past century, which is to recognize that 0 and 1 are very special numbers". I thought mathematicians always recognized this. I think the point in the posts you refer to is that mathematicians are getting more careful to make sure that their proofs are really correct.
I'd write longer paragraphs, but that's personal I guess. I have a maths history book which says that Gauss proved the Fundamental Theorem. I think earlier proofs exist, but they are nowadays deemed incomplete. I didn't know that the Elements contains a more restricted result. -- Jitse Niesen 14:18, 3 April 2008 (CDT)
Reponses:
  1. I agree, the word different is superfluous.
  2. No, we don't need two separate articles. However, if the main article is going to be "unique factorization", then "FToA" should be given as a synonym in the first sentence. Furthermore, typing "FToA" into CZ's main search box should deposit one on that page. Right now, if one searches for "FToA", he just gets a list of search hits, and the first one is actually the prime number page draft, not the unique factorization page. It needs to be redirected -- is this easy? I'll look into it... (Interestingly, typing "unique factorization" into the Wikipedia search box deposits you on a page about unique factorization domains -- a bad choice of redirection IMO).
  3. Noel originally wrote "number theory", and my long winded response boiled down to my thinking "arithmetic" was the more apt word. Perhaps it should say "elementary number theory". The problem is that number theory these days is big, and for instance, it seems hard to me to draw a direct connection between unique factorization and major results in analytic number theory (although Euler's factorization of the zeta function involves it). Also, it is precisely the failure of unique factorization that spurred the invention of rings and ideals and algebraic number theory in general (although unique factorization into prime IDEALS is an important building block in this area). Certainly, if you stick to elementary number theory, working with integers and congruences, then it is important, although even here it is hard to gauge how much. Very few proofs seem to come out and say, "and this next step follows from unique factorization". It is more "fundamental" in its importance, since much structure would be absent if it were false. For instance, statements that "such and such type of number has a prime factor of this type" would be silly, if you could have different prime factorizations. Also, security of certain cryptosystems is based on the assumption that the product of two large primes is hard to factor. If there were other factorizations, some that maybe involved small primes, these would no longer be viable cryptosystems. There must be a pithy way to summarize this type of fundamental importance accurately, and if someone thinks of one, that would be great. Maybe a nice allusion to that atoms/molecules metaphor again? I'll try to figure one out myself.
  4. I agree that even mathematical noobs probably have always realized that 0 and 1 are "special" numbers right away. However, even important number theorists as late as the 1900's would sometimes list 1 as a prime number. No one found a real need for a proof of FToA until Gauss, so I wouldn't say necessarily that the problem was that proofs were incorrect. I would guess that once Gauss proved this result, he did not consider 1 to be prime (I'd hope so, at least). Perhaps a lot of the time, people didn't realize the appropriate definitions until enough of the theory had been developed, like the general theory of rings and the FToA in this case ("appropriate" definitions being ones that make the theory and theorems as simple and elegant as possible).
I get worried about repeating something like "Gauss was the first to prove this theorem". I have been tempted to write sentences like this several times now, and even if I see one in a history book, there never seems to be a source. How could there be? Someone would have had to comb every extant reference to make sure no one else had proved it earlier, an impossible task. So every statement like this seems to beg the question, "how many old primary sources did you consult before you decided that Gauss was the first?" It certainly seems to happen regularly that some new source is discovered that proves such a statement false.Barry R. Smith 22:04, 3 April 2008 (CDT)
A few addtional bits:
  1. I added that "different" after thinking for a while of how to make the intro sentence as clear and consise as possible for non-mathematician readers; i.e. I only added words where I thought they really helped. Yes, technically it's superfluous (to the likes of us :-) - but I believe it will increase the likelihood of correct comprehension for the 'average' reader.
  2. For what it's worth, Wikipedia has a separate article on the Fundamental Theory of Mathematics. Not saying we need one, that's y'all's call, just providing data. I have set up the redirects as you suggest.
  3. I believe I can find a way to say exactly what Barry wants - that although the FToA is not called out specifically, what it says is important, and the basic idea/attribute of the integers (unique factorizability) which it talks about is used throughout "elementary number theory" (which I will also put in).
  4. That was my (not very good, sigh) attempt to capture the essence of what Conway said in one of his posts in that thread ("Mathematicians this century are generally much more careful about exceptional behavior of numbers like 0 and 1 than were their predecessors: we nowadays take care to adjust our statements so that our theorems are actually true. It's easy to find lots of statements in 19th century books that are actually false with the definitions their authors used"). I tried to capture the jist of what he said in a concise way that would make sense to non-experts, although you're right, my words went further than what he said - I will look at it again.
Thanks for being so patient with this non-mathematician! :-) J. Noel Chiappa 23:02, 3 April 2008 (CDT)
OK, fixed #'s 3 and 4. See what you think. J. Noel Chiappa 23:20, 3 April 2008 (CDT)
Yes, perhaps I am not well-suited to decide how useful the word "different" is. If it makes it clearer to the non-expert, like explicitly clarifying that 1 is not prime, then perhaps it is better to include it. I like having the main page titled "unique factorization" rather than FToA, since the former is the more descriptive term. I definitely like the change to "elementary number theory". However, that sentence now seems wordy to me. Do you like this better: "Unique factorization into prime numbers is formalized as the Fundamental Theorem of Arithmetic, being the foundation for much of the structure of the integers described by elementary number theory."? Also, I will go ahead and divide the first paragraph of the section on 1 into two sentences -- it seems too long for one sentence. I understand now where your comment on 0 and 1 came from -- I had already forgotten precisely what Conway had written (absent-minded professorism!). I like that sentence now. Can I cut the last statement in that section now? It can appear on some more advanced page, and the words "the Fundamental Theorem is a good example" above it seem to obviate the need for having this second more obscure example.
Also, thanks for wading through my windiness to help make this fundamental page correct but accessible to a broad readership.Barry R. Smith 10:58, 4 April 2008 (CDT)
Hi, sorry about the slow reply - been on travel.
I will take a look at that sentence; I already trimmed it once to be less wordy.
The two-sentence form looks better to me.
The "last statment in that section" (i.e. "At a more advanced level ... not visible in the context of integers.") could definitely move to a more advaced page.
Hey, we're all here to make a better encyclopaedia, right? :-) J. Noel Chiappa 16:19, 10 April 2008 (CDT)
OK, I took a crack at that section. I split that sentence you were asking about into two, but made no other changes to it because it didn't seem that bad. I did make a number of other changes to improve the overall readability, though.
First, I had placed that long sentence at the end of the section, so that it would flow into the opening of the next section (why 1 is not a prime). I decided that the advantages of that flow were not worth the overall non-optimal ordering of content within this section, so I moved it up. When I did that, I could run that 'widow' short para about the atom analogy into it, so that analogy was no longer just hanging about on its own (and I could cut some duplicate verbiage at the same time).
Finally, I reworded the last sentence in the first para; the old version was crisp and exact 'mathematicsese', but I think my new (slightly longer) version will be more accessible to 'average' readers.
Anyway, see what you think. J. Noel Chiappa 16:48, 10 April 2008 (CDT)
Reset indentation
I like your changes, with two comments: your rewording of the last sentence in the first para of the approved version is fine, except that some mathematicians encourage avoidance of the word "any", as it can mean different things to different people and in different contexts. When someone says, "if x is any number", do they mean that they are making a statement that is true for ALL possible values of x, or do they mean that they have singled out ONE particular value of x, whose identity has not yet been revealed, and are making a statement about that one value? I don't know if this type of confusion can arise in your new sentence. Perhaps a statement about use of the word "any" should be on the style guidelines for the math workgroup, if it isn't there already? The second comment is that to me, at least, the sentence suggesting the analogy to atoms/molecules seems to show up abruptly at the end of the paragraph, with not enough connection to the earlier sentences in the paragraph. Good work though.Barry R. Smith 23:54, 18 May 2008 (CDT)
I get your point about 'any': I had thought that the wording there ("Every number N >1 ... for any particular N") made it clear that if referred, one at a time, to any (all) N in that set. The problem is that I want the reader to, in their mind, single out one particular N, so I can make a statement about the set of factorizations of that N (i.e. make it is simple as possible to understand) - and also indicate that that statement is true of all N in the set N > 1. What word(s) do mathematicians use when they want the 'all' meaning of "any"? Or should I reorder it (which will make it a tiny bit longer), and explicitly say something like 'Considering any N > 1, it can be written as a product of prime factors, and all such expressions for N will contain the same factors, differing only in the sequence in which they are listed; this is true for all N > 1.'? That's probably slightly more rigorous, but somehow seems to not flow as well. Or maybe I'm being too picky? Is there some other alternative fix (an added modifier, or something) you can suggest, that removes the possible lack of rigour, while retaining the current form?
As to the analogy to atoms/molecules (and associated footnote), I agree with you! I didn't introduce any of that; I wasn't too thrilled by it, but out of deference to whoever wrote it, didn't want to simply toss it. I struggled to find a place for it where it did fit, and following onto the text about "critical building block in many of the important results in the area of elementary number theory" seemed the best I could find. One possibility is to transplant it up into the intro section, placing it in a para of its own, after the para about odd numbers, where I think it would fit a bit better (in terms of overall flow). That would make an awfully short one-sentence para, though. I suppose we could move some (or all?) of the text in the footnote up there, to bulk it up, but if so, I should probably rewrite the whole thing from scratch, to come up to the standards we have reached everywhere else (preen, preen :-). Let me ask this: is the thought it is trying to express accurate, and worth retaining? If so, I can set to and try and write it better, and would suggest that location in the intro for it. Reaction? J. Noel Chiappa 10:25, 19 May 2008 (CDT)

Primes of special forms subsection

The third type of prime considered in this section seems out of place to me. As far as I know, primes of the form n^2+1 are mostly a curiosity, and uninteresting for anything else. It would be easy to find many other types of "primes" of this form. Any one object to me removing them? As consolation, I am going to insert a bullet about primes in arithmetic sequences, which seem much more important to me.Barry R. Smith 17:50, 1 April 2008 (CDT)

I might suggest leaving them because Mersenne primes are a major source of "largest prime" values. I know, I know, to most true mathematicians this is probably boring juvenile crap, but some people enjoy it (like some people enjoy tiddliwinks) - see, for instance, GIMP so an article on primes ought to at least mention Mersenne primes! Blast, wrote that whole section, then realized you were talking about N^2+1, not 2^N-1! On thinking about it, they seem rather obscure to me, so we can probably lose them. I'd just comment them out, rather than discard the text completely; that way, if someone makes a case for them, it's trivial to put them back. J. Noel Chiappa 19:40, 1 April 2008 (CDT)

Alternative definition

I am interested in having a non-mathematician perspective on the last part of this section. It seems to me to ramp up in sophistication very quickly, starting with mention of the word "ideal", and then moving into sentences about "rings" and "generation" of "ideals". Certainly, if this page is intended for non-specialists, then those terms should at least be linked. But would they be better placed in a page about prime ideals in rings, and a much simplified discussion put in its place on this page?Barry R. Smith 17:50, 1 April 2008 (CDT)

I couldn't make heads or tails of it most of it. I would just move everything past the Euclid's Lemma thing to an /Advanced subpage (see Quantum mechanics/Advanced for what such pages look like). The first couple of paras I would leave, as they are comprehensible to us mortals, and mildly interesting - but I will rewrite them a bit to make them clearer. J. Noel Chiappa 19:48, 1 April 2008 (CDT)

Fermat primes

The current discussion of Fermat primes says that one can construct a regular p-gon if p is a Fermat prime. Perhaps more surprising is that these are the ONLY primes for which you can construct a regular p-gon, so I am going to add this.

The above unsigned comment isn't by me (though I agree with it). Peter Jackson 17:12, 24 November 2008 (UTC)

MUCH MORE IMPORTANT. There's an error in the article. It says Fermat primes are 2↑n + 1. That should be 2↑2↑n + 1. Peter Jackson 17:10, 24 November 2008 (UTC)

Other types of primes

I think that if we are going to discuss other types of primes, obvious choices include Wieferich and Wilson primes. But where do we draw a line about which special types of primes to include? Wieferich primes showed up in work on Fermat's Last Theorem. Perhaps a criterion would be to include any special forms for which a significant result is known? I like this better than the criterion of including any forms of primes with "names".Barry R. Smith 18:15, 1 April 2008 (CDT)

Write articles on them, and link to those articles from the "Related Articles" subpage. As you suggest, I'd only put really important ones here. That's probably where to put Fermat primes, now that I think of it. I'll leave that to you all too. J. Noel Chiappa 19:48, 1 April 2008 (CDT)

Reapproval needed

As pointed about by Peter Jackson above, the definition of Fermat prime should be a prime of the form , not one of the form . Actually, the primes of the first type are precisely the primes of the second type. (Proof: If n=kt with k an odd prime, then 2^n+1 has 2^t+1 as a factor other than 1 and itself). But as written, the definition is certainly nonstandard and somewhat misleading. As such, I think reapproval of this page should be expedited.

Issues:

  • Noel suggests that Fermat primes should appear just on the "related articles" page. I think it is appropriate to have something in the main article about special types of primes, mentioning a few types. Fermat prime is certainly one of the most popular. But there should be agreement -- the problem could be fixed just by linking to pages about a few types of special primes without defining any of them in the "prime number" page.
  • It is technically correct as written, so if reapproval is an arduous process (I haven't done it myself), then perhaps it is not worth it just to fix this one problem.
  • The current draft is rather different than the approved version, so if there is agreement that the draft is better than the current version, or could be made better than it, then perhaps we should work to reapprove now even if the process is difficult.Barry R. Smith 21:22, 27 November 2008 (UTC)