Content

Primality

Prime numbers are natural numbers, e.g. 2, 3, 5, 7,..., which can only be divided by 1 and itself. Although the way to recognize the primality of a natural numbe is very simple, there is difficulty of distinguishing prime numbers from composite numbers when natural numbers become very large.

Primality and Factorization

In general, the problem of primality and factorization of a large natural number is the involving of finitely many steps. The simple algorithm for the problem of primality and factorization is the method of trial division. For a given natural number N, a division test can be used to determine whether the natural number N is a prime or a composite number. The division test can be tried in succession of every number n=2,3,4,...,⌊√N⌋ to check whether n divides N or not. Composite number in the list can also be ignored from the division test. If none of the prime number in the list can divide N, then N is a prime. The problem with the trial division is the time consumption on determining whether a large number is a prime or composite.

The Sieve of Eratosthenes (c 3 BC)[1]

Instead of trial division, Eratosthenes making use of multiplication, an easier operation than division to sieve out composite number of the multiples of primes p for all p2≤N in an organized way. The sieving process starts from the smallest prime p=2, all multiples of the prime p, which are bigger than prime p, are crossed out. The process is repeated until p=⌊√N⌋. For example, all composite number small or equal to 100 can be sifted away after sieving with multiples of number 2, 3, 5, and 7. Numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97 are primes. Imply

Fermat's Little Theorem[1]

Although the Sieve of Eratosthenes has much improved the method of trial division, the Sieve of Eratosthenes is still a time consuming process. Methods are developed to reduce the time required for test primality. One type of classical methods is making use of theorems on congruences. One important theorem on primality testing is the Fermat's Little Theorem. The Fermat's Little Theorem state that if p is a prime and a is any positive integer then ap≡ a(mod p). And if integer a is not divisible by a, then ap-1≡ 1(mod p). The proof of Fermat's Little Theorem is first published by Euler in 1736. Let a be equal to 1, Euler's first proof  proves the stated lemma is true at a=2 by the binomial expansion of 2 in the form of 1+1. Imply

Euler's second proof proves the Fermat's Little Theorem is true at a=2 by the binomial expansion of 2 in the form of 1+1 directly and give an alternate approach to prove the stated lemma is true. Imply

Euler's third proof proves both the Fermat's Little Theorem and the stated Lemma is also true at a=3 by the binomial expansion of 3 in the form of 1+2 directly in a similar way. Imply

Similar to the proof on case a=3, Euler proves both the Fermat's Little Theorem and the stated Lemma is also true at a general case using the binomial expansion of a in the form of 1+a directly by general induction step. Imply

The proof is making use of the property of the binomial coefficient which based on the fact that if p is a prime then the binomial coefficient of term k such that 0<1≤k≤p-1<p should always be divided by p since the binomial coefficient is an integer and p is not divisible by any factors of the denominator of the binomial coefficient. prime p is the common factor of the binomial coefficient. The Fermat's Little Theorem can be used to identify one of the crucial property of a prime number. However, the Fermat's Little Theorem is also valid for some composite number, called Fermat pseudoprime. This is because there are two more variables in each binomial term besides the binomial coefficient. Therefore the Fermat's Little Theorem can only be true for sieving out composite numbers, more or repeated tests is needed to confirm the tested number is a prime. Besides for a composite number of a power of p, if p∤a and pe is the highest power of p divides ap-1-1 then pe+n is the highest power of p divides ape(p-1)-1. 

Euler in 1736 expand the proof to a general form. If p is a prime and a and b are any integer then all number in the form of (a+b)p-ap-bp is divisible by p. The proof is same as before and the number 1 in 1+a is replaced by b, i.e. a+b. Imply

The Order of "a" Modulo "p" [1]

In 1758, Euler further extend the proof to the division of powers. If p is prime, a is any integer, and gcd(a,p)=1, there exists an infinite geometric progression {1, a, a2, a3,a4,... ,ar, ...} where r is an integer, then there are infinitely many terms which remain a residue 1 when divided by p and the exponents of those terms that divided by p with remainder 1 will form an arithmetic progression.

If aλ is the smallest power of a that have remainder 1 after divided by prime p, then all remainders of the terms in the geometric progression {1, a, a2, a3,a4,... ,aλ-1} up to term aλ is distinct. Since whenever there are two terms in the geometric progression having the same remainder, there must have one more term while i≠j with remainder equal to 1 below ,aλ such that the proposed λ is not the smallest. Imply

In general, there have p-1 positive distinct residues less than p when an integer is divided by p. Therefore, let p is a prime number and a is prime to p, if all the positive numbers less than p are represented by the residues of the powers of a divided by p, then ap-1 will be the smallest power which have remainder 1 when divided by p. That is the orders of a are λ=p-1 (mod p). Since there are only maximum p-1 distinct positive remainders when an integer is divided by p and the remainders of the finite set of the power of a less than aλ are distinct and λ, the maximum number of terms in the finite site of the power of a less than aλ are less or equal to p-1 and . Consider the case λ=p-1. If ai≡a0≡1(mod p), then ai+1=a1(mod p). Since when i is 0<i<p-1, the remainder will appear twice and contradicts to the result of distinct positive remainders, therefore i should equal or greater than p-1 and ap-1 will be the smallest power of a with remainder 1 when divided by p, that is ap-1≡1(mod p) and ap≡a(mod p). The p-1 is also the constant of the arithmetic progression of the exponent, i.e. k=p-1. Imply

