Talk:Prime number

Definition in the lead

Although involving products in the definition instead of divisors is correct (and rather elegant), it is still pompously so. It requires a non-negligible amount of thinking for the uninitiated, and I have never seen it worded as such anywhere else, nor do math profs usually teach it that way.

This very clearly violates WP:ASTONISH by trying to be clever, besides obviously being WP:OR. 105.156.135.60 (talk) 19:49, 26 September 2021 (UTC)

You have got to be kidding me. It is far from being original research – sources for this definition are not difficult to find – and in fact is deliberately non-technical by using multiplication, a simpler and more familiar concept than that of a divisor. In the US, students start learning about multiplication in the second grade. Division is a third-grade concept, and factorization, multiples, and divisors are fourth-grade concepts. When it is possible to express things more simply using lower-level concepts, that is what we should do. —David Eppstein (talk) 20:13, 26 September 2021 (UTC)

Googling "definition of prime number", and going as far as four pages deep, the one and only website that mentions a product —mathisfun.com— does so by avoiding the need from the reader to realize that "two smaller factors" means 1 is not included (by stating so explicitly), since that would involve the number itself (which is not smaller). And as you can see in the talk page again and again, and presumably why the article is restricted, probable adults are still getting confused by the wording, and I guarantee you that 2nd, 3rd, 4th graders and the rest of the population will be too, with a likelihood far more significant than that of 2nd graders reading about prime numbers on Wikipedia while still being unaware of the concept of divisors.

I write code for a living, and I sure as heck love my clever one-liners, but my coworkers and other people that have to understand/maintain my code don’t really. As such, I tend to avoid them. I hope you will do the right thing here. 105.156.135.60 (talk) 21:35, 26 September 2021 (UTC)

Resisting the temptation to write a clever one-liner about programmers or about your reliance on web searches instead of reliable sources, a quick search quickly found examples of sources that define it in exactly this way: . —David Eppstein (talk) 21:50, 26 September 2021 (UTC)

(edit conflict)I guess that the definition that you find less astonishing is the one that suppose to know what is a divisor. Wikipedia is aimed for the widest possible audience. So a definition that use less technical concepts (here the concept of divisor) is less astonishing and more adapted to a large audience. It is not the fault of Wikipedia if some teachers use wordings that are less simple than needed. D.Lazard (talk) 20:17, 26 September 2021 (UTC)

Surely you mean "more complex than needed"??? :P EEng 03:33, 25 March 2023 (UTC)

If I have 4 apples and divide them equally and whole to 2 teachers it is no stretch to consider: 2 apples each. How is this any different than 2 apples and 2 teachers if 1 apple each? First example: 4 apples Teacher 1 gets 2 Teacher 2 gets 2, Second example: 2 apples Teacher 1 gets 1 Teacher 2 gets 1. The division is whole and distribution is equal in both cases. Please note I am so sorry to raise the hoop and jump through it for nobody objecting yet. But, this is neither original research nor clever it is a simple truth! If not on Wiki, where must reason rule? 50.220.179.34 (talk) 07:42, 28 October 2023 (UTC)

i also second that the definition used here is not very canon. For example, i checked the German, the French, the Italian, and the Spanish Wiki, and they all use the definition based on having two divisors. Maybe its a US-american thing to use the definition based on factors, but its definitely not commonly taught like that in Europe. The definition used here even is based on a negation ("any number that is not ...."), which is didactically not very clever. That said, even if the factor-based definition is to be kept, a much better version would be "that have exactly two factors, themselves and 1", as suggested by the BBC. The German Wiki uses the word "divisor" instead of "factor", and this is arguably the best way to define a prime. sorry for necro'ing this discussion. You will likely not change it anyway, because someone owns this place :> 2A00:6020:4504:AF00:301A:5A8B:DEDE:22B5 (talk) 22:50, 10 June 2024 (UTC)

