An integer p is prime if whenever p = ab with a,b Î \Bbb Z, either a = ±p or b = ±p .

[For sanity's sake, we will take the position that primes should also be ³ 2 .]

Primality Tests.

How do you decide if a number n is prime?

Brute force: try to divide every number (better: prime) £ n (better £ Ön) into n, to locate a factor.

Fermat's Little Theorem. If p is prime and (a,p) = 1, then a^p-1 º 1 (mod p) .

A composite number n for which a^n-1 º 1 (mod n) is called a pseudoprime to the base a. A composite number which is a pseudoprime to every base a satisfying (a,n) = 1 is called a Carmichael number.

f(n) = number of integers a between 1 and n with (a,n) = 1; if n = p₁^a₁¼p_k^a_k is the prime factorization of n, then f(n) = p₁^a₁-1(p₁-1)¼p_k^a_k-1(p_k-1)

Euler's Theorem.If (a,n) = 1, then a^f(n)(mod n) .

Wilson's Theorem. p is prime Û (p-1)! º -1 (mod p)

Fermat Þ if (a,n) = 1 and a^n-1\not º 1 (mod n) then n is not prime.

If p is prime and a² º 1 (mod p), then a º ±1 (mod p)

(Miller-Rabin Test.) Given n, set n-1 = 2^k d with d odd. Then if n is prime and (a,n) = 1, either a^d º 1 (mod n) or a^{2i d} º -1 (mod n) for some i < k.

If n is not prime, but the above still holds for some a, then n is called a strong pseudoprime to the base a.

Compositeness test: If a^d\not º ±1 (mod n), compute a^{2i d} (mod n) for i = 1,2,¼ . If this sequence hits 1 before hitting -1, or is not 1 for i = k, then n is not prime.

Fact: If n is composite, then it is a strong pseudoprime for at most 1/4 th of the a's between 1 and n.

Finding Factors.

(Pollard Rho Test.) Idea: if p is a factor of N, then for any two randomly chosen numbers a abd b, p is more likely to divide b-a than N is.

Procedure: given N, use Miller-Rabin to make sure it is composite! Then pick a fairly random starting value a₁ = a, and a fairly random polynomial with integer coefficients f(x) (such as f(x) = x²+b), then compute a₂ = f(a₁), ¼, a_n = f(a_n-1), ¼ . Finally, compute (a_2n-a_n, N) for each n. If this is > 1 and < N, stop: you have found a proper factor of N. If it gives you N, stop: the test has failed. You should restart with a different a and/or f.

Basic idea: this will typically find a factor on a timescale on the order of Öp £ N^1/4, where p is the smallest (but unknown!) prime factor of N.

Periods of repeating fractions.

For integers n with (10,n) = 1, the fractions a/n have a repeating decimal expansion. E.g, 2/3 = .6666¼, 1/7 = .142857142857¼, etc.

Determining the length of the period (repeating part) can be done via FLT: 1/7 = .142857142857¼ means 1/7 = 142857/10⁶+142857/10¹²+¼ = 142857/(10⁶-1), i.e 7|10⁶-1, and 6 is the smallest power for which this is true.

In general (if (a,n) = 1), we define \roman ord_n(a) = k = the smallest positive number with a^k º 1 (mod n). Equivalently, it is the largest number satisfying a^r º 1 (mod n) Þ \roman ord_n(a)|r . (Therefore, \roman ord_n(a)|f(n), by Euler's Theorem.)

Generally, then, the period of 1/n = \roman ord_n(10), when (10,n) = 1. When (10,n) > 1, we can write n = 2^r 5^s b = ab with (10,b) = 1, and then write

[1/n] = [1/ab] = [A/a] +[B/b] for some integers A,B .

A/a will have a terminating decimal expansion, so 1/n will have some garbage at the beginning , and then repeat with period equal to the period of b.

Gauss conjectured that there are infinitely many primes p whose period is p-1; this is still unproved.

Primality tests for special cases.

(Lucas' Theorem.) If for, each prime p with p|n-1, there is an a with a^n-1 º 1 (mod n) but a^(n-1)/p\not º 1 (mod n), then n is prime.

Application: look at N = 2^k+1. This could be prime only if k = 2ⁿ; otherwise k = 2ⁿd, d odd, and then 2²ⁿ+1|(2²ⁿ)^d+1 = N. The numbers F_n = 2²ⁿ+1 are called Fermat numbers; the ones which are prime are called Fermat primes. The only known Fermat primes correspond to n = 0,1,2,3,4; Euler showed that 641|F₅, and F_n is known to be composite for n = 5,¼,28. By Lucas' Thm, F_n is prime Û there is an a with

a^F_n-1 º 1 (mod F_n), but a^(F_n-1)/2\not º 1 (mod F_n) (which really together means a^(F_n-1)/2 º -1 (mod F_n)

Pepin showed that it if some a will work, then a = 3 will work!

Fermat primes are important in Euclidean geometry; Gauss showed that a regular N-sided polygon can be constructed with compass and straight-edge Û N is a power of 2 times a product of distinct Fermat primes.

Primitive roots.

A number a is called a primitive root of 1 mod n if \roman ord_n(a) = f(n) (the largest it could be).

Strong converse to Lucas' Thm: If n is prime, then there is a primitive root of 1 mod n (i.e., there is one a that will work for every prime p in Lucas' Thm).

The proof uses the important

(Lagrange's Theorem.) If p is a prime, and f(x) = a_n xⁿ+¼a₁ x+a₀ is a polynomial with integer coefficients, a_n\not º 0 (mod p), then the equation

f(x) º 0 (mod p)

has at most n solutions.

This implies that if p is prime and d|p-1, then the equation x^d º 1 (mod p) has exactly d solutions.

Lemma: If \roman ord_n(a) = m, then \roman ord_n(a^k) = m/(m,k)

Corollary: If p is prime, then there are exactly f(p-1) (incongruent mod p) primitive roots of 1 mod p: find one, a, then the rest are a^k for 1 £ k £ p and (k,p-1) = 1.

Fact: There is a primitive root mod n only for n = 2,3,p^k,2p^k for p a prime.

Artin has conjectured that if a is not a square or -1, then a is a primitive root of 1 for infinitely many primes p. (This is a generalization of Gauss' conjecture above.)

n^{\roman th} roots modulo a prime:.

If p is prime and (a,p) = 1, then (setting r = (n,p-1) the equation xⁿ º a (mod p) has

r solutions if a^(p-1)/r º 1 (mod p)

no solution if a^(p-1)/r\not º 1 (mod p)

This result does not really require p to be prime, only that there be a primitive root mod p. The exact statement is:

If there is primitive root of 1 mod N and (a,N) = 1, then (setting r = (n,f(N)) the equation xⁿ º a (mod N) has

r solutions if a^f(N)/r º 1 (mod N)

no solution if a^f(N)/r\not º 1 (mod N)

Some consequences:

(Euler's Criterion.) The equation x² º a (mod p) has a solution (p = odd prime) Û a^(p-1)/2 º 1 (mod p) ; it then has two solutions (x and -x).

The equation x² º -1 (mod p) has a solution Û (-1)^(p-1)/2 º 1 (mod p) Û p = 2 or p º 1 (mod 4)

For f(x) = a polynomial with integer coefficients, let S(n) = the number of (incongruent, mod n) solutions to the congruence equation f(x) º 0 (mod n). Then:

If (M,N) = 1, then S(MN) = S(M)×S(N). So: to decide if a congruence equation has a solution (and how many), it suffices to decide this for the prime power factors of the modulus.

Sums of squares.

If n = a²+b², then n º 0,1, or 2 (mod 4). Since the product of the sum of two squares

(a²+b²)(c²+d²) = (ac+bd)²+(ad-bc)² = (ad+bc)²+(ac-bd)²

is the sum of two squares, and

2n = (a²+b²) Þ n = ([(a-b)/2])²+([(a+b)/2])² and m = (a²+b²) Þ 2m = (a-b)²+(a+b)²

it suffices to focus on odd numbers, and (more or less) odd primes.

If p º 1 (mod 4) is prime, then p is the sum of two squares.

If p º 3 (mod 4) is prime and p|a²+b², then p|a and p|b.

Together, these imply that a positive integer n can be expressed as the sum of two squares Û in the prime factorization of n, every prime congruent to 3 mod 4 appears with even (possibly 0) exponent.

If n can be expressed as a sum of two squares in two different ways, n = a²+b² = c²+d², then n = (x²+y²)(z²+w²) is the product of two sums of squares, with x,y,z,w ³ 1 .