Number theory is the theory of the integers. Throughout this page, all numbers are integers, unless stated otherwise.
Integers can be positive, negative or 0.
Mostly, results are presented without proof. You can find the proof in any book on number theory.
You learned how to divide integers, getting a quotient and a remainder. That idea extends to all integers, as long as the number you are dividing by is positive.
Theorem. ("Division algorithm") Let x and y be any two integers where y > 0.
There exist unique integers q and r so that
We say that q is the quotient and r is the remainder when you divide x by y.
Example. If you divide 25 by 3, the quotient is 8 and the remainder is 1. Notice that (8)(3) + 1 = 25.
Example. If you divide −25 by 3, the quotient is −9 and the remainder is 2. Notice that (−9)(3) + 2 = −25.
Expression x mod y is the remainder when you divide x by y.
We write y | x to indicate that y divides x; that is, x mod y = 0.
Example. 5 | 30 is true.
Example. 2 | 42 is true.
Example. 5 | 42 is false.
A factor, or divisor, of x is a number y so that y | x.
Example. 7 is a divisor of 42.
Let x and y be two nonnegative integers, not both 0. Then gcd(x, y), the greatest common divisor of x and y, is the largest integer d such that d | x and d | y.
We say that x and y are relatively prime if gcd(x, y) = 1.
Greatest common divisors are easy to compute using Euclid's algorithm.
| gcd(0, x) | = | x |
| gcd(x, y) | = | gcd(y mod x, x) |
The time needed to compute gcd(x, y) is O(log(x + y)).
Definition. x ≡ y (mod m) (x is congruent to y mod m) is true if x mod m = y mod m.
Equivalently, x ≡ y (mod m) is true if m | x−y.
Example. 25 ≡ 1 (mod 3).
Notice that
In some ways, congruences work like ordinary equations. For example, you can add the same integer to each side of a true congruence and you get another true congruence.
Theorem.
If x ≡ y (mod m) then, for all a, a + x ≡ a + y (mod m).
If x ≡ y (mod m) then, for all a, x − a ≡ y − a (mod m).
If x ≡ y (mod m) then, for all a, ax ≡ ay (mod m).
Example. 25 ≡ 1 (mod 3). So 25 + 1 ≡ 1 + 1 (mod 3).
Example. 25 ≡ 1 (mod 3). So 25 − 2 ≡ 1 − 2 (mod 3). That is, 23 ≡ −1 (mod 3).
Be careful. Dividing each side of a true congruence by the same number does not necessarily yield a true congruence.
You can perform addition, subtraction and multiplication mod m by reducing mod m after every step.
For example, let's compute 34 mod 5.
32 ≡ (3)(3) ≡ 9 ≡ 4 (mod 5) 33 ≡ (3)(32) ≡ (3)(4) ≡ 2 (mod 5) 34 ≡ (3)(33) ≡ (3)(2) ≡ 1 (mod 5)
In fact, you can compute powers much more efficiently than that. Here is an efficient modular power algorithm. Assume that x is not 0.
| x0 mod m | = | 1 |
| x2n mod m | = | (x2 mod m)n mod m |
| xn+1 mod m | = | x(xn mod m) mod m |
That yields a polynomial time algorithm to compute xn mod m.
You should be familiar with the concept of the reciprocal of a number in ordinary (real number) arithmetic. The reciprocal of x is 1/x. The defining property of a reciprocal r of x is:
We can use a similar notion with congruences.
Definition. r is a reciprocal of x (mod m) if rx ≡ 1 (mod m).
Example. 5 is a reciprocal of 4 mod 19 since 20 ≡ 1 (mod 19).
Inverses do not always exist. In fact, x has an inverse (mod m) if and only if x and m are relatively prime.
You can compute the inverse of x mod m efficiently, provided gcd(x, m) = 1, using an extension of Euclid's algorithm.
A number x is prime if x > 1 and the only factors of x are 1 and x.
Example. 7 and 37 are prime numbers.
A number x is composite if x > 1 and x is not prime.
Example. 143 is composite because 143 = (11)(13).
Theorem. Suppose that x > 1. Then there is a way to form x as a product of prime numbers, and those prime numbers are unique up to reordering.
Example. 12 = 2⋅3⋅3. You can reorder the factors, (2, 3, 3), but every product of prime numbers that has result 12 will be some ordering of those factors.
Theorem. Suppose that p is a prime number and x is relatively prime to p. Then
Example. 5 is prime. So 34 ≡ 1 (mod 5). You can check that by noting that 34 = 81, and 81 ≡ 1 (mod 5).
Example. 23 is prime. So 622 ≡ 1 (mod 23).
Fermat's Little Theorem has a surprising consequence. Suppose that 0 < x < y and you compute xy−1 mod y, and that the result is not 1. Then y cannot be prime. (If it were, the result would have to be 1).
That gives us a way to demonstrate that a number y is composite without finding a factor of y.
Example. 25 mod 6 = 32 mod 6 = 2. So 6 must be composite.
Fermat's Little Theorem can be used as the core of an algorithm to test whether a number is prime.
Definition. Zn* = {x | 0 < x < n and gcd(x, n) = 1}
It turns out that, with the exception of some rare numbers called Carmichael numbers, if n is composite then, for at least half of the members y of Zn*, yn−1 is not congruent to 1 mod n.
That leads to the following randomized algorithm to test whether n is prime. Assume that n > 1 and select a positive integer m.
isPrime(n)
for i = 1, ..., m
x = a random number
where 1 < x < n;
if gcd(x, n) ≠ 1 then
return false;
if xn−1 ≠ 1 (mod n) then
return false;
end for
return true;
If isPrime(n) returns false, then it is always correct.
If n is not a Carmichael number and n is composite, the probability that isPrime(n) returns true is no more than 2−m. For example, if you choose m = 20, then the probability that isPrime(n) returns an incorrect answer is less than 1/1,000,000.
It turns out that Carmichael numbers are not really a problem. They all have small factors, and they are easy to recognize by a separate test.
Notice that, if isPrime(n) returns false, it does not necessarily find a factor of n. It does a nonconstructive proof that a factor exists.
For a long time, people had to rely on randomized algorithms to test whether a large number is prime. In 2003 a deterministic polynomial-time algorithm to test primality was discovered. So recognizing prime numbers is in P.
The factoring problem is: given a positive integer n, list the prime factors of n.
Factoring appears to be very expensive. No polynomial time factoring algorithm is known.
The obvious algorithm to factor n searches for factors by dividing n by each candidate factor. That is very slow for large n.
For example, suppose that n is 100 digits long. Then n is roughly 10100. If a factor of n exists, then there must be one that is no larger than the square root of n. But that is about 1050, comparable to the number of protons in the earth.
There are known algorithms that are much better than the obvious algorithm. The Number Field Sieve has factored numbers with 125 digits.
But still, no polynomial time algorithm has been found.
Conjecture. There is no polynomial-time algorithm to factor an integer.
Theorem. Suppose that m1, …, mk are pairwise relatively prime. (That is, each pair of them is relatively prime.) For any integers a1, …, ak, there exists a value x so that
| x ≡ a1 (mod m1) |
| … |
| x ≡ ak (mod mk) |
and any two solutions x1 and x2 satisfy
| x1 ≡ x2 (mod n) |
where n = m1⋅…⋅mk.