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