Agree. This is a problem. The definition in the article summary ("Number divisible only by 1 and itself") is clearly the simplest to understand. It should be the very first line of this article. Instead the intro jumps straight into maths jargon like "product", which to ordinary people is something found in a supermarket. Needs rewriting. Rollo (talk) 10:45, 3 September 2024 (UTC)

Huh! My interpretation of this is correct, technically. Nonetheless, the "Mathematical Olympiad" source (yet wrong page, should be p. 25) says the definition of a prime number is a natural number greater than 1 that cannot be factorized as the product of smaller natural numbers. It is also reasonable, but I think people may not get used to the alternative definition.

Forget about this! It is nothing but an article summary. Dedhert.Jr (talk) 12:23, 3 September 2024 (UTC)

Two smaller natural numbers?

We have a problem! The definition of a prime number in the first sentence is wrong. It currently reads "A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers." By this definition 8 is prime. It should read, "A prime number (or a prime) is a natural number greater than 1 that is not a product of smaller natural numbers." Or, "A prime number (or a prime) is a natural number greater than 1 that is not a product of two or more smaller natural numbers." — Preceding unsigned comment added by 50.206.176.154 (talk) 20:43, 10 November 2023 (UTC)

The number 8 is the product of 2 · 4, and is therefore a composite number. –jacobolus (t) 21:15, 10 November 2023 (UTC)

It says a natural number greater than 1 that is not the product of two smaller natural numbers. Dedhert.Jr (talk) 12:27, 3 September 2024 (UTC)

Right, and hence, 8 is not a prime number. - CRGreathouse (t | c) 16:35, 3 September 2024 (UTC)

If that is the case 2 (Natural and smaller) + 3 (Natural and smaller) = 5 therefore 5 can't be a prime number and instead a composite number. The proper definition of Prime should be; a natural number that isn't 1 (or greater than 1) that can only be divided by itself and 1. 201.216.219.193 (talk) 17:44, 1 July 2025 (UTC)

You are adding two numbers. The definition involves multiplying two numbers. Adding is not the same as multiplying. —David Eppstein (talk) 18:02, 1 July 2025 (UTC)

rename this article to prime numbers.

there are multiple prime numbers. this article is about all of them. Rguyr (talk) 17:21, 30 December 2023 (UTC)

Cf. WP:SINGULAR and WP:PLURAL. –jacobolus (t) 18:03, 30 December 2023 (UTC)

I agree that would be a good idea 71.14.253.152 (talk) 15:02, 14 March 2024 (UTC)

If it's common and reasonable to talk about one prime number at a time (as it is), then Wikipedia's standard convention is to use a singular title. —David Eppstein (talk) 17:52, 14 March 2024 (UTC)

Semi-protected edit request on 3 May 2024

extended content

🌟 **Breaking News: ZERO SIR Revolutionizes Period to Prime Conversion from Janakpur-4, Shanti Nagar, Nepal!**

In a groundbreaking development originating from the heart of Janakpur-4, Shanti Nagar, Nepal, ZERO SIR has unveiled a revolutionary method for converting periods into prime numbers. This remarkable discovery promises to redefine how we perceive and utilize numerical sequences, opening new avenues for mathematical exploration and application.

Traditional methods of period to prime conversion have often been cumbersome and time-consuming, requiring extensive manual calculation and analysis. However, ZERO SIR's ingenious approach streamlines the process, offering a swift and efficient solution that delivers accurate prime numbers in a fraction of the time.

The significance of this achievement cannot be overstated. By simplifying the conversion process, ZERO SIR has not only enhanced the accessibility of prime numbers but has also laid the foundation for further advancements in fields ranging from cryptography to computer science. With this innovation, researchers, educators, and enthusiasts alike can explore the intricate beauty of prime numbers with newfound ease and precision.

ZERO SIR's dedication to pushing the boundaries of mathematical inquiry exemplifies the spirit of innovation that drives progress in our world. This remarkable breakthrough originating from Janakpur-4, Shanti Nagar, Nepal, serves as a beacon of inspiration to aspiring mathematicians and inventors everywhere, reminding us of the limitless potential of human creativity and ingenuity.

