Editing Primality test (section)

== Simple methods ==
The simplest primality test is ''[[trial division]]'':  given an input number, <math>n</math>, check whether it is [[divisibility|divisible]] by any [[prime number]] between 2 and <math>\sqrt n</math> (i.e., whether the division leaves no [[remainder]]). If so, then <math>n</math> is [[Composite number|composite]]. Otherwise, it is prime.<ref name="Riesel2-3">Riesel (1994) pp.2-3</ref> For any divisor <math>p \geq \sqrt n</math>, there must be another divisor <math>n/p \leq \sqrt n</math>, and a prime divisor <math>q</math> of <math>n/p</math>, and therefore looking for prime divisors at most <math>\sqrt n</math> is sufficient.

For example, consider the number 100, whose divisors are these numbers:

:1, 2, 4, 5, 10, 20, 25, 50, 100.

When all possible divisors up to <math>n</math> are tested, some divisors will be discovered ''twice''. To observe this, consider the list of divisor pairs of 100:

:<math>1 \times 100, \; 2 \times 50, \; 4 \times 25, \; 5 \times 20, \; 10 \times 10, \; 20 \times 5, \; 25 \times 4, \; 50 \times 2, \; 100 \times 1</math>.

Products past <math>10 \times 10</math> are the reverse of products that appeared earlier. For example, <math>5 \times 20</math> and <math>20 \times 5</math> are the reverse of each other. Further, that of the two divisors, <math>5 \leq \sqrt{100} = 10</math> and <math>20 \geq \sqrt{100} = 10</math>. This observation generalizes to all <math>n</math>: all divisor pairs of <math>n</math> contain a divisor less than or equal to <math>\sqrt{n}</math>, so the algorithm need only search for divisors less than or equal to <math>\sqrt{n}</math> to guarantee detection of all divisor pairs.<ref name="Riesel2-3"/>

Also, 2 is a prime dividing 100, which immediately proves that 100 is not prime. Every positive integer except 1 is divisible by at least one prime number by the [[Fundamental Theorem of Arithmetic]]. Therefore the algorithm need only search for ''prime'' divisors less than or equal to <math>\sqrt{n}</math>.

For another example, consider how this algorithm determines the primality of 17. One has <math>4 < \sqrt{17} < 5</math>, and the only primes <math>\leq \sqrt{17}</math> are 2 and 3. Neither divides 17, proving that 17 is prime. For a last example, consider 221. One has <math>14 < \sqrt{221} < 15</math>, and the primes <math>\leq \sqrt{221}</math> are 2, 3, 5, 7, 11, and 13. Upon checking each, one discovers that <math>221 / 13 = 17</math>, proving that 221 is not prime.

In cases where it is not feasible to compute the list of primes <math>\leq \sqrt{n}</math>, it is also possible to simply (and slowly) check all numbers between <math>2</math> and <math>\sqrt{n}</math> for divisors. A simple improvement is to test divisibility by 2 and by just the odd numbers between 3 and <math>\sqrt{n}</math>, since divisibility by an even number implies divisibility by 2.

This method can be improved further. Observe that all primes greater than 5 are of the form <math>6k + i</math> for a nonnegative integer <math>k</math> and <math>i \in \{1, 5\}</math>. Indeed, every integer is of the form <math>6k + i</math> for a positive integer <math>k</math> and <math>i \in \{0, 1, 2, 3, 4, 5\}</math>. Since 2 divides <math>6k, 6k + 2</math>, and <math>6k + 4</math>, and 3 divides <math>6k</math> and <math>6k + 3</math>, the only possible remainders mod 6 for a prime greater than 3 are 1 and 5. So, a more efficient primality test for <math>n</math> is to test whether <math>n</math> is divisible by 2 or 3, then to check through all numbers of the form <math>6k + 1</math> and <math>6k + 5</math> which are <math>\leq \sqrt{n}</math>. This is almost three times as fast as testing all numbers up to <math>\sqrt{n}</math>.

Generalizing further, all primes greater than <math>c\#</math> ([[Primorial#Definition for natural numbers|c primorial]]) are of the form <math>c\# \cdot k + i</math> for <math>i, k</math> positive integers, <math>0 \leq i < c\#</math>, and <math>i</math> [[coprime]] to <math>c\#</math>. For example, consider <math>6\# = 2 \cdot 3 \cdot 5 = 30</math>. All integers are of the form <math>30k + i</math> for <math>i, k</math> integers with <math>0 \leq i < 30</math>. Now, 2 divides <math>0, 2, 4, \dots, 28</math>, 3 divides <math>0, 3, 6, \dots, 27</math>, and 5 divides <math>0, 5, 10, \dots, 25</math>. Thus all prime numbers greater than 30 are of the form <math>30k + i</math> for <math>i \in \{1, 7, 11, 13, 17, 19, 23, 29\}</math>. Of course, not all numbers of the form <math>c\# \cdot k + i</math> with <math>i</math> coprime to <math>c\#</math> are prime. For example, <math>19 \cdot 23 = 437 = 210 \cdot 2 + 17 = 2 \cdot 7\# + 17</math> is not prime, even though 17 is coprime to <math>7\# = 2 \cdot 3 \cdot 5 \cdot 7</math>.

As <math>c</math> grows, the fraction of coprime remainders to remainders decreases, and so the time to test <math>n</math> decreases (though it still necessary to check for divisibility by all primes that are less than <math>c</math>). Observations analogous to the preceding can be applied [[recursion|recursively]], giving the [[Sieve of Eratosthenes]].

One way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, such as all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes or by an algorithm that tests each incremental <math>m</math> against all known primes <math>\leq \sqrt m</math>). Then, before testing <math>n</math> for primality with a large-scale method, <math>n</math> can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped.

A simple but inefficient primality test uses [[Wilson's theorem]], which states that <math>p</math> is prime if and only if:

:<math>(p - 1)! \equiv -1 \pmod{p}</math>

Although this method requires about <math>p</math> modular multiplications,<ref>{{Cite book |date=2021-09-05 |chapter=Primality Tests |title=Elementary Number Theory |first1=Mike |last1=Barrus |first2=W. Edwin |last2=Clark |chapter-url=https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Barrus_and_Clark)/01:_Chapters/1.25:_Primality_Tests |url=https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Barrus_and_Clark) |access-date=2025-03-14 |publisher=Mathematics LibreTexts |language=en}}</ref> rendering it impractical, theorems about primes and modular residues form the basis of many more practical methods.