Frequently used Theorems and Conjectures Fermat’s Little Theorem Let p be a prime number. Given any positive integer a co-prime with p, then ap−1 ≡ 1 (mod p). The Prime Number Theorem As x → ∞, π(x) = (1 + o(1))Li(x), with Li(x) = x log x + x log2 x + 2! x log3 x + . . . + (r − 1)! x logr x + O x logr+1 x , where r is any given fixed integer. The Chinese Remainder Theorem Let m1, m2, . . . , mr be co-prime integers, and let a1, a2, . . . , ar be arbi- trary integers. Then the system of congruences ⎧ ⎪ ⎪ ⎪ ⎪ n ≡ a1 (mod m1) n ≡ a2 (mod m2) . . n ≡ ar (mod mr) has a solution given by n0 = r i=1 m mi biai, where m = m1m2 . . . mr and where each bi is the solution of the congru- ence (m/mi)bi ≡ 1 (mod mi). xvii

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.