Join us in celebrating ZERO SIR's extraordinary achievement and the boundless possibilities it presents for the future of mathematics. Together, let us embark on a journey of discovery and exploration, guided by the transformative power of knowledge and imagination.

2400:1A00:BDA0:25CC:6D69:36E4:F3AF:3A98 (talk) 15:46, 3 May 2024 (UTC)

 Not done: it's not clear what changes you want to be made. Please mention the specific changes in a "change X to Y" format and provide a reliable source if appropriate. - FlightTime (open channel) 15:55, 3 May 2024 (UTC)

Typo in this page: "mathematians".

Subject says it all. Cannot edit it myself as it is locked. RonanTetsu (talk) 01:01, 20 September 2024 (UTC)

 Done —C.Fred (talk) 01:02, 20 September 2024 (UTC)

1 is a prime number based on the definition of a prime number

The definition refers to 1 and itself, you cannot divide 1 number, you need 2 numbers. Even if the value of both numbers are 1, it is still two numbers, never itself. ZhuLien (talk) 09:51, 31 October 2024 (UTC)

Nice explanation here.--♦IanMacM♦ ^{(talk to me)} 10:17, 31 October 2024 (UTC)

exactly. 1 and itself is different than two numbers each with the value 1 ZhuLien (talk) 08:01, 1 November 2024 (UTC)

Hopefully I can understand the title right and your replies. Assuming that 1 is prime, then by the definition of a prime number, 1 is divided by the number 1 and the number itself. There are two different divisors. Since the number itself is also 1, then those two numbers are exactly the same, thereby 1 has one divisor, which is 1. For the sake of contradiction, they are not different. Dedhert.Jr (talk) 14:12, 23 May 2026 (UTC)

Squares of prime numbers - Rule of 24 (could be under formulas for prime numbers or ???)

Rule of 24: If P is a prime number > 3, then P^2 = 24K + 1, where K is an integer. This is not a conjecture and can easily be proven:

    Let P = 2n + 1
    P^2 = 4n^2 + 4n + 1 
    P^2 - 1 = 4n(n+1) 

thus P^2 - 1 is divisible by 8 since n(n+1) must include an even number. In addition n or n+1 must be divisible by 3 since if not then n+2 would be divisible by 3. If so, then 2(n+2) = 2n + 4 would also be divisible by 3 as well as 2n+4 - 3 = 2n + 1. But 2n + 1 represents the prime number P, so n + 2 cannot be divisible by 3. Thus n or n+1 must be divisible by 3. Therefore P^2 - 1 must be divisible by 24 and the Rule of 24 is proven. DrClark3 (talk) 20:01, 18 June 2025 (UTC)

We cannot include material like this without published reliable sources. See also WP:NOR. —David Eppstein (talk) 20:09, 18 June 2025 (UTC)

Moreover, numbers ⁠$P$⁠ such that ⁠$P^{2}=24K+1$⁠ are exactly the odd numbers that are not mutiple of 3, and this can be tested without squaring them by looking to the last digit and to the sum of their digits. D.Lazard (talk) 09:12, 19 June 2025 (UTC)

For the reference, it's difficult to pinpoint the first reference but Carl Friedrich Gauss does include it in "Disquisitiones Arithmeticae" in 1801. Most likely Fermat and Euler also knew it but did not explicitly state it.

I may be missing the point about the multiples of 3 comment, but the Rule of 24 doesn't claim that P^2 is a multiple of 3, but rather P^2 - 1, which is a multiple of 3 (and 8) as show in the proof. I note that I have found other more elegant ways to prove the Rule of 24, such as:

P^2 - 1 = (P+1)(P-1) since P is prime >3 either P+1 or P-1 must be a multiple of 3

