Prime number

In mathematics, a prime number (or prime) is a natural number greater than 1 (number) whose only positive number divisors are one and itself. A natural number that is greater than one and is not a prime is called a composite number. The numbers 0 (number) and one are neither prime nor composite. The property of being a prime is called ''primality''. Prime numbers are of fundamental importance in number theory. The sequence of prime numbers begins :2 (number), 3 (number), 5 (number), 7 (number), 11 (number), 13 (number), 17 (number), 19 (number), 23 (number), 29 (number), 31 (number), 37 (number), 41 (number), 43 (number), 47 (number), 53 (number), 59 (number), 61 (number), 67 (number), 71 (number), 73 (number), 79 (number), 83 (number), 89 (number), 97 (number), 101 (number), 103 (number), 107 (number), 109 (number), 113 (number) ... This is sequence A000040 [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000040] in On-Line Encyclopedia of Integer Sequences; see list of prime numbers for the first 500 primes. The set of all prime numbers is sometimes denoted by ℙ, a blackboard bold P. As 2 is the only even prime number, the term ''odd prime'' is used to refer to all prime numbers except 2. In the context of ring theory, a branch of abstract algebra, the term "prime element" has a specific meaning. Here, a ring element ''a'' is defined to be prime if whenever ''a'' divides ''bc'' for ring elements ''b'' and ''c'', then ''a'' divides at least one of ''b'' or ''c''. With this meaning, the additive inverse of any prime number is also prime. In other words, when considering the set of integers Z as a ring (mathematics), −7 is a prime element. However, even among mathematicians, the term "prime number" generally means a positive prime integer. == Representing natural numbers as products of primes == The fundamental theorem of arithmetic states that every positive integer can be written as a product of primes in an essentially unique way. Primes are thus the "basic building blocks" of the natural numbers. For example, we can write :

23244 = 2^2 \times 3 \times 13 \times 149

and any other such factorization of 23244 will be identical, except for the order of the factors. See prime factorization algorithm for details for how to do this in practice, for larger numbers. The importance of this theorem is one of the reasons for the exclusion of 1 from the set of prime numbers. If 1 were admitted as a prime, the precise statement of the theorem would require additional qualifications. == How many prime numbers are there? == There are infinitely many prime numbers. The oldest known proof for this statement is given by the Greek mathematician Euclid in his ''Elements'' (Book IX, Proposition 20). Euclid states the result as "there are more than any given [finite] number of primes", and his proof is essentially the following: :Take a finite number of primes. Multiply them all together and add one (see Euclid number). The resulting number is not divisible by any of the finite set of primes, because dividing by any of these would give a remainder of one. Therefore it must either be prime itself, or be divisible by some other prime that was not included in the finite set. Therefore the set we started with was not in fact all primes. Other mathematicians have given their own proofs. One of those (due to Leonhard Euler) shows that proof that the sum of the reciprocals of the primes diverges. Ernst Kummer's is particularly elegant and Furstenberg provides one using general topology. Even though the total number of primes is infinite, one could still ask "approximately how many primes are there below 100,000" or "How likely is a random 100-digit number to be prime?" Questions like these are answered by the prime number theorem. == Finding prime numbers == The Sieve of Eratosthenes is a simple way to compute the list of all prime numbers up to a given limit. In practice though, one usually wants to check if a given number is prime, rather than generate a list of primes. Further, it is often satisfactory to know the answer with a high probability. It is possible to quickly check whether a given large number (say, up to a few thousand digits) is prime using probabilistic primality tests. These typically pick a random number called a "witness" and check some formula involving the witness and the potential prime ''N''. After several iterations, they declare ''N'' to be "definitely composite" or "probably prime". These tests are not perfect. For a given test, there may be some composite numbers that will be declared "probably prime" no matter what witness is chosen. Such numbers are called pseudoprimes for that test. A new deterministic algorithm which finds whether a given number ''N'' is prime where the time required is a Complexity classes P and NP (i.e. of the logarithm of ''N'') has recently been described. == Some properties of primes == *If ''p'' is a prime number and ''p'' divides a product ''ab'' of integers, then ''p'' divides ''a'' or ''p'' divides ''b''. This proposition was proved by Euclid and is known as ''Euclid's lemma''. It is used in some proofs of the uniqueness of prime factorizations. *The ring (algebra) Z/''n''Z (see modular arithmetic) is a field (mathematics) if and only if ''n'' is a prime. Put another way: ''n'' is prime if and only if Euler's totient function = ''n'' − 1. *If ''p'' is prime and ''a'' is any integer, then ''a''^''p'' − ''a'' is divisible by ''p'' (Fermat's little theorem). *If ''p'' is a prime number other than 2 and 5, 1/p is always a recurring decimal, with a period of p-1 or a divisor of p-1. This can be deduced directly from Fermat's little theorem. 1/p expressed likewise in base q (i.e. other than base 10) has similar effect, provided that p is not a prime factor of q. The Wiki page on recurring decimal shows some of the interesting properties. *An integer ''p'' > 1 is prime if and only if the factorial (''p'' − 1)! + 1 is divisible by ''p'' (Wilson's theorem). Conversely, an integer ''n'' > 4 is composite if and only if (''n'' − 1)! is divisible by ''n''. *If ''n'' is a positive integer, then there is always a prime number ''p'' with ''n'' < ''p'' ≤ 2''n'' (Bertrand's postulate). *Adding the reciprocals of all primes together results in a divergent infinite series (Proof that the sum of the reciprocals of the primes diverges). More precisely, if ''S''(''x'') denotes the sum of the reciprocals of all prime numbers ''p'' with ''p'' ≤ ''x'', then ''S''(''x'') = Θ(ln ln ''x'') for ''x'' → ∞ (see Big O notation). *For each prime number ''p'' > 2, there exists a natural number ''n'' such that ''p'' = 4''n'' � 1. *For each prime number ''p'' > 3, there exists a natural number ''n'' such that ''p'' = 6''n'' � 1. *In every arithmetic progression ''a'', ''a'' + ''q'', ''a'' + 2''q'', ''a'' + 3''q'',... where the positive integers ''a'' and ''q'' ≥ 1 are coprime, there are infinitely many primes (Dirichlet's theorem). *The characteristic of every field is either zero or a prime number. *If ''G'' is a finite group (mathematics) and ''p''^''n'' is the highest power of the prime ''p'' which divides the order of ''G'', then ''G'' has a subgroup of order ''p''^''n''. (Sylow theorems) *If ''p'' is prime and ''G'' is a group with ''p''^''n'' elements, then ''G'' contains an element of order ''p''. *The prime number theorem says that the proportion of primes less than ''x'' is asymptotic to 1/ln ''x'' (in other words, as ''x'' gets very large, the likelihood that a number less than ''x'' is prime is inversely proportional to the number of digits in ''x''). == Open questions == There are many open questions about prime numbers. The most significant of these is: * Riemann hypothesis: This essentially says that the primes are as regularly distributed as possible. From a physical viewpoint, it roughly states that the irregularity in the distribution of primes only comes from random noise. From a mathematical viewpoint, it roughly states that the asymptotic distribution of primes (about 1/ log ''x'' of number less than ''x'' are primes, the prime number theorem) also holds for much shorter intervals of length about the square root of ''x'' (for intervals near ''x''). This hypothesis is generally believed to be correct, in particular, the simplest assumption is that primes should have no significant irregularities without good reason. Other famous conjectures have a much greater chance of being true (in a formal sense, they follow from simple heuristic probabilistic arguments) with the lack of a solution more of a reflection of lack of good technical tools (so theoretical physicists would just regard them as being true): * Goldbach's conjecture: Can every even integer greater than 2 be written as a sum of two primes? * Twin prime conjecture: A ''twin prime'' is a pair of primes with difference 2, such as 11 and 13. Are there infinitely many twin primes? * Does the Fibonacci sequence contain an infinite number of primes? * Are there infinitely many Lenstra-Pomerance-Wagstaff conjectures and Fermat primes? The expected answers are ''yes'', resp. ''no''. * Are there infinitely many primes of the form ''n''² + 1? * Is there always a prime number between ''n''² and (''n'' + 1)² for every ''n''? * Cramer's conjecture that

d(x)

, the largest gap between consecutive primes, among all primes less than ''x'', is asymptotic to

\log^2 x

