Primality Testing // from CLRS

Prime Number Theorem: // page 965

pi(N) ~= N / ln(N)

According to Terence Tao, the proof is something like the below:

      Listening to the "music" of the primes. We start with a "sound wave" that is "noisy" at the prime numbers and silent at other numbers; this is the von Mangoldt function. Then we analyze its notes or frequencies by subjecting it to a process akin to Fourier transform; this is the Mellin transform. Then we prove, and this is the hard part, that certain "notes" cannot occur in this music. This exclusion of certain notes leads to the statement of the prime number theorem.

---------------------------------------------------------------------------------------------

Chinese Remainder Theorem: // page 950

n = PRODUCT( ni ) { ni is pairwise relatively prime }
a <---> (a1 ... ak) { ai = a mod ni } have bijection.

PF:
a --> (a1 ... ak), QED
(a1 ... ak) --> a, a = SUM( ai * mi * ( mi^(-1) mode ni ) ), mi = PRODUCT( nj except ni ), QED

Practice: X = 2 (mod 3), X = 3 (mod 5), X = 2 (mod 7), Find X


---------------------------------------------------------------------------------------------

Primality Testing 1: // page 956

if n is prime, only x = 1 or -1, x^2 = 1 (mod n)

PF:

if n = 2, 0^2 = 0, 1^2 = 1, 2^2 = 1, QED

if n > 2, p | (x-1)(x+1). p | (x-1) or p | (x+1), but not both.(Use Contradiction) If p | (x-1), x = 1(mod n). if p | (x+1), x = -1(mod n), QED

Corollary: if exist x != 1 & x != -1, x^2 = 1 (mod n), n is composite.(contrapositive)

---------------------------------------------------------------------------------------------

Primality Testing 2: // page 967

if n is prime, for all x != kn, x^(n-1) = 1 (mod n)

PF:

define Ai = x * i (mod n); P = PRODUCT( Ai ) { i = 1 ~ (n - 1) } ; Q = PRODUCT( i ){ i = 1 ~ (n-1) }

All Ai are distinct. ( Use Contradiction, if Ai = Aj (mod n), then x * (i - j) = 0 (mod n), then n | x * (i - j), then n | (i - j), but i - j < n, Contradict. )

Thus, P = Q (mod n)

x^(n-1) * Q = Q (mod n)

Q( x^(n-1) - 1 ) = 0 (mod n)

x^(n-1) = 1 (mod n)

Corollary: if exist x^(n-1) != 1 (mod n), n is composite.(contrapositive)

But there's something called Carmichael Number, that looks just like Prime under this test.

---------------------------------------------------------------------------------------------

Primality Testing 3: // page 968

For PT2, We use a^(n-1) = 1 (mod n). But here let a^(n-1) = a^(u*2^t), check a^u, (a^u)^2, ((a^u)^2)^2 ... 

So we won't be fooled by Carmichael Number.

And we can prove that if n is composite, then there are (n-1)/2 number a, that can discover it is composite.

http://ideone.com/FzgRvN