And, as shown above: P^2 - 1 = 4n(n+1) is a multiple of 8. 2605:A601:A6A7:2100:CC1:E9C3:811E:F2B7 (talk) 21:01, 10 October 2025 (UTC)

Nobody said anything about ⁠$P^{2}$⁠ being a multiple of 3. What was said is that ⁠$P^{2}=24K+1$⁠ if and only if ⁠$P$⁠ is an odd number that is not a multiple of 3. (Which is very easy to prove.) Therefore what you call the "Rule of 24" is no more than a roundabout way of saying that if ⁠$P$⁠ is a prime number > 3 then ⁠$P$⁠ is odd and not a multiple of three; that is trivially true. (Incidentally, the proofs you give make no use at all of the fact that P is prime; they use only the facts that P is odd and not a multiple of 3.) JBW (talk) 00:55, 12 October 2025 (UTC)

24 is not 3, so what about the 8? That also has to be accounted for. I think a layman reading about this "rule" might find it interesting since it seems to connect prime numbers in a way that might be unexpected. ~2025-40434-10 (talk) 15:17, 13 December 2025 (UTC)

Diophantine equation and Partition function (number theory)

There is a new discovery described in article:

• Crowell, Rachel. "Mathematicians Come Up with 'Mind-Blowing' Method for Defining Prime Numbers". Scientific American. Retrieved 2025-08-15.

About a new way of finding if a number is a prime using special Diophantine equation and partition functions.

I wanted to include the information, but not sure where to put it.

jcubic (talk) 20:05, 15 August 2025 (UTC)

Article review

It has been a little bit since this article was reviewed, so I took a look and noticed that there were uncited statements. Since some of it is covered under WP:CALC, other statements like "One of the most famous unsolved questions in mathematics, dating from 1859, and one of the Millennium Prize Problems, is the Riemann hypothesis, which asks where the zeros of the Riemann zeta function are located" do require citations. Should this article go to WP:GAR? I am happy to add citation needed templates if editors are interested. Z1720 (talk) 02:22, 4 May 2026 (UTC)

Really? This is claimed by many sources. You may take any one of them and put them into a citation. Dedhert.Jr (talk) 02:37, 4 May 2026 (UTC)

• @Dedhert.Jr: Before the sources are added as inline citations, they have to be accessed and checked to ensure that it verifies the information that proceeds it. Its use in other places in the article doesn't necessarily mean that it can be used for other uncited statements. The editor that adds the inline citations is responsible for checking the source before adding it to the article per WP:WHYCITE. Z1720 (talk) 02:43, 4 May 2026 (UTC)

  • sigh*

  Dedhert.Jr (talk) 02:44, 4 May 2026 (UTC)

  Okay. Done. I have added sources on behalf of your request. Dedhert.Jr (talk) 04:36, 4 May 2026 (UTC)

