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
Previous Page Next Page