Prove that there are infinitely many primes. (Hint: how that none of the primes p1, p2, ..., pk divide (p1 p2 ··· pk) + 1.)
The hint tells us everything.
If we have finite prime numbers{p1,p2,p3,...,pk}. We show that A = (p1 p2 ··· pk) + 1 is neither a composite number nor prime number.
- Becauce we have finite prime numbers, then A is not prime.
- On the other hand, A mod p1 = 1;A mod p2 = 1;...;A mod pk = 1. So, A is not composite.
As a result, we have infinite many primes.
Prove that if a | b and b | c, then a | c.
a | b means b = k1a
b | c means c = k2b
So, c = k2b = k1k2a which means a | c
If p[i] dismatch T[j],next time trace back to j+1;That is,compare from p[0] and T[j+1].
Prove that if p is prime and 0 < k < p, then gcd(k, p) = 1.
Obvious.
Prove Corollary 31.5.
ab = kn
b = n(k/a), because gcd(n,a) = 1,k/a is an integer
b = k'n, k' = k/a
so n | b
Prove that if p is prime and 0 < k < p, then  p | (p k). Conclude that for all integers a, b, and primes p, (a+b)p ≡ ap +bp (modp).
The first is pretty obvious using polynomial expansion.
If solve the first, the second is easy too.
(a+b)^p mod p
= a^p + b^p + a^1*b^(p-1)(p 1) + ... mod p
= a^p + b^p mod p
Prove that if a and b are any integers such that a | b and b > 0,
then (x mod b) mod a = x mod a for any x.
Prove, under the same assumptions, that
x ≡ y mod b) implies x ≡ y (mod a)
for any integers x and y.
Assume x = ra + b , b = ka
x mod a = b
x mod b = (ra+b)%(ka) = (r%k)a+b
x mod b mod a = (r%k)a % a + b % a = b
For any integer k > 0, we say that an integer n is a kth power if there exists an integer a such that ak = n.We say that n > 1 is a nontrivial power if it is a kth power for some integer k > 1. Show how to determine if a given β-bit integer n is a nontrivial power in time polynomial in β.
I only have naive idea : iterate every number.
Prove equations (31.6)–(31.10).
straightforward
Show that the gcd operator is associative. That is, prove that for all integers a, b, and c, gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).
Assume a = p1^i1 * p2^i2 * ... * pk^ik
Assume b = p1^j1 * p2^j2 * ... * pk^jk
Assume c = p1^l1 * p2^l2 * ... * pk^lk
gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = p1^min(i1,j2,k1) * p2^min(i2,j2,k2) * ... *pk^min(ik,jk,lk)
Prove Theorem 31.8.
If the way is not unique, then some combinations of primes are equal to others. However, gcd(prime1, prime2) = 1, so it is not possible.
Give efficient algorithms for the operations of dividing a β-bit integer by a shorter integer and of taking the remainder of a β-bit integer when divided by a shorter integer. Your algorithms should run in time O(β2).
UNSOLVED
Give an efficient algorithm to convert a given β-bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most β takes time M(β), then binary-to-decimal conversion can be performed in time Θ(M(β) lg β).  (Hint: Use a divide-and-conquer approach, obtaining the top and bottom halves of the result with separate recursions.)
Follow @louis1992 on github to help finish this task