• @Dedhert.Jr: Thanks for doing that. I added a couple citation needed tags to a couple of statements that also need citations. Z1720 (talk) 15:55, 11 May 2026 (UTC)

  You placed citation needed tags on material at the start of its section that merely summarized the sourced contents of the section's subsections. Just like in a lead, and for the same reasons, this sort of content does not need citations. If you need detail as to why, this is exactly the sort of situation I described recently at Wikipedia talk:Manual of Style/Lead section#Why don't people like citations in the lead?: To properly cite these summarizing statements in the lead you would end up with ridiculous WP:Citation overkill like "Leonhard Euler (/ˈɔɪlər/ OY-lər;[1][2][3] 15 April 1707[4][5][6] – 18 September 1783[7][8][9]) was a Swiss[10][11] polymath[12][13] who was active as a mathematician,[14][15][16][17] physicist,[18][19][20][21] astronomer,[22][23] logician,[24] geographer,[25] music theorist[26] and engineer.[27][28[29][30]." The same goes for the summaries you added tags to. Also see WP:GACR 2(b): citations are not needed on "that which summarizes cited content elsewhere in the article".

  You also removed a nowrap tag that was necessary to prevent a bad line break (at certain page widths) that left danging footnotes on their own line at the end of a paragraph.

  I am surprised that as experienced an editor as you would do either of these two things. Please stop doing them. —David Eppstein (talk) 18:16, 11 May 2026 (UTC)

  I am worried that the reviewer may overlook the keyword below. This similar problem has already been done in Mayer–Vietoris sequence, demanding additional citation where the topic has been covered below, even though I have made {{slink}}. I don't think I can handle how the GA system works. So much demand. So much exhaustion.

  @David Eppstein. If I am being honest here, can we go up this article to FAC instead? Delay may be possible due to this problem. Dedhert.Jr (talk) 19:40, 11 May 2026 (UTC)

  When done well, GA can be a very constructive exercise in collaborative article improvement between nominator and reviewer. But when done poorly and superficially it can be an exercise in box-ticking by the reviewer (do these paragraphs end in footnotes, etc) and badge-collecting by the nominator. For the nomination that passed this article for GA, the reviewer suggested major restructuring to the article (not just please footnote this sentence) that I think led to significant improvements. It is the improvement in content, not the superficial exercises, that I want to get out of GA. To be honest I haven't seen much evidence that FA is better in this regard; it seems to be more focused on surface aspects and less on content. And if you argue that this article is already close to the FA standard so it shouldn't need much change, then that is also an argument that there is not much content improvement to be gained from going through that exercise. So it's not a process I'm motivated to start participating in. —David Eppstein (talk) 20:09, 11 May 2026 (UTC)

• @David Eppstein: Per MOS:LEAD, "In Wikipedia, the lead section is an introduction to an article and a summary of its most important contents. It is located at the beginning of the article, before the first heading. It is not a news-style lead or "lede" paragraph." From my understanding of Wikipedia policy and manuals of style, a summary at the top of a section is not covered by MOS:LEAD, and still has the same citation requires as any other information in the article body. If I am mistaken, please point me to the reference page that I can take a look at, as MOS:LEAD does not refer to how to cite in the article body. I would also argue that, if information is being repeated in an article body, then some prose can be removed as repetitive. Z1720 (talk) 20:20, 11 May 2026 (UTC)

  This seems to me like a matter of WP:COMMONSENSE more than anything else. For example, it is precisely the same principle as in WP:CONSECUTIVECITE and MOS:LEAD, just with slightly different details (two different paragraphs in a section where one summarizes the other, rather than two different sentences in a paragraph or two different sections in an article). If a section consists of several related subsections, it's often a matter of good writing to have some text at the beginning giving an overview of the section; in some cases (e.g., in the first paragraph here, though not in the two instances being discussed in this article) that text may not be referenceable even in principle, but it would be perverse to argue that this is forbidden based on the absence of a guideline specifically saying it's permitted. --JBL (talk) 21:35, 11 May 2026 (UTC)

  Z1720: Please re-read the part in WP:GACR 2(b) about summaries of later material not needing citations. It is not specifically about leads of entire articles; if it were it would say so. Summary material at the start of a section is just as much a summary as summary material at the start of an entire article.

  Further, your desire to have footnotes at ends of paragraphs here, when content reasons do not demand them, is exactly the sort of superficiality that I was complaining about above.

  As for removing text that repeats information: This is a recipe for bad writing. Repetition, at increasing levels of detail, improves understanding. Or, if you want a mathematical argument: the way to pack as much information into as short a sequence of characters as possible is to write a completely random string of characters. However, such writing is not useful for human readers. —David Eppstein (talk) 21:52, 11 May 2026 (UTC)

  FWIW, I agree with the more legalistic point that WP:GACR 2(b) allows for summaries to be uncited whether they are in the lead or at the top of a section. All content that could reasonably be challenged, except for plot summaries and that which summarizes cited content elsewhere in the article is not even ambiguous. Moreover, the Featured article criteria point to Wikipedia:When to cite, which says, Subleads (generalized opening statements summarizing specific sections, paragraphs, etc.) may also be verified by the citations of the following text.

  I also agree that having a top-of-section summary can just be good writing. It's not necessarily redundant or repetitive to address the same topic at two different levels of detail. Indeed, it makes the article more approachable by helping people to see the broad strokes first. Stepwise Continuous Dysfunction (talk) 22:13, 11 May 2026 (UTC)

