HEJ, HU ISSN 1418-7108
Manuscript no.: ANM-000926-A
 Articles Frontpage [*] [*]

Exact proof of the prime property

With the methods discussed above we can prove very fast - in most of the cases -, that a number is composite, but usually we are not able to prove exactly the prime property (even using our best tool, the Miller-Rabin test). To this we have before this section only the basic algorithm, which is useless for larger numbers. Fortunately, we have some other methods which are relatively easy to programize and are efficient. We call a number $g$ primitive root (mod $p$), if $g^{p-1}$ mod $p =1$ and $g^{k}$ mod $p \ne 1$ for $1 \le k < p-1$. If there exists a primitive root (mod $p$), then $p$ is a prime number, since in this case the numbers $g^{k}$ mod $p$ for $1 \le k \le p-1$ are all different and produce the numbers $1, 2, \dots, n-1$ in some order of succession, i.e. $p$ does not have a non-trivial divisor. The number of the primitive roots (mod $p$) is $\phi(p-1)$, so it is relatively easy to find such a number. For example $2$ is a primitive root modulo $11$. 

  > seq(2^i mod 11,i=1..10);

\begin{displaymath} 2, \,4, \,8, \,5, \,10, \,9, \,7, \,3, \,6, \,1 \end{displaymath}

After finding a number $x$ for which $x^{n-1}$ mod $n =1$, we know already, that the order of $x$ is a divisor of $n-1$. If the order is exactly $n-1$, then $n$ is prime. So we have to check the exponents, which are the (prime) divisors of $n-1$, namely the exponents $(n-1)/p$. Thus, by the check of the following two conditions we have a very nice method to prove exactly the prime property: a) $x^{n-1}$ mod $n =1$, b) $x^{(n-1)/p}$ mod $n \ne 1$, for all prime divisors $p$ of $n-1$. It is known moreover, that the $x$ bases here are allowed to be different, the prime property is still satisfied (J. BRILLHART, D. H. LEHMER and J. L. SELFRIDGE, 1975), details in [1]. Thus to prove the prime property of $n$, we need the complete factorization of $n-1$. However in many cases we are not able to factorize $n-1$, if $n$ is very large. That is, why perfected methods were worked out, using only the partial factorization of $n-1$ or that of $n+1$. In the first case let us write $n$ in the form $n= d_1 \cdot d_2 + 1$, where $0 < d_2 \le d_1+1$. If for all prime divisor $p$ of $d_1$ there exists an $x$, for which $x^{n-1}$ mod $n =$ gcd $(x^{(n-1)/p}-1,n)=1$, then $n$ is prime (H. C. POCKLINGTON, 1914). We use these two methods in the following subsection to prove the prime property of a large number. Similarly as by the factorization, there are exact prime tests using elliptic curves (details in [1]). Moreover, very effective methods are known to prove the prime properties of numbers in special forms, e.g. for Fermat numbers and Mersenne numbers. These methods start so, that we know the factorization of $n-1$ or $n+1$, but they use further special improvements. The following test for Mersenne numbers was worked out by É. LUCAS and D. H. LEHMER (proof in [8]). Let $p$ be an odd prime, and let us define the sequence $\{L_i\}$ in the following manner: $L_0 = 4$, $L_{i+1} = (L_i^2 - 2)$ mod $(2^p - 1)$. Then $2^p - 1$ is prime if and only if $L_{p-2}=0$. Due to this method, we are able to prove the prime property of very large Mersenne numbers. Here we check the $13$th Mersenne number. 

  > L:=4: l:=4: m:=13:
  > for i from 1 to m-2 do
  >   L:=(L*L - 2) mod (2^m-1): l:=l,L
  > od: l;

\begin{displaymath} 4, \,14, \,194, \,4870, \,3953, \,5970, \,1857, \,36, \,1294, \, 3470, \,128, \,0 \end{displaymath}

HEJ, HU ISSN 1418-7108
Manuscript no.: ANM-000926-A
 Articles Frontpage [*] [*]