Editing Jacobi symbol (section)

==Primality testing==

There is another way the Jacobi and Legendre symbols differ. If the [[Euler's criterion]] formula is used modulo a [[composite number]], the result may or may not be the value of the Jacobi symbol, and in fact may not even be −1 or 1. For example,

:<math>\begin{align}
\left(\frac{19}{45}\right) &= 1  &&\text{ and } & 19^\frac{45-1}{2} &\equiv  1\pmod{45}. \\
\left(\frac{ 8}{21}\right) &= -1 &&\text{ but } &  8^\frac{21-1}{2} &\equiv  1\pmod{21}. \\
\left(\frac{ 5}{21}\right) &= 1  &&\text{ but } &  5^\frac{21-1}{2} &\equiv 16\pmod{21}.
\end{align}</math>

So if it is unknown whether a number ''n'' is prime or composite, we can pick a random number ''a'', calculate the Jacobi symbol {{big|(}}{{sfrac|''a''|''n''}}{{big|)}} and compare it with Euler's formula; if they differ modulo ''n'', then ''n'' is composite; if they have the same residue modulo ''n'' for many different values of ''a'', then ''n'' is "[[Probable prime|probably prime]]".

This is the basis for the probabilistic [[Solovay–Strassen primality test]] and refinements such as the [[Baillie–PSW primality test]] and the [[Miller–Rabin primality test]].

As an indirect use, it is possible to use it as an error detection routine during the execution of the [[Lucas–Lehmer primality test]] which, even on modern computer hardware, can take weeks to complete when processing [[Mersenne number]]s over <math>\begin{align}2^{136,279,841} - 1\end{align}</math> (the largest known Mersenne prime as of October 2024). In nominal cases, the Jacobi symbol:

<math>\begin{align}\left(\frac{s_i - 2}{M_p}\right) &= -1 & i \ne 0\end{align}</math>

This also holds for the final residue <math>\begin{align}s_{p-2}\end{align}</math> and hence can be used as a verification of probable validity. However, if an error occurs in the hardware, there is a 50% chance that the result will become 0 or 1 instead, and won't change with subsequent terms of <math>\begin{align}s\end{align}</math> (unless another error occurs and changes it back to −1).