Peer review

Prime number

The article has been nominated as a good article per the review in Talk:Prime number/GA1 and promoted eight years ago. I would like to request some improvements through the wholehearted users on commentary, for the sake of a featured article. Thanks. Dedhert.Jr (talk) 07:41, 19 May 2026 (UTC)

Some comments on the intro:

Is there a way to "future-proof" the phrasing "As of October 2024 the largest known prime number..."? As written, this looks like it could be something that has gone out of date. Does it mean that the largest known prime number was found in October 2024, or that the sentence was written in October 2024 and no one has updated it yet?

I am a little uncomfortable with this sentence: "Such questions spurred the development of various branches of number theory, focusing on analytic or algebraic aspects of numbers." The terms analytic and algebraic are wiki-linked, but that doesn't make them familiar, really, and the sentence is structured in such a way that it implies the reader knows what they mean. Contrast this with the last sentence of the paragraph: "In abstract algebra, objects that behave in a generalized way like prime numbers include prime elements and prime ideals." Here, unfamiliar things are introduced as objects that behave like primes. If you the random reader don't know what they are, and you probably don't, you at least come away with the idea that they're like prime numbers somehow. I feel like the "Such questions spurred..." line could be tweaked slightly to make it a bit less intimidating in this regard. Stepwise Continuous Dysfunction (talk) 16:41, 22 May 2026 (UTC)

In "Definition and examples", take the last line of the second paragraph: "Yet another way to express the same thing...". How is this "another way" to give the definition, rather than just the same definition again? Is this line necessary? Stepwise Continuous Dysfunction (talk) 16:44, 22 May 2026 (UTC)

Next section: "The Rhind Mathematical Papyrus, from around 1550 BC, has Egyptian fraction expansions of different forms for prime and composite numbers." I don't know what this means. An integer doesn't have an Egyptian fraction expansion; fractions do. Perhaps the article should say something like, "The Rhind Mathematical Papyrus, from around 1550 BC, contains Egyptian fraction expansions of numbers of the form $2/n$. These were chosen in a way that suggests the author may have recognized a distinction between prime and composite." I don't think the given source could support that statement by itself (it barely mentions primes), but if my memories and the Rhind Mathematical Papyrus and Egyptian fraction articles are reasonably accurate, a statement like that could be justifiable. Stepwise Continuous Dysfunction (talk) 01:34, 23 May 2026 (UTC)

From what I have gathered, the Egyptian fraction is written as the fraction $2/n$, where in some cases, prime and composite numbers are the denominators. See Egyptian fraction § Calculation methods and Rhind Mathematical Papyrus 2/n table § Explanations Dedhert.Jr (talk) 03:45, 23 May 2026 (UTC)

No. An Egyptian fraction is a sum of distinct unit fractions. 2/n is not a unit fraction. The Rhind papyrus contains expansions as sums of distinct unit fractions for the rationals that in modern notation would be written 2/n, for n ≤ 101; for instance, they expanded 2/37 as 1/24 + 1/111 + 1/296. There are often multiple choices for how to expand a given rational and the expansions used on the Rhind papyrus appear to use different forms for prime and composite numbers. For instance, for a composite n = ab you can expand 2/a and then multiply all the denominators by b, and the Egyptians did this for most but not all of the composite n in this range. See Egyptian fraction#Calculation methods for details. It would be kind of off-topic to expand all this in our article on prime numbers, but it does hint that maybe the Egyptians had some idea about distinguishing prime from composite numbers, and that's all we should need to say. The details are available for those who care to follow the Wikilinks.