. This conjecture clearly implies the previous one, but its status is a little more unsure. == The largest known prime == The largest known prime is 2^25964951 − 1 (this number is 7,816,230 digits long); it is the 42nd known Mersenne prime. M_25964951 was found on February 18, 2005 by Martin Nowak, a member of a collaborative effort known as GIMPS). The next largest known prime is 2^24036583 − 1 (this number is 7,235,733 digits long); it is the 41st known Mersenne prime. M_24036583 was found on May 15, 2004 by Josh Findley (member of GIMPS) and it was announced in late May 2004. The third largest known prime is 2^20996011 − 1 (this number is 6,320,430 digits long); it is the 40th known Mersenne prime. M_20996011 was found on November 17, 2003 by Michael Shafer (and GIMPS) and announced in early December 2003. Historically, the largest known prime has almost always been a Mersenne prime since the dawn of electronic computers, because there exists a particularly fast primality test for numbers of this form, the Lucas-Lehmer test for Mersenne primes. Some of the largest primes not known to have any particular form (that is, no simple formula such as that of Mersenne primes) have been found by taking a piece of semi-random binary data, converting it to a number n, multiplying it by 256^k for some positive integer k, and searching for possible primes within the interval [256^''k''''n'' + 1, 256^''k''(''n'' + 1) − 1]. In fact, as a publicity stunt against the Digital Millennium Copyright Act and other WIPO Copyright Treaty implementations, some people have applied this to various forms of DeCSS code, creating the set of illegal prime numbers. Such numbers, when converted to binary and executed as a computer program, perform acts encumbered by applicable law in one or more jurisdictions. == Applications == Extremely large prime numbers (that is, greater than 10¹⁰⁰) are used in several public key cryptography algorithms. Primes are also used for hash tables and pseudorandom number generators. == Primality tests == ''Main article primality test'' A primality test is an algorithm which tests a number for primality, i.e. whether the number is a prime number. * AKS primality test * Fermat primality test * Lucas-Lehmer test * Lucas-Lehmer primality test * Solovay-Strassen primality test * Miller-Rabin primality test A probable prime is an integer which, by virtue of having passed a certain test, is considered to be probably prime. Probable primes which are in fact composite (such as Carmichael numbers) are called pseudoprimes. == Some special types of primes == A prime ''p'' is called ''primorial prime'' or ''prime-factorial'' if it has the form ''p'' = Π(''n'') � 1 for some number ''n'', where primorial stands for the product 2 � 3 � 5 � 7 � 11 � ... of all the primes ≤ n. A prime is called ''factorial prime'' if it is of the form factorial � 1. The first factorial primes are: :n! − 1 is prime for n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166,... :n! + 1 is prime for n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154... The largest known primorial prime is Π(24029) + 1, found by Caldwell in 1993. The largest known factorial prime is 3610! − 1 [Caldwell, 1993]. It is not known if there are infinitely many primorial or factorial primes. Primes of the form 2^''n'' − 1 are known as Mersenne primes, while primes of the form

2^{2^n} + 1

are known as Fermat primes. Prime numbers ''p'' where 2''p'' + 1 is also prime are known as Sophie Germain primes. Other special types of prime numbers include Wieferich primes, Wilson primes, Wall-Sun-Sun primes, Wolstenholme primes, unique primes, Newman-Shanks-Williams primes (NSW primes), Smarandache-Wellin primes, Wagstaff primes and supersingular primes. The base-ten digit sequence of a prime can be a palindrome, as in the prime 10³¹⁵¹² + 9700079 � 10¹⁵⁷⁵³ + 1. == Prime gaps == Let ''p''_''n'' denote the ''n''-th prime number (i.e. ''p''₁ = 2, ''p''₂ = 3, etc.). The ''gap'' ''g''_''n'' between the consecutive primes ''p''_''n'' and ''p''_{''n'' + 1} is the number of (composite) numbers between them, i.e. :''g''_''n'' = ''p''_{''n'' + 1} − ''p''_''n'' − 1. (Slightly different definitions are sometimes used.) We have ''g''₁ = 0, ''g''₂ = ''g''₃ = 1, and ''g''₄ = 3. The sequence {''g''_''n''} of prime gaps has been extensively studied. For any ''N'', the sequence :(''N'' + 1)! + 2, (''N'' + 1)! + 3, ..., (''N'' + 1)! + ''N'' + 1 is a sequence of ''N'' consecutive composite integers. Therefore, there exist gaps between primes which are arbitrarily large, i.e. for any natural number ''N'', there is an integer ''n'' with ''g''_''n'' > ''N''. (Choose ''n'' so that ''p''_''n'' is the greatest prime number less than (''N'' + 1)! + 2.) On the other hand, the gaps get arbitrarily small in proportion to the primes: the quotient (''g''_''n''/''p''_''n'') limit (mathematics) zero as ''n'' approaches infinity. We say that ''g''_''n'' is a ''maximal gap'' if ''g''_''m'' < ''g''_''n'' for all ''m'' < ''n''. The largest known maximal gap is 1131, found by T. Nicely and B. Nyman in 1999. It is the 64th smallest maximal gap, and it occurs after the prime 1693182318746371. The largest prime gap with identified gap ends known as of 1 January 2005 has a length of 2254930 [http://hjem.get2net.dk/jka/math/primegaps/megagap2.htm]. Note that the Twin Prime Conjecture simply asserts that ''g''_''n'' = 1 for infinitely many integers ''n''. == Formulae yielding prime numbers == ''Main article formula for primes'' There is no formula for primes which is more efficient at finding primes than the methods mentioned above under "Finding prime numbers". Those which do exist have little practical value. The curious polynomial ''f''(''n'') = ''n''² − ''n'' + 41 yields primes for ''n'' = 0,..., 40, but ''f''(41) is composite. There is no polynomial which only yields prime numbers in this fashion. There is a set of Diophantine equations in 25 variables and one parameter with the following property: the parameter is prime if and only if the resulting system of equations has a solution over the natural numbers. This can be used to obtain a single formula with the property that all its ''positive'' values are prime. Another formula is based on Wilson's theorem mentioned above, and generates the number two many times and all other primes exactly once. There are other similar formulae which also produce primes. == Generalizations == The concept of prime number is so important that it has been generalized in different ways in various branches of mathematics. === Prime elements in rings === One can define prime elements and irreducible elements in any integral domain. For the ring Z of integers, the set of prime elements equals the set of irreducible elements; it's {...−11, −7, −5, −3, −2, 2, 3, 5, 7, 11, ...}. As an example, we consider the Gaussian integers Z[''i''], that is, complex numbers of the form ''a'' + ''bi'' with ''a'' and ''b'' in Z. This is an integral domain, and its prime elements are the Gaussian primes. Note that 2 is ''not'' a Gaussian prime, because it factors into the product of the two Gaussian primes (1 + ''i'') and (1 − ''i''). The element 3, however, remains prime in the Gaussian integers. In general, rational primes (i.e. prime elements in the ring Z of integers) of the form 4''k'' + 3 are Gaussian primes, whereas rational primes of the form 4''k'' + 1 are not. === Prime ideals === In ring theory, one generally replaces the notion of number with that of ideal (ring theory). ''Prime ideals'' are an important tool and object of study in commutative algebra, number theory and algebraic geometry. The prime ideals of the ring of integers are the ideals (0), (2), (3), (5), (7), (11), ... A central problem in algebraic number theory is how a prime ideal factors when it is ''lifted'' to an extension field. For example, in the Gaussian integer example above, (2) ''ramifies'' into a prime power (1 + ''i'' and 1 − ''i'' generate the same prime ideal), prime ideals of the form (4''k'' + 3) are ''inert'' (remain prime), and prime ideals of the form (4''k'' + 1) ''split'' (are the product of 2 distinct prime ideals). === Primes in valuation theory === In class field theory yet another generalization is used. Given an arbitrary field (mathematics) ''K'', one considers valuations on ''K'', certain functions from ''K'' to the real numbers R. Every such valuation yields a topological field, and two valuations are called ''equivalent'' if they yield the same topology. A ''prime of K'' (sometimes called a ''place of K'') is an equivalence class of valuations. With this definition, the primes of the field Q of rational numbers are represented by the standard absolute value function (known as the "infinite prime") as well as by the p-adic number on Q, for every prime number ''p''. == Quotes == :"Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate." — ''Leonhard Euler'' :"God may not play dice with the universe, but something strange is going on with the prime numbers." — ''Paul Erd�s'' == See also == * Prime power * Sphenic number * Highly composite number * Primorial * J�rgen Pedersen Gram * Logarithmic integral function == References == * Karl Sabbagh, ''The Riemann Hypothesis: The Greatest Unsolved Problem in Mathematics''. Farrar, Straus and Giroux; 340 pages * John Derbyshire, ''Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics''. Joseph Henry Press; 448 pages * Marcus du Sautoy, ''The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics''. HarperCollins; 352 pages * H. Riesel, ''Prime Numbers and Computer Methods for Factorization'', 2nd ed., Birkh�user 1994. == External links == * [http://primes.utm.edu/curios/ Prime curios] at the prime pages * The prime pages -- http://www.utm.edu/research/primes/ * [http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Prime_numbers.html MacTutor history of prime numbers] * [http://www.maths.hscripts.com/prime_number.php Online Prime Number calculator] * [http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html The "PRIMES is in P" FAQ] * [http://wikisource.org/wiki/Prime_numbers_%282_-_20000%29 The first 20,000 primes] (through 224737) at Wikisource * [http://www.primenumbers.net/prptop/prptop.php List of largest known probable primes] * [http://www.primepuzzles.net/ The prime puzzles] * [http://www.ibiblio.org/omdb/prime/ The Prime Project] generates a new prime number every time the page is loaded * [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html An English translation of Euclid's proof that there are infinitely many primes] * [http://wims.unice.fr/wims/wims.cgi?module=tool/number/primes.en Primes] from WIMS is an online prime generator. * [http://www.kwiznet.com/p/takeQuiz.php?ChapterID=1543&CurriculumID=5 Prime Factorization Worksheet] generates new questions every time the page is loaded * [http://mathworld.wolfram.com/PrimeSpiral.html Prime Spiral pattern] * [http://www.alpertron.com.ar/googolm1.pl?digits=12 12 digit primes] Known 12-digit prime factors of Googolplex - 1 *http://www.maths.ex.ac.uk/~mwatkins/zeta/vardi.html An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier Integers Number theory Prime numbers ang:Frumt�l scn:nummuru primu th:จำนวนเฉพาะ

Prime number

Some page format added. User:Charles Matthews 07:49, 4 May 2004 (UTC) ==Initial segment of primes== Links: http://www.utm.edu/research/primes/ The first 750,000 primes: http://www.geocities.com:80/ResearchTriangle/Thinktank/2434/prime/primenumbers.html ---- Now here's an interesting question which may even provide a valid use for subpages. Would adding a list of all the prime numbers known to mankind be counter-productive to the idea of the Wikipedia? It ''is'' "a compendium of human knowledge", regardless of how obscure and arcane. (I suppose one could extend this to listing Pi to a :quadrillion digits, to be somewhat hyperbolic.) Thoughts? --User:Colin dellow ---- I'd say that the encyclopedia should be a compendium of all useful knowledge. Digit number 323454 of Pi and the temperature at noon on May 7, 1976 in Salt Lake City are part of human knowledge, but really, nobody has a use for this information except maybe some highly specialized experts, who know where to look it up. ---- I perhaps didn't make my point clear. Wikipedia presents the ability to have "useless" trivia because of the :Wikipedia is not paper argument. :Perhaps it will be useful only to a specialised group, but does it hurt to have it? It would increase the amount of information available in the Wikipedia. (I found the comment about temperature s in Salt Lake City at a given year to be somewhat unrelated to this question, BTW.) --User:Colin dellow ----- Actually, I don't think it would be possible to list all the known primes. There are just too darn many of them, and it's too easy to find more. - Hank Ramsey ---- I don't think it would be a waste of space to have a separate article that lists say, all the primes less than 10,000. This is actually very little raw data, but having available the primes in this range is very useful to many people, especially for testing conjectures, making conjectures, playing around with numbers, etc. The information would NOT just be trivial as in the temperature of Salt Lake City at a certain time. Also, I think it would be very useful if there were an article that listed the complete prime factorisations of all integers less than 10,000. Again, this is not trivial information, it's very important if someone wants to quickly test whether or not a conjecture may or may not be true. Agreed --User:Haggis 14:39, 24 Feb 2005 (UTC) :But don't forget, that there exist prime-tables (2-100.000, 100.001-200.000, ... ) in wikisource. --User:Arbol01 02:19, 25 Feb 2005 (UTC) correcting Wikipedia entry of Euclid's Infinitude of Primes proof Fixed font - Proportional font Archimedes Plutonium Apr 14, 10:17 am show options Newsgroups: sci.math, sci.logic, sci.edu From: Archimedes Plutonium - Find messages by this author Date: Thu, 14 Apr 2005 12:17:05 -0500 Local: Thurs,Apr 14 2005 10:17 am Subject: correcting Wikipedia entry of Euclid's Infinitude of Primes proof Reply | Reply to Author | Forward | Print | Individual Message | Show original | Report Abuse Thu, 14 Apr 2005 12:23:29 -0000 SunCode wrote: > > Yes, thanks, I will execute on your suggestion. > Yes! do so, but please read this page first =) > http://en.wikipedia.org/wiki/Wikipedia:No_original_research > SunCode. Correcting Euclid's Infinitude of Primes (IP) proof is not original research, especially in light of the fact that out of 31 authors of a publicly written IP proof only 3 of them gave a valid rendition, and the others which includes MathWorld and Wikipedia gave a flawed and invalid IP proof. So that hardly counts as original research in the fact that 3 authors of the past of Flath, Landau, and Stillwell managed to give a valid IP proof in a textbook and that it was the misfortune of MathWorld and Wikipedia to have chosen the other 28 authors who rendered a invalid and error filled rendition. If Wikipedia had copied Stillwell's rendition plus adding a line saying that Euclid gave a Direct Method Proof of increasing set cardinality then Wikipedia would not be on the list of flawed and invalid proofs. So this is not original research but the correction of flawed and invalid past thinking and understanding. I have not pinpointed as to where in the history of mathematics that this stain and tarnish on Euclid's IP started. I have a educated guess that it was Gauss himself who started the flaw because Gauss used Reductio Ad Absurdum so much in his own work of Number Theory that later mathematicians would fall into the trap of thinking that Euclid's IP was Reductio Ad Absurdum (the Indirect Method). So thanks to SunCode, I am still going to apply to Wikipedia today to start the motion for them to change their entry on Euclid's Infinitude of Primes proof. If Wikipedia had a webpage where they claim that the addition of 2 plus 2 comes out to be equal to 3, then that should not be called original research when someone trys to correct them by pointing out it is equal to 4. Thanks SunCode, and I think I will apply for a brevity Euclid's Infinitude of Primes proof considering that full details can always be referred to my website of File 106 in www.iw.net/~a_plutonium Correction to Wikipedia website of Euclid's Infinitude of Primes Proof: Euclid, from his own language of "prime numbers are more than any assigned multitude" gave a Direct Proof Method for Infinitude of Primes. This method is one of increasing the set cardinality of any given finite set of primes which by logic then generalizes to an infinite set. Many mathematicians in the 19th and 20th century erroneously thought that Euclid gave a Indirect Proof Method which caused them to render an invalid proof attempt by searching for a prime-factor. Direct Proof of IP: Given any finite collection of primes 2,3,...,pn possessing a cardinality n We find another prime by considering P!+1 = (2x3x...xpn) +1 Either P!+1 itself is a prime or else it has a prime factor not equal with any of the primes on the finite list. Thus the cardinality of every finite set can be increased. And since all/any finite cardinality set can be increased by 1 more prime therefore the set of primes is an infinite set. Euclid's IP was not Indirect or Reductio Ad Absurdum but I give it here anyway to show for instruction sake: Proof: The prime numbers are the numbers 2,3,...,pn,... of set P Suppose finite, then 2,3,...,pn is the complete set of primes. Form P!+1 = (2x3x,...,xpn) + 1 Now P!+1 is necessarily a new prime because all the primes that exist leave a remainder of 1 when divided into P!+1 and so by the very definition of what it means to be prime this new number of P!+1 in this restricted space of primes is necessarily a new prime not on the original list. Contradiction, hence set of primes is infinite. Euclid never used the Indirect Method to prove his Infinitude of Primes. Somewhere around the time of Gauss was the erroneous claim that Euclid used the Reductio Ad Absurdum for IP. Worse yet was the mixing up of methods of making a prime factor search in the Indirect Method when P!+1 once formed is automatically the new prime. So I have corrected two items in Euclid's Infinitude of Primes proof. One item is the history of the proof is Direct and not Indirect method. The second item is that in a Indirect proof of IP there cannot be a prime-factor search because the definition of prime forces the new number P!+1 to be automatically the new prime given that restricted space of primes. Copy send to Wikipedia editors. Please note I can make the correction as brief as possible to one short paragraph. Archimedes Plutonium www.iw.net/~a_plutonium whole entire Universe is just one big atom where dots of the electron-dot-cloud are galaxies :Archimedes Plutonium has been posting much to sci.math under the bizarre impression that Euclid's proof is somehow imprecise, too verbose, or incorrect. It is none of these things, and his strange explanation of how Euclid did not use a simple (in fact, seen by most as the protypical) reductio ad absurdum proof is merely clutter. Incorrect clutter. This is the first time I've edited a wikipedia page; I am going to attempt a revert. User:Tezh 08:40, 15 Apr 2005 (UTC) :Of course, Archimedes Plutonium is correct and Euclid is wrong. Euclid's proof is formally incorrect because it actually states that given any three primes, one can find a fourth not on the list. Sometimes, I wonder if anyone has actually read Euclid's actual proof, which is widely available in English. -ilan ::I have read Euclid's actual proof, in English transaltion, and I thought that it was clear that Euclid meant to imply the general case as an obvious extrapolation from the case of one and then three primes. He didn't explicitly say anything like "extending this argument to the general case proves the theorem," but I believe that was what he was thinking, and that he considered it too obvious to put in. Certainly it is implausible to suggest he meant nothing of this kind, and that he made an error of logic, since the proof is so obviously defective without it; Euclid was not so foolish as that. -- User:Dominus 19:20, 25 May 2005 (UTC) ::Well, considering how much anger and frustration is observed in professors grading students who only did 3 steps in a mathematical induction proof, it is ironic to see that this was the exact method used by Euclid and Archimedes. I guess they would have miserably failed finite mathematics courses. The final irony is Doron Zeilberger's observation that doing 3 steps in an induction is actually a formally correct proof for the formulas for the sum of the first n positive integers. -ilan ==Infinitude of primes == Note regarding the proof of the infinitude of primes: we use the fact that every composite number has a prime factor. I think that requires proof in itself. ---- Yes, perhaps, if it isn't obvious. It is clear that if a given number has a composite divisor, then the divisors of that divisor are also divisors of the original number (if A=B*C and C=D*E then A=B*D*E). If any of these divisors are composite, we can apply this principle recursively to find more divisors of the original number. We cannot recurse indefinitely because the number cannot have an infinite number of divisors. So eventually we must reach a point where all the new divisors are prime. QED ------ Re: every composite number has a prime factor; this is a direct corollary of the fundamental theorem of arithmetic. Done. ---- sub page or article on infamous research project "A Short List of Even Primes" which is of course, mainly acknowledgements and academic scaffolding, followed by the list, viz. 2 ---- I wouldn't mind a link to a joke if it's clearly labeled as such. For that matter, I wouldn't mind adding the old "proof" that all primes are odd. -user:LC ---- The article says: :There are infinitely many prime numbers. The oldest known proof for this statement dates back to the Greek mathematician Euclid. It is also one of the oldest known proofs by contradiction. I thought that Euclid stated the theorem as "Given any prime, there is a larger prime." With the theorem stated like this, the proof isn't a proof by contradiction -- the existence of the larger prime is shown directly. Can someone confirm this, or am I misremembering? --User:Zundark, 2001 Oct 11 I think you're right; I'll take the contradiction bit out. --AxelBoldt :I see someone has put it back in again. I will remove it (or reword it) if no one can provide a justification for it. --User:Zundark 15:09 Apr 3, 2003 (UTC) Yes, I believe it IS a proof by contradiction. We wish to show there exist infinitely many primes. So, suppose not; suppose there only exist finitely many primes. Then certainly there exists a _largest_ prime since there are only finitely many. But given this largest prime, I can show that there must exist another prime larger than the largest prime. This is a contradiction. Hence, there must be an infinite number of primes. :It's not a question of what ''we'' wish to show, but of what Euclid actually showed. There is an English translation [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html here]. Euclid claims that there are more than any given finite number of primes, and proves this directly by taking a finite number of primes, and showing that there is another. To read this as a proof by contradiction that there are an infinite number of primes is to add a modern gloss that does not exist in the original. :If you read the above-mentioned translation you will see that Euclid's proof - like many of his other proofs - does involve a proof by contradiction: he proves by contradiction that ''G'' is not a member of the finite set of primes. But our article is wrong to claim that Euclid's proof of the theorem as a whole is a ''reductio ad absurdum''. I will maybe try to rewrite that part of the article later today. --User:Zundark 11:19, 13 Oct 2003 (UTC) :It seems to me, at least from the translation linked above, that the theorem certainly does involve proof by contradition. It says, in part: ::"I say that G is not the same with any of the numbers A, B, and C. If possible, let it be so. ... Therefore G, being a number, measures the remainder, the unit DF, which is absurd. Therefore G is not the same with any one of the numbers A, B, and C." :Euclid assumes that ''G'' (previously constructed as a prime factor of ''ABC''+1) is identical with one of ''A'', ''B'', or ''C'', derives a contradiction, and concludes the oppoisite, that ''G'' is distinct from ''A'', ''B'', and ''C''. I don't know how free the translation is, but to assert that the proof is not an example of reductio ad absurdum in the face of the phrase "which is absurd" is rather absurd. -- User:Dominus 19:33, 25 May 2005 (UTC) ::There is a difference between "involves a ''reductio ad absurdum''" (which the proof certainly does, as I already pointed out above some 19 months ago) and "is a ''reductio ad absurdum''" (which the proof isn't). --User:Zundark 20:38, 25 May 2005 (UTC) :::Well, the distinction is lost on me personally, in the present case, then. Can you elaborate?? User:Revolver 05:28, 26 May 2005 (UTC) ::::The [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html translation linked above] is an eleven-paragraph proof, of which two-and-a-bit paragraphs near the end are a proof by ''reductio ad absurdum'' that G is not equal to A, B or C. You could even remove this ''reductio ad absurdum'' part and the proof as a whole would still make sense, so I don't see how the proof as a whole can possibly be considered as a ''reductio ad absurdum''. --User:Zundark 08:20, 26 May 2005 (UTC) :::::I see. I was thinking again that it started "Thm: There are an infinite number of primes. Pf: Suppose not, then...", again forgetting this isn't how it's stated. User:Revolver 08:51, 26 May 2005 (UTC) ---- It seems that the source of confusion or differing interpretations is coming from different ways of translating Euclid's statement into logical statements involving quantifiers. The modern definition of an infinite set is usually taken to be the following (if not, then it is easily shown to be equivalent to the definition): A set S is infinite if it cannot be put in 1-1 correspondence with a natural number or the empty set (if 0 is not considered a natural number). This is a definition by negation. An infinite is defined to be one that is not finite. So, to prove by definition that a set is infinite, one can do the following: Suppose for sake of contradiction that S CAN be put in 1-1 correspondence with a natural number or 0. Then..... Thus, S is infinite. The way of expressing this definition in terms of logical quantifiers would be ~ (exists A)(P(A)) where ~ is negation and P(A) a statement involving A. By modern rules of logic (at least, most logical systems, and certainly the one most working math people use), this is logically equivalent to (for all A)(~ (P(A))) This is the form of the theorem as stated by Euclid. He gave a direct proof of the positive assertion that for all A, ~ P(A) is true. What is happening is we come along, almost subconsciously without thinking, identify this statement with the logically equivalent form given above, and then realize that by the definition of infinite set, this is really a proof that the set of primes is infinite. Now, how this should all be interpreted and presented, I don't have all the answers, maybe a short disclaimer explaining what I've mentioned above is in order. At any rate, it's open for discussion. ==Types of primes== I took this out for now: :''multifactorial'', ''compositorial'' or ''binomial'' primes since the terms are not defined. I couldn't understand the examples :Multifactorial prime is for example 43328! � 7 - 1, compositorial prime 8711!/ ∏(8711) - 1 and binomial prime 104087!/(52043! � 52044!) + 1. And in this paragraph :and can have many other properties in collecting of different terms or can be derived from some well known sequences as for example as the primitive part U(n) of the nth term in the Fibonacci sequence e.g. U(40295) or as V(n) in the Lucas sequence e.g. V(25504) and many more. what is the "primitive part" of the nth term in the Fibonacci sequence? user:AxelBoldt ---- Yes, user:AxelBoldt I'll soon make those definitions more clear. And on the other hand if you understand the first two definitions (''primorial'' and ''factorial'' prime) you should understand the next three ones, because they are just futher extendings of the first two ones. These short contributions stole me some 3 to 4 hours of intense work just to get them together and one can easily put them out in a minute. The topic of pure and just pure primes is for me at a highest interestings. I think Axel you're looking for too much "usefull" and wonderful definitions, theorems, proofs and such inhere. Math is not just that. The good example for this is for instance (a pure mathematician) Keith Devlin with his piercing work for better understanding of the whole past, present and future math or I can say this for our mathematician France Križanič who wrote some nice Devlinlike books - and he is still writting them. For example integral in a complex is not for a high school, but he had put it in his huge textbook for secondary schools. He put there some beautifull work of theoretical astronomer M�bius as well. I can talk on and on - but I am afraid someone would say in Marley's manner I've got so much things to say, ha, ha. XJam keep on moving and try putting some more stones in math knowledge on this icy road. For the term "primitive part" I need more Time because nobody told me about, hey ho. (Back to work XJ again, ''- come together and make it work, whoahh, we got five days to go, working for the next day, hey hey, now ...'' [Bob Marley, ''Work'', live at final tour in Berlin 1980 ]). And I have enough Time because I really do not want to steal anything from Nature. I do believe that Fibonacci never dreamed that someday someone would talk some more about his "obscure" sequence found everywhere in a Nature itself. That goes for Lucas (and many, many others) too. I hope I'll achieve at least fair level of Axel's rigorousness soon. Another thing (I'll say this as fast as I can :-) ) as of the first above external link someone put in this talk. I'll generate with that list an Ulam-(M�bius) cloth and I'll post a picture of it in Wikipedia's digital archives as soon as possible. We can then ''Distiquence Arithmeticaenniolus'' (this is a weird Gausslike verb) some more, if ya agree. This list is for me very Hardylike "usefull" for me, because I have no current working algorithm to produce it. But if someone had already made an Ulam cloth of primes, please let me (us) know.
user:XJamRastafire [2002.03.23] 6 Saturday (0) - the 3rd day of spring 2002. Natty Dread 20000 miles away from home. ==Largest known primes== This sentence appears under the heading 'Largest known prime': "This result with purely PC based computer with < 1GHz Pentium processor beat some previous prime-runners as supercomputer Cray T94 was." I can't be certain as to the meaning of this sentence, making it rather difficult to fix. Anyone? :Yes user:The Ostrich as it is evident from your user profile page you're already in computer's world so you should understand that (almost simple) computer's net fight of David against giant Goliath. I would not refuse one such model T94 if it would by a New Year's Day's present but anyway. You should check at fist GIMPS term to see how a small or a huge connected computers via the net can work very efficiently together. We can say that Wikipedia works in the same way. There are many examples (I know not all of them) of such work: Odlyzko's mathematical work with te Riele on Mertens conjecture (see for the current wikipedia status of this at [http://www.wikipedia.com/wiki/Talk:Moebius_function http://www.wikipedia.com/wiki/Talk:Moebius_function], SETI@home, ISDN-ODETTE conection of European automobile industry and many more) It is good to know Odlyzko and te Riele used for the job one of the "first" models of Crays - a model 1 (It sounds just like a fomous Ford's model T1). And probybly Odlyzko had decided to make some of his outstanding calculations on such dispersed "systems". He wrote some article on this subject too. As you like fractals can you give me any help on my previous instance about Ulam's cloth of primes? And actually it was exactly 500 MHz Pentium based PC to gain that recorld on the biggest Mersenne prime up to date. I hope this will kill the curiosity in cat. Greets to Ox from Ce. --user:XJamRastafire [2002.03.23] 6 Saturday (1st ed) :Sorry folks - above - I was talking nonsenses about Ulam's cloth. Ulam's prime spiral is as it is. I have already put its representation on wikipeda (see moebius function) so I don't have to make it again but anyway I do believe that mentioned list of primes is very important for everyone who wants to deal with primes. --user:XJamRastafire [2002.03.24] 0 Sunday (0) Someone should update this section . . . . The 42 Mersenne prime has now been found (February 2005). ==Gaps between primes == I moved the following material here for now: :For example the gap bettween 1693182318746351 and 1693182318746371 is ''g'' = 1693182318746351 - 1693182318746371 - 1 = 19, but the next consecutive gap ''g''₆₄ is 1131. This kind of gap is called ''maximal prime gap'' with property of occurences of gaps of ''at least of this length'' following initiating prime ''p'' and is the largest known maximal prime gap, found by T. Nicely and B. Nyman in 1999. :Jose Luis Gomez Pardo in 2001 found the largest first known occurence prime gap greater than 1131, which is 21611, following the initiating and ''certified'' prime 10⁹⁹⁹ + 24196831 but with its consecutive prime to be ''probabilistic'', that is, proven to be statistically prime (with a probability extremely close to 1), using, for example, Miller-Rabin test with multiple bases or some other primality test. There are of course many prime gaps with sizes from 1131 to 21612 but 1131 is the maximal one. This will probably change soon. Cram�r showed that if the Riemann hypothesis holds, it would be: g < k √p log p . Specifically, I have the following questions: what exactly is a ''maximal prime gap''. I do not understand the example and explanation given above. Second, it seems that Pardo did not infact find the largest gap, but just a probable gap, is that correct? Third, if there are many gaps with sizes between 1131 and 21612, how can 1131 be the maximal one? user:AxelBoldt ==Primorials== The largest known Primoral seems to be outdated; [http://primes.utm.edu/top20/page.php?id=5] mentions 392113#+1 ---- Let me say these things: //-1 Yes, strictly speaking primorial primes are not special case of factorial ones. Generating a 'prime product' for ''n'' as ∏(n) goes in 'a same manner' as a function ''n''! = 1 � 2 � 3 � 4 � 5 � 6 � ..., but we have to 'check' first its argumets for primality what is a bit harder than adding a number by 1. Thus 1 � 2 � 3 � 5 � 7 � 11 � ... is easy just for first numbers of ''n''. Try to get ∏(1234567890) by hand. I don't believe that even Carl Friedrich Gauss would solve in one hour ∏(100) as he did Σ(100). Another strictly mathematical question would be which primorial primes are members of factorial prime set or vice verse as for arbitrary ''n'' is ''n''!>∏(n). (Is this proven?) Are there any? I've found trivial 3!� 1 = ∏(3) � 1 = {7,5}, but here Nash's logic already ends... :Primorial primes can never be factorial except in the two cases you list. The reason is that all factorials beyond 3! are divisible by four, but products of different primes are never divisible by four. user:AxelBoldt //0 You didn't move just above material but you moved out also this: << This gap was discovered by Euclid in 300 BC. Others define it to be simply ''G'' = ''q'' - ''p'', so the gap ''G''₁ following the prime 2 has the length 1. Another definition for gap is with a parameter ''r'' = g/2 and some other authors have specified a gap by the terminating prime ''p''_k+1, rather than the initiating prime ''p''_k. >> :Yes, the slight variations in the definition of prime gap didn't seem to be important; the concept itself is more important. What exactly did Euclid discover? user:AxelBoldt Euclid was probably first one who was thinking about gaps, so that's why I had put him in the article. I've noticed that someone sometimes wants definitions and nothing more than definitions and sometimes not. I think I have explained also good enough what initiating prime and its 'bounded' partner are. Gaps are very close connected with primes, so they should be well defined for better understanding of primes themselves. ::Have no futher knowledges about Euclid's discovery. //1 The example explains the ambiguity of maximal gaps. There are no gaps with greater size than 1131 from 2 to initiating prime 1693182318746371. So 1131 is the largest one bellow this prime and it stands on 64th place. g₁=0 is first one. I don't know if a list of all known maximal gaps is appropriate for the article? We can put it in, if someone wants. :I see, that makes it clear. I'll put the maximal gaps back in. One more question: you say above that ''g₆₄ = 1131. Does that mean in your notation that the 64th prime minus the 63rd prime + 1 equals 1131? user:AxelBoldt :: No, no. Indexes of gaps and primes here are not equal at all. Perhaps 'late enough' would be ''p''_n-''p''_n-1=g_n+1-1 for some period or (it would be infinitive) after some initiating prime ''p''. In this case is: g₆₄-g₆₃+1=1131-923+1=208. But it is here ''p''_{X(of the 64th gap)}-''p''_{Y(of the 63th gap)}-1=''p''_Z=1693182318746371-1686994940955803-1=6187377790567. It is correct ''p''_X(n)-''p''_X-1-1=g_n-1 as it is in this first three examples: ''p''_{2(of the 2nd gap)}-''p''₁-1=g₁=3-2-1=0,''p''₄₍₃₎-''p''₃-1=g₂=7-5-1=1, ''p''₉₍₄₎-''p''₈-1=g₃=23-19-1=3 and so on). For now on we need pencil and paper to produce more examples. And after some time we would need a computer soon. And finally 923 is 63th maximal gap. Initiating prime for g₆₄ is 1693182318746371 but is not 64th prime. ::: Oh, so the ''n'' in ''g''_''n'' refers to the fact that ''g''_''n'' is the ''n''-th maximal gap? Then we have to change the notation in the article. user:AxelBoldt //2 (Probably) Yes. //3 I think gaps above 1131 were found in this way. Someone took some special types of primes and he calculated with one primality test gaps between them. Some were greater than 1131 but these primes were much bigger and much 'far away' than primes near 1 · 10¹⁶. Someone should examine all primes above initiating prime of the maximal gap g₆₄. I do believe that there exist a gap, let us say, g_x1=24242824248748732872000000000000000000000001, but, first nobody knows where and second, if he knows it, what would this help him to complete a gapopedia. And finally what are the still uknown properties of gaps we should look for? (I do hope I had understood Pardo's discovery and of others well enough. --user:XJamRastafire [2002.03.27] 3 Wednesday (0) ---- ==Defining 'prime number'== The first section gives two contradictory definitions of ''prime''. The first definition would imply -2 is not prime. The article should either give a single definition, or it should explicitly say that there are two different definitions in common use. The math dictionary I own gives only the second definition: ''an integer not equal to 0, 1, or -1, whose positive divisors include only 1 and itself''. :The first section gives two definitions of ''prime'', but they aren't really contradictory. One is a definition of primes in N, the other of primes in Z. Perhaps this should be made clearer. If the term "prime numbers" is used without further clarification it usually means primes in N, and I think this is how the term is usually used in Wikipedia. --user:Zundark, Thursday, April 4, 2002 :Yes the first definition is a bit deficient. In the second section is then said that primes can be negative natural numbers too. (In fact 1 is prime, but this is a convention, right?) How about 0? Why 0 is not a prime? We can't make natural factorization on it perhaps this would be too trivial. --user:XJamRastafire [2002.04.04] 4 Thur's day (0) :By the fundamental theorem of arithmetic, -2 cannot be prime, since (-2)² = 2² = 4. You also can't prime factorise -1 (and you can't uniquely prime factorise any negative number, or 0). Unless someone can demonstrate the usefulness of 'negative primes', implying 'prime natural number' every time you say 'prime' seems superfluous. We can also use the theorem to define primes P as the increasing sequence of integers {p₁,p₂,p₃,...} such that for all ''n'' ∈ N there is a unique sequence of integers X {x₁,x₂,x₃,...} where p₁^x₁�p₂^x₂�p₃^x₃�...=n (i.e. the primes are exactly those integers which can uniquely prime factorise every natural number). We can then show 1 isn't prime (or the prime factorisation of 1 wouldn't be unique, and therefore the corresponding set X has all elements set to zero), and 2 is prime, and no prime can be negative, etc (you can probably also show that there is only one P which satisfies these conditions, but I haven't proved that in my head yet). (I allow for x_i to be negative, but that still results in only one set of primes, which is trivial to prove. We can also use n ∈ Q, since rational numbers must also have a unique prime factorisation with some negative x_i) User:Elektron 11:34, 30 Apr 2004 (UTC) ::I've also corrected it and made it prettier and added bits. User:Elektron 12:14, 30 Apr 2004 (UTC) ::On the other hand, for a unique factorization domain and its appropriate definition, −2 ''is'' a prime; because then uniqueness is defined up to multiplication by a unit in the ring. User:Charles Matthews 12:08, 30 Apr 2004 (UTC) :::That went completely over my head User:Elektron 12:14, 30 Apr 2004 (UTC) ::::The point is that we have a concept of prime elements in any integral domain. The integers form an integral domain whose prime elements are the negative primes and the positive primes. The Fundamental Theorem of Arithmetic can be restated for this more general concept of primes, and it applies to all unique factorization domains. --User:Zundark 12:44, 30 Apr 2004 (UTC) :::::Right - but prime number really ought to stick to natural numbers, anyway. Other stuff should be done by links. By the way, this page pretty well takes the biscuit for being a confusing talk page. Anyone here competent and able to clean it up/archive stuff, without infringing any wikiquette? User:Charles Matthews 15:04, 30 Apr 2004 (UTC) :::::You can uniquely prime-factorise 1 (2⁰3⁰5⁰...), but you can't uniquely prime-factorise 0 or -1 no matter what you define as 'prime'. You can uniquely prime-factorise integers less than -1 (using the primes -2,-3,-4,-5,-6,-7,-9,-11,-13), but this limits you to an odd number of prime factors for every integer. My point is this: each natural number is uniquely represented by a sequence of prime indices (e.g. 1 ~ {0,0,0...}, 10 ~ {1,0,1,0,0,...}, 12 ~ {2,1,0,...}), and each sequence of prime indices uniquely represents a natural number. Extending this to zero or negative numbers doesn't work, and changing the fundamental theorem of arithmetic so that no 'uniqueness' is necessary seems icky. User:Elektron 09:19, 1 May 2004 (UTC) ::::::OK, perhaps it isn't so hard to understand, for example, that unique factorisation of polynomials is naturally stated as 'up to constants'. In any case anyone who wants to know the standard usage on unique factorisation in more abstract contexts has to get over this hurdle. User:Charles Matthews 10:39, 1 May 2004 (UTC) ::::::Elektron, I just wanted to re-assure you that what Charles and Zundark are saying is standard undergraduate mathematics (and has been for decades) and not some wacky left-field thing. "Uniqueness up to" is a pervasive and undoubtedly useful concept in algebra, although it may seem a little odd when meeting it for the first time. User:Pcb21 User_talk:Pcb21 09:06, 4 May 2004 (UTC) -1, 0, and 1 are ''not'' prime, by definition, because that definition is more useful than one that includes them. --LDC :When discussing primes it has always been the convention to assume we are only discussing primes in N: this is not a Wikipedia convention, it is found in all number theory AFAIK. When discussing negative primes (those not in N but found in Z) people will usually clearly identify this as such. Most mathematicians do not regard negative primes as particularly interesting, however one day someone may discover some fascinating property exclusive to negative primes and change this attitude. :The definition of 1, 0 and -1 as neither prime nor composite occurred because (as LDC rightly pointed out) there was no perceived benefit to a prime definition that included them, and it messed up an otherwise very useful definition. Until someone can prove that there is a genuine benefit to changing this definition (which has been around for several hundred years) this will probably remain the case. The quotient of 1/0 is left as "undefined" for similar reasons - having a defined value for 1/0 only messes things up and doesn't serve any (identified) useful purpose. :A request - could someone (Axel, LDC, other?) write the article on illegal prime? It sounds really interesting and I was keen to learn the rest of the story. - User:MMGB The reason that 1, 0, -1 are not considered prime nor composite can be best explained by thinking in terms of the concepts of general ring theory. We are looking at a commutative ring with unity. Prime elements in these rings are usually defined as elements ''p'' such that whenever ''p'' divides ''ab'', then either ''p'' divides ''a'' or ''p'' divides ''b''. EXCEPT that we exclude those elements that trivially divide everything in ring, in the case of the integers, these elements are 1, -1, which are called the UNITS of the ring. A prime is defined as a non-zero, non-unit, that satisfies the above property. 1 and -1 are excluded because they trivially divide everything. Zero is excluded because it only divides itself, nothing else. The reason the NEGATIVE primes are considered not so interesting is that we only really care about primes "considered up to a unit", i.e. primes which differ by a unit element are identified or associated with each other. Since 1 and -1 are the only units, this means every class under this relation has 2 elements, namely itself and its opposite, -3 isn't important because it's ALREADY identified with 3 by multiplication up to the unit element -1. -------- ::I suggest the following shortest possible and correct definition of ''prime'' for the Wikipedia article "Prime number": ::''A prime number is a natural number with exactly two natural divisors.'' ::Hans Rosenthal (hans.rosenthal AT t-online.de -- replace AT by @ ) ::PS: Never forget that here we are just seeking for a fine and simple definition of the term ''prime number'' ! ==Ulam spiral== According the the article, the Ulam spiral question is an open one. However, there is information about the origin of this pattern in M. Gardner, Sixth Book of Mathematical Games, Scribner?s, 1971 if someone would look it up. Anyhow, one quick explanation is that any prime (excluding 2 and 3) is equal to a multiple of 6 +/- 1. The reason for this is as follows: Break the primes into 6 columns (http://www.geocities.com/~harveyh/Image_No/Plot_Lin.gif, from http://www.geocities.com/~harveyh/moreprimes.htm . Anything in column 2, 4, or 6 is divisible by 3. Anything that is in column 3 is divisible by 3. Those numbers form the basis for diagonal patterns when using a spiral since the spiral offsets these numbers by 1 in each loop (looking at one particular side of the loop). :Have also a look at the discussion in Talk:Ulam_spiral. There is probably not much mystery left in Ulam's spiral. User:FvdP 11:53 Nov 19, 2002 (UTC) ==Formulae for primes == Here are the explicit formula for prime numbers, twinprimes, number of primes, number of twinprimes. It was published in the Proceedings of the Indian Academy of Sciences and reviewed by other mathematical journals. The formula was examined as correct by world renowned mathematicians such as Dr.Paul Erdos, Dr.Halberstien and Dr. K.Ramachandra of TIFR. The four formulae were discovered by Venu Atiyolil in the year 1983 and are presented below in the pdf format. The proof may be difficult to follow to some mathematics students as the method of writing was from a world class School of Mathematics where the author was a research member. http://www.ias.ac.in/jarch/mathsci/92/00000050.pdf http://www.ias.ac.in/jarch/mathsci/92/00000051.pdf http://www.ias.ac.in/jarch/mathsci/92/00000052.pdf http://www.ias.ac.in/jarch/mathsci/92/00000053.pdf http://www.ias.ac.in/jarch/mathsci/93/00000068.pdf ____________________________________________________________________ I was going to change the formulas to TeX, but some of them don't seem to make sense. Under "Formulas generating prime numbers", the first "alternately" definition given subtracts (j-1)! from itself. Thus the summation function is just 1/j. The second "alternately" divides j by itself. This also effectively means (j-2)! is subtracted from itself, so the summation function is 0. These are obviously incorrect. What exactly is to be done about these? User:Eric119 06:30 Feb 17, 2003 (UTC) :Um, never mind this. Silly me, I didn't catach on that [x] was given as the floor function. I thought it was just normal bracketing. Okay there are no problems with the formulas now (except I still need to convert to TeX...). User:Eric119 06:41 Feb 17, 2003 (UTC) ----- *why does composite link to Prime? --PY ---- An anon user added some bogus about prime number formulae. Please do note that the number of computations in these formulae is at least as big as the number of computations involved in optimised versions of Erastothenes' sieve for a number of comparible size. Can someone make it NPOV? User:Gebruiker:Dedalus 12:24, 28 Feb 2005 (UTC) :I've reverted the page, and I'm moving the information about Venu Atiyolil's contributions to formula for primes, where I will rewrite it NPOV. -- User:Dominus 14:47, 28 Feb 2005 (UTC) :I replaced the link to the author's GeoCities site (which was unreliable, since the paper in question was only downloadable at bitmap images that soon exhausted his bandwidth quota) with links to the PDF archive version of the pages on the official web site of the Indian Academy of Sciences. -- User:Dominus 15:09, 28 Feb 2005 (UTC) I've reverted all the changes by this anon guy. He keeps adding info to articles when it's been moved from one article to another, and he also has been deleting/altering comments on talk pages. User:CryptoDerk 03:13, Mar 5, 2005 (UTC) ==First 25 primes== I don't like the table "The First 25 Primes". Apart the number themselves, there is no really interesting and relevant information. The length of periods of inverses in base 10 has some interest but is not relevant or interesting enough for ''this'' article. Who minds how one writes the prime numbers in binary ??? That should be an "exercise left to the reader" ;-) User:FvdP 20:53, 30 Oct 2003 (UTC) So I removed it ("be bold" !) and here is it: _n p_n Binary 1/p Len 1 2 10 0�5 1 2 3 11 0�3... 1 3 5 101 0�2 1 4 7 111 0�142857... 6 5 11 1011 0�09... 2 6 13 1101 0�076923... 6 7 17 10001 0�0588235294117647... 16 8 19 10011 0�052631578947368421... 18 9 23 10111 0�0434782608695652173913... 22 10 29 11101 0�0344827586206896551724137 931... 28 11 31 11111 0�032258064516129... 15 12 37 100101 0�027... 3 13 41 101001 0�02439... 5 14 43 101011 0�023255813953488372093... 21 15 47 101111 0�0212765957446808510638297 872340425531914893617... 46 16 53 110101 0�0188679245283... 13 17 59 111011 0�0169491525423728813559322 0338983050847457627118644 06779661... 58 18 61 111101 0�0163934426229508196721311 4754098360655737704918032 7868852459... 60 19 67 1000011 0�0149253731343283582089552 23880597... 33 20 71 1000111 0�0140845070422535211267605 6338028169... 35 21 73 1001001 0�01369863... 8 22 79 1001111 0�0126582278481... 13 23 83 1010011 0�0120481927710843373493975 9036144578313253... 41 24 89 1011001 0�0112359550561797752808988 7640449438202247191... 44 25 97 1100001 0�0103092783505154639175257 7319587628865979381443298 9690721649484536082474226 804123711340206185567... 96 ==The Bear == Should there be a link to Prime Number Shitting Bear on this page? Right now that page is essentially an orphan :) User:Adam Bishop 20:30, 3 Dec 2003 (UTC) :I've added it. User:Arvindn 03:59, 4 Dec 2003 (UTC) == What is a prime number == A prime number is a number with exactly two factors. What is wrong with this simple definition? Why worry about 1? It is stated, that the definition given is used throughout Wikipedia. Check that out (e.g. german version). : 6 has two factors, 2 and 3, but isn't prime. User:Dysprosia 12:15, 26 Feb 2004 (UTC) :: 6 has four factors (1, 2, 3, and 6), not two. -- User:Dominus 22:09, 26 Feb 2004 (UTC) ::: That's what one gets when one edits late at night ;) I was thinking proper divisors only... User:Dysprosia 22:51, 26 Feb 2004 (UTC) :"What is wrong with this simple definition?" Well, it's simple, but the word "exactly" looks quite arbitrary at first sight (at least it did so to me, when I saw it for the first time, quite a long time ago). The real reason for not including 1 is that somehow, from the point of view of products, 1 is "empty", while the primes "have content". Where "to have content" can be defined as "to have at least 2 factors". That's why it's "exactly" rather than "at most". I think this should be explained, instead of asking people to blindly rely on definitions. User:FvdP 18:52, 26 Feb 2004 (UTC) Really, this is a FAQ. Should it have its own page? Not because there is a second point of view on whether 1 is a prime. But perhaps because some historic tables of primes did start at 1. User:Charles Matthews 22:12, 26 Feb 2004 (UTC) Being bored one summer I sat down and with nothing more than a pen and some paper worked out all the primes between (but not including) 1 and 10000. I later found out that I had created an optimised version of the Sieve of Eratosthenes (o=N*N). However, by doing this I came to the conclusion that the divisors definition is wrong and taught only because it is simple to write down. If you look at the sieve method you should see that what you've got is NOT a definition of what is prime, but rather what is non-prime. From that you work out that what is remaining of your set of numbers is a set of primes. To put it another way... a non-prime = X * a prime. Where X can be either prime or non-prime. This simple equation has some important consequences. If we include 1 in the set of non-primes it can be used in the equation by replacing X with 1, then we'd get the following equation... non-prime = 1 * a prime. Therefore non-prime = prime. Which of course would make all primes also non-prime! (still with me?). The alternative is to make 1 prime, which would produce the following equation... non-prime = X * 1. Therefore non-prime = X. Which would make every value non-prime, including 1! (didn't we just make it prime?) As you can see this is a problem, but only if we place the value '1' into one of the sets 'prime' or 'non-prime'. The answer is remarkably simple - it's neither. Once I realised this it pointed out how remarkably stupid the divisors 'definition' is and meant I finally knew why the value of 1 is not prime. I haven't looked into what other consequences this could have, like in the negative realm - I'm not a mathemagican! However I did go back to my maths teacher and explained this to him, he was very impressed, but decided to keep teaching the old system, but such is life. : In a sense your are correct: 1 is regarded in mathematics as a 'unit', which is object distinct from primes and composite numbers. : But your equation ''non-prime = X * a prime'' is simply not true if X is allowed to be 1 (what in mathematics is called a 'multiplicative identity'). You've generalized an equation past its point of truth, and then think that its consequences are somehow profound. -- User:Saforrest 14:58, Feb 11, 2005 (UTC) ::I learned counting starting with zero. Prime numbers have exactly two divisors. For example, 2 has divisors 1 and 2. And 1 has only 1 divisor, and that divisor is 1. Therefore, 1 is not a prime. Neither is it a composite. A composite has at least three divisors, or at least two proper divisors. The table of prime factors included 1 as a prime factor of 1, that was to silly. User:Gebruiker:Dedalus 21:59, 15 Feb 2005 (UTC) I see where I have gone wrong. The method I was taught was - a prime is a number which can be DIVIDED only by itself and 1 (a truely incorrect definition!). I apologise about the confusion that I may have caused with divisors. However, I still believe that the definition of a non-prime has value and can reduce confusion about what is prime. Especially since everyone I have ever talked to about this believe 1 to be prime (or non-prime)! ==List of prime number topics== what about an article "List of prime number related articles"? I think it'd be nice to gather them all in a page so people could read all about prime numbers that wikipedia has... User:Kieff 02:42, May 4, 2004 (UTC) It's not a bad idea. Th raw material should all be at List of number theory topics, if someone wants to compile such a list. User:Charles Matthews 09:44, 4 May 2004 (UTC) == Prime Numbers in Science == I have moved this from the article: ''Pradeep Kumar, Plamen Ch. Ivanov, and H. Eugene Stanley discovered an interesting pattern in the distribution of prime numbers.'' This is recent work (see http://xxx.lanl.gov/abs/cond-mat/0303110); it might merit inclusion somewhere, but I'd like to see more background. After all, the statistical properties of the primes have been studied intensively. User:Charles Matthews 09:31, 4 May 2004 (UTC) ------------- Removed: The first recorded prime numbers were found in Africa on the Ishango bone dating back to 6,500BC. They were 11, 13, 17, 19. As firstly it's unclear what this statement actually means, and secondly googling there seems to be little evidence that these numbers were intentionally prime. --User:Gunter 22:18, 31 Dec 2004 (UTC)The statement is obvious. lunar calendar or not is besides the point, they are the first recordings of prime numbers -------- From the "Prime gaps" entry: "We say that g_n is a maximal gap if g_m < g_n for all m < n. The largest known maximal gap is 1131, found by T. Nicely and B. Nyman in 1999. It is the 64th smallest maximal gap, and it occurs after the prime 1693182318746371." Is the second sentence of the above statement still up-to-date ? Hans Rosenthal (hans.rosenthal AT t-online.de -- replace AT by @ ) == Website == I don't want to put it right into the article since I made it myself, and I would feel like I was spamming, but someone might enjoy http://jax.hopto.org/maths/books/prime/ , which is an article on Prime Numbers I wrote. == This page == Could "some part" of this page be put into an archive (as it is getting long)? == Primes in other base systems == How do prime numbers work when numbers other than 10 are used (eg base 6, base 23 etc)? Would there be different primes, more of them or less of them? :Prime numbers are not defined in terms of a base. They are the same numbers however you write them. --User:Zundark 18:12, 23 May 2005 (UTC) == Likelihood x is prime == From prime number theorem: ''One can also derive the probability that a random number n is prime: 1/ln(n).'' I ''know'' this is normal shop talk (I am a number theorist myself), and I have heard such statements for years, but that still doesn't stop me from having the right to the opinion that such a statement is complete nonsense. Actually, the way it is worded now in the article is fine with me...I included "randomly-chosen" just for all the non-math, or non-number theory oriented readers. But, I still feel that statements such as the above are misleading at best and damaging at worst. I am not alone in this sentiment: while talking a number theory/complex analysis class at Univeristy of Oregon, the teacher (Dick Koch) recalled a conversation he had with a non-number theorist and when he said "the prime number theorem tells you the probability that ''n'' is prime", his colleague insisted he was talking nonsense. Of course, we all know what we "really" mean when we say something like this, but I think it's more instructive to give an ''example'': if you choose the 1,000 natural numbers between 1,000,001 and 1,001,000, then you will expect to find roughly 1,000/ln(1,000,000) primes amongst them. This is a more helpful way of explaining it, I think. But, again this is just my opinion. User:Revolver 10:05, 31 May 2005 (UTC) As I keep repeating, the problem with people writing pages that they don't understand very well is an inability to be imprecise. The reason is that they need the details in order to understand the concepts. This leads to overly technical explanations that fail to address the basic conceptual issues. Moreover, this whole field is about forgetting details (asymptotics). As I wrote elsewhere on this page, heuristic (that is, non rigourous) probabilistic reasoning leads to correct conjectures about the distribution of primes. Not only that, but rigourous results are often obtained by trying to make these arguments precise, in particular, sieve theory. For example, the large sieve is essentially based on the hypothesis that the primes in different arithmetic progressions are probabilistically independent. User:Ilanpi 10:34, 31 May 2005 (UTC) :I understand what the PNT says, and I understand what the intended meaning of your original wording was. My point is that the ability to be imprecise is an ''achievement'' that only comes from lots of experience and familiarity with these areas of research. For the seasoned researcher who has been thinking about these issues for years, such imprecise thinking is very useful in many ways, in the manner you describe. I'm less optimistic about how useful it is to people trying to learn this stuff for the first time. I'm really pessimistic about how useful it is to the kind of general, mathematically naive reader who visits a popular page like this. Saying "for large ''n'', the probability that ''n'' is prime is 1/ln(''n'')" means a lot, if you already have a fundamental understanding about what the PNT says, and you have experience in interpreting these kinds of statements. If you ''don't'' already understand PNT, or you have little experience thinking in this way, I wonder if such a statement is more confusing than enlightening, that's all. You said it yourself -- "they need the details in order to understand the concepts". You were talking about authors, but doesn't the same observation apply to readers? User:Revolver 11:08, 31 May 2005 (UTC) :I believe that the person who doesn't understand probability in a technical sense, e.g., thinks he understands when he hears the weather report saying that the probability of rain is 50%, will accept a statement like: "the probability that a large number is prime is 1/its digits" and will have some kind of understanding which is a lot better than the student trying to understand all the steps in the actual proof of the prime number theorem, taught by someone who never gave any motivation. It reminds me of me, when I was taking analysis in university, and I never understood Fourier series, as taught by my pure math professor. Years later, I looked at signal processing books, and the following explanation came to mind: "Fourier coefficients are the graphic equaliser on your stereo," which would have helped me a lot earlier. On the other hand, you have a point, that suppressing details can be more of a barrier for people who actually know the subject somewhat. However, these people should look at a textbook, instead of this site. User:Ilanpi 11:29, 31 May 2005 (UTC) ''(so theoretical physicists would just regard them as being true)'' :This seems to be stretching it. Even theoretical physicists still acknowledge the distinction between convincing heuristic arguments and according-to-Hoyle proof?? Or am I missing something? User:Revolver 11:20, 31 May 2005 (UTC)

See other meanings of words starting from letter:

P

PA | PB | PC | PD | PE | PF | PG | PH | PI | PJ | PK | PL | PM | PN | PO | PR | PS | PT | PU | PW | PX | PY | PZ |

Words begining with Prime_number:

Prime_number
Prime_number
Prime_Numbers
Prime_numbers
Prime_numbers
Prime_Number_Shitting_Bear
Prime_Number_Shitting_Bear
Prime_number_shitting_bear
Prime_number_spiral
Prime_number_theorem
Prime_number_theorem
Prime_number_theory