However for some a, the order f is less then p-1 such that not all positive numbers less than p are represented by the residues of the powers of a divided by p. In other words, there exists some possible remainders which are not the residue of powers of a when divided by p. From Fermat's Little Theorem, p is prime and p|(ap-1-1) (mod p) then ap-1 always have a remainder 1 when dividing p. And for the smallest power of the order λ which have remainder 1 when dividing p, the set of exponents is an arithmetic progression with a constant of λ. That is {0,λ,2λ,3λ,4λ,...}. Since p-1 must be in the set of the arithmetic progression with a constant λ.Therefore, if p is prime and aλ is the smallest power of a when divided by p with remainder 1, then will the exponent λ will be a divisor of the number p-1. Imply

As a result, for any integer a and a prime p, if a is not a multiple of the prime p, there exists the smallest exponent λ, such that aλ≡1 (mod p). And for any other exponent i, ai≡1 (mod p) is valid if and only if f divides i. and the particular case is f divides p-1. The exponent λ is called the order of "a" modulo "p". The residues of the power of a divided by p are still distinct and only some of the residues less than p when a is divided by p, are not the residues of the power of a divided by p.

Let t be the order of "a" modulo "p", the set of the power of a divided by p with distinct residue is {1,a,a2,...,at-1} If t<p-1, then there exists a positive integer k of 1<k<p is not the residue of a power of a. A new set with the multiplication of k can be constructed {k,ka,ka2,...,kat-1}, which has distinct residues when divided by p and no one is the residue of the power of a(mod p). The new set has distinct residues because whenever there are two terms in the geometric progression having the same remainder, they will cause contradiction to the set of the power of a with the order of "a" modulo "p" equals to t. There is also no duplicate residues in the two sets of powers of a  Imply

There are totally 2t distinct residues (mod p) in sets {1,a,a2,...,at-1} and {k,ka,ka2,...,kat-1}. Since the order of "a" modulo "p" is equal to t and t<p-1, imply 2t≤p-1. If 2t=p-1, then t|(p-1). If 2t<p-1 then try another integer f. Similar to k, a new set {f,fa,fa2,...,fat-1}, which has distinct residues when divided by p and no one is the residue of ai or kai  (mod p). Then there are totally 3t distinct residues (mod p) in sets {1,a,a2,...,at-1}, {k,ka,ka2,...,kat-1}, and {f,fa,fa2,...,fat-1}. Similarly if 3t=p-1, then t|(p-1). If 3t<p-1 then try another integer again.

Since p is a prime, and t≤p-1, eventulaly t divides p-1. Thus for some integer m, p-1=tm. Imply ap-1=atm, and ap-1≡atm(mod p), therefore ap-1≡atm≡(at)m≡1(mod p) since at≡1(mod p). If t≠p-1, then there always exists some m such that p-1=tm.

Since t is the least power of a that divided by p with remainder 1. therefore t always divides (p-1) and ap-1-1≡at-1≡0(mod p), there is a m such that mt=p-1. In other words, at≡a2t≡a3t≡...≡amt-2t≡amt-t≡amt≡1 or in term of p-1,  ap-1-mt+t≡ap-1-mt+2t≡ap-1-mt+3t≡...≡ap-1-2t≡ap-1-t≡ap-1≡1. Since the difference between two terms is at, the difference of the multiplication of the sum of all terms by at and the sum of all terms is equal to zero, therefore at(ap-1-mt+t+ap-1-mt+2t+ap-1+mt+3t+...+ap-1-2t+ap-1-t+ap-1)-(ap-1-mt+t+ap-1-mt+2t+ap-1-mt+3t+...+ap-1-2t+ap-1-t+ap-1)≡0. Therefore (at-1)(ap-1-mt+t+ap-1-mt+2t+ap-1-mt+3t+...+ap-1-2t+ap-1-t+ap-1)≡ap-1-1≡0

As a result,   (at-1)|ap-1-1 also besides  t|ap-1-1.

Primitive Roots Modulo a prime p[1]

Similar to changing the value of integer k for the order of a modulo p equals to t and less then p-1, the integer a can also be altered such that the value of the order of a modulo p is changed accordingly. Let p>2 and t≥1. If p-1 divides t, then jt≡1 (mod p) for j=1,2,3,...,p-2,p-1. The sum of these terms is equal to S≡p-1≡-1 (mod p). Let g be a primitive root modulo p. If p-1 does not divide t,  then gt≢1(mod p). Since the set of residue class of g modulo p of order p-1 is {1, 2,...,(p-2),(p-1)},  the set of residue class with the multiplication of g to the residue is the same,  {g, g2,...,g(p-2),g(p-1)}. Therefore, for S≡∑ p-1
j=1 jt (mod p), imply ∑ p-1
j=1 (gj)t≡gt∑ p-1
j=1 jt≡gtS (mod p). Since gt≢1(mod p), p does not divide gt-1, imply S≡0 (mod p). Imply

For every prime p, there always exists at least one integer g, not a multiple of the prime p, such that the order of g modulo p is equal to p-1. Therefore the distinct power set {g0,g1, g2,...,gp-2} is equal to the distinct residue set {1, 2,...,(p-2),(p-1)}. Every integer g with 1≤g≤p, such that g mod p has order p-1 is called a primitive root modulo p. One of the effective method is suggested by Gauss.