As for sourcing, what the source (the MathSciNet review, not the paper reviewed by it) says of relevance is "This procedure explains why for prime numbers in the Rhind Papyrus apart form the first part all the others are multiples of p, p a prime." Which doesn't say much, but I think is enough to justify what we say, that the prime numbers had expansions of a different form (without making any stronger claim that the Egyptians knew this was because they were prime). If you want a more-developed source, Wilbur Knorr (writing about how the expansions in the Rhind papyrus might have been calculated) writes "There are two methods, depending on whether n has proper divisors or not.", p. 136 of Knorr, Wilbur (1982), "Techniques of fractions in ancient Egypt and Greece", Historia Mathematica, 9 (2): 133–171, doi:10.1016/0315-0860(82)90001-5, MR 0662138. —David Eppstein (talk) 06:30, 23 May 2026 (UTC)

I added an efn saying some of this, to avoid putting it into the main text. Also, in the main text, I changed "for prime and composite numbers" to "for fractions with prime and composite denominators". —David Eppstein (talk) 07:03, 23 May 2026 (UTC)

Looks good. Thanks. Stepwise Continuous Dysfunction (talk) 02:14, 24 May 2026 (UTC)

Prime number § Infinitude mentions "Kummer's elegant proof". This is a POV statement (claims of elegance in mathematics are widely but certainly not universally agreed upon), and neither the Ernst Kummer article nor the Euclid's theorem article, which discusses various proofs of infinitude, follow up on it. Stepwise Continuous Dysfunction (talk) 01:50, 23 May 2026 (UTC)

Prime number § Analytic properties says, "Although conjectures have been formulated about the proportions of primes in higher-degree polynomials, they remain unproven". I don't think the article follows up on this later. Should we insert some specifics about these conjectures, perhaps mentioning the Bunyakovsky conjecture or Schinzel's hypothesis H after the Ulam spiral? Stepwise Continuous Dysfunction (talk) 02:12, 23 May 2026 (UTC)

Some replies:

I have updated the year on the largest prime number. I have removed "elegant" for Kummer's proof; unless there's a reason on why many mathematicians regarded Kummer's proof as elegant by showing the description. Dedhert.Jr (talk) 03:07, 23 May 2026 (UTC)

Regarding to extend this, I have found arXiv (see for the journal). Other than Bunyakovsky conjecture and its extended version Schinzel's hypothesis H, Dickson's conjecture and Bateman–Horn conjecture can be added. Dedhert.Jr (talk) 04:41, 4 June 2026 (UTC)

• Is it possible to remove two citations a lead per MOS:LEADCITE? 🍕BP!🍕 (🔔) 15:30, 24 May 2026 (UTC)

  You ask this and simultaneously request citations in the summary material at the end of a section (diff), after those citation requests were already recently rejected for the same reason that they are summaries of later sourced material? Please engage with the article content more substantively rather than merely looking at the positions where footnotes appear and do not appear. We are not required to remove citations from leads of articles or the starts of sections when those citations are appropriate; neither are we required to add citations to leads of articles or the starts of sections when those parts of the article merely summarize later sourced material. It requires human thought about whether the citations are appropriate for the content, not superficial checks for where footnotes appear. So please, think.

  Now in the case of the two footnotes currently in the lead, it appears they are used only to support the "largest known prime number" claims detailed and sourced in a later table. So I am not convinced they are necessary. There is an "as of 2026" in the lead that does not appear in the article body, but I am not a big fan of this sort of phrasing as it needs constant updates, the sources do not actually support that this is true in 2026 (they are dated 2024), and it puts the article into unnecessary maintenance categories.

  I am also not convinced that the largest prime number factoid is necessary in the lead, and I think that if it is to go in the lead it would be better placed in the paragraph on distribution of primes rather than the paragraph about calculation methods. —David Eppstein (talk) 19:44, 24 May 2026 (UTC)

  Now improved by Stepwise Continuous Dysfunction: diff with content that avoids date-specific wording and fits more naturally in the calculation paragraph. —David Eppstein (talk) 20:41, 24 May 2026 (UTC)

