Number Theory
Draft for Information Only Content
Primality
PrimalityPrime 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 FactorizationIn 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 ap1≡ 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≤p1<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 ap11 then pe+n is the highest power of p divides ape(p1)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)papbp 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 p1 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 ap1 will be the smallest power which have remainder 1 when divided by p. That is the orders of a are λ=p1 (mod p). Since there are only maximum p1 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 p1 and . Consider the case λ=p1. If ai≡a0≡1(mod p), then ai+1=a1(mod p). Since when i is 0<i<p1, the remainder will appear twice and contradicts to the result of distinct positive remainders, therefore i should equal or greater than p1 and ap1 will be the smallest power of a with remainder 1 when divided by p, that is ap1≡1(mod p) and ap≡a(mod p). The p1 is also the constant of the arithmetic progression of the exponent, i.e. k=p1. Imply However for some a, the order f is less then p1 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(ap11) (mod p) then ap1 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 p1 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 p1. 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 p1. 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,...,at1} If t<p1, 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,...,kat1}, 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,...,at1} and {k,ka,ka2,...,kat1}. Since the order of "a" modulo "p" is equal to t and t<p1, imply 2t≤p1. If 2t=p1, then t(p1). If 2t<p1 then try another integer f. Similar to k, a new set {f,fa,fa2,...,fat1}, 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,...,at1}, {k,ka,ka2,...,kat1}, and {f,fa,fa2,...,fat1}. Similarly if 3t=p1, then t(p1). If 3t<p1 then try another integer again.
Since p is a prime, and t≤p1, eventulaly t divides p1. Thus for some integer m, p1=tm. Imply ap1=atm, and ap1≡atm(mod p), therefore ap1≡atm≡(at)m≡1(mod p) since at≡1(mod p). If t≠p1, then there always exists some m such that p1=tm. Since t is the least power of a that divided by p with remainder 1. therefore t always divides (p1) and ap11≡at1≡0(mod p), there is a m such that mt=p1. In other words, at≡a2t≡a3t≡...≡amt2t≡amtt≡amt≡1 or in term of p1, ap1mt+t≡ap1mt+2t≡ap1mt+3t≡...≡ap12t≡ap1t≡ap1≡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(ap1mt+t+ap1mt+2t+ap1+mt+3t+...+ap12t+ap1t+ap1)(ap1mt+t+ap1mt+2t+ap1mt+3t+...+ap12t+ap1t+ap1)≡0. Therefore (at1)(ap1mt+t+ap1mt+2t+ap1mt+3t+...+ap12t+ap1t+ap1)≡ap11≡0 As a result, (at1)ap11 also besides tap11. 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 p1, 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 p1 divides t, then jt≡1 (mod p) for j=1,2,3,...,p2,p1. The sum of
these terms is equal to S≡p1≡1 (mod p). Let g be a primitive root
modulo p. If p1 does not divide t, then gt≢1(mod p). Since the set of residue class of g
modulo p of order p1 is {1, 2,...,(p2),(p1)}, the set of residue class
with the multiplication of g to the residue is the same, {g,
g2,...,g(p2),g(p1)}. Therefore, for S≡∑ p1 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 p1. Therefore the distinct power set {g0,g1, g2,...,gp2} is equal to the distinct residue set {1, 2,...,(p2),(p1)}. Every integer g with 1≤g≤p, such that g mod p has order p1 is called a primitive root modulo p. One of the effective method is suggested by Gauss. ©sideway References
ID: 130400010 Last Updated: 2013/4/19 Revision: Ref: 
Home (5) Computer Hardware (149) Software Application (187) Digitization (24) Numeric (19) Programming Web (648) CSS (SC) ASP.NET (SC) Regular Expression (SC) HTML Knowledge Base Common Color (SC) Html 401 Special (SC) OS (389) MS Windows Windows10 (SC) .NET Framework (SC) DeskTop (7) Knowledge Mathematics Formulas (8) Number Theory (206) Algebra (20) Trigonometry (18) Geometry (18) Calculus (67) Complex Analysis (21) Engineering Tables (8) Mechanical Mechanics (1) Rigid Bodies Statics (92) Dynamics (37) Fluid (5) Fluid Kinematics (5) Control Process Control (1) Acoustics (19) FiniteElement (2) Biology (1) Geography (1)  
Latest Updated Links

Copyright © 20002019 Sideway . All rights reserved Disclaimers last modified on 10 Feb 2019