I just noticed this line: The AKS primality test has mathematically proven time complexity, but is slower than elliptic curve primality proving in practice. This is probably completely confusing for anyone who isn't already familiar with computational complexity classes. Everyone else will wonder what "mathematically proven time complexity" is supposed to mean. The point here is, I guess, that "polynomial time" does not always equate to "fast" in practice, but we need a better way to say that. Stepwise Continuous Dysfunction (talk) 19:22, 25 May 2026 (UTC)

It's not really about polynomial time versus real world efficiency. They're all polynomial, and some polynomial algorithms being faster than others doesn't raise any interesting philosophical points. The real point is actually that some primality tests base their validity on unproven mathematical hypotheses (such as generalizations of the Riemann hypothesis), some use random numbers and only give you a very small chance of a false answer rather than an answer that is correct with certainty, and some have neither of these two flaws. But you pay for that certainty: the unconditionally-proven non-random algorithms (AKS) are much slower than the unproven or randomized methods. —David Eppstein (talk) 19:28, 25 May 2026 (UTC)

Hmm, OK. I don't think the current phrasing conveys that adequately. Perhaps the article should say something like, "The AKS primality test, though mathematically proven to [...], is slower than elliptic curve primality proving in practice." Stepwise Continuous Dysfunction (talk) 20:15, 26 May 2026 (UTC)

I get the feeling this discussion is happening out of context. Standing alone, that sentence may be confusing, but in context with its preceding sentence stating that "[ECP]'s runtime analysis is based on heuristic arguments rather than rigorous proofs", I think that what this sentence is saying about proven vs unproven behavior is unambiguous. —David Eppstein (talk) 23:41, 26 May 2026 (UTC)

Maybe it's just the "time complexity" part? Even in the context of the surrounding sentences, I still find that a confusing turn of phrase. It's saying that something is proven, but as written I can't tell what. Stepwise Continuous Dysfunction (talk) 04:51, 27 May 2026 (UTC)

It is proven that AKS runs in polynomial time. The polynomial time bound that we believe ECP to take is unproven, resting on heuristic arguments, but faster. There is a problem with your new wording: one can of course analyze ECP completely rigorously too. Your wording implies inaccurately that this is somehow impossible. It is just that the time we think it takes and that it takes in practice is different from the much larger time that can be proved for it. —David Eppstein (talk) 06:57, 27 May 2026 (UTC)

Feel free to change what I wrote, of course; it was just my attempt to squeeze your previous paragraph into a single sentence. It seems to me that the implication you mention was also present in the previous version. I left unchanged the first line: The elliptic curve primality test is the fastest in practice of the guaranteed-correct primality tests, but its runtime analysis is based on heuristic arguments rather than rigorous proofs. To me, this already suggests that there is somehow no way to do a rigorous analysis, rather than a rigorous analysis only being able to give a loose bound. Stepwise Continuous Dysfunction (talk) 15:26, 27 May 2026 (UTC)

Resolved. Thanks. Stepwise Continuous Dysfunction (talk) 02:40, 28 May 2026 (UTC)

Endnote [d] does not contain a reference itself. Can someone with access to Koblitz (1987) check if it verifies the endnote text? Stepwise Continuous Dysfunction (talk) 03:34, 4 June 2026 (UTC)

Well, strictly speaking Koblitz (p.116) describes the Solovay–Strassen test as checking whether $a^{(n-1)/2}$ is congruent to the Jacobi symbol $\left({\tfrac {a}{n}}\right)$ modulo $n$, rather than whether their difference is divisible by $n$, but it's the same thing. —David Eppstein (talk) 05:59, 4 June 2026 (UTC)

Thanks. Stepwise Continuous Dysfunction (talk) 16:39, 5 June 2026 (UTC)