Number theory is the study of the mathematical properties of the integers, or whole numbers---0, 1, 2, 3, ...---and especially that part that concerns divisibility. (A number and its negative have the same divisibility properties, so we will not mention negative numbers explicitly, although we will need them for calculations.)

- One integer
*n*is said to be**divisible**by another integer*m*if*m*divides*n*with no remainder. So 14 is divisible by 7, but 15 is not. - Equivalently, we say that
*n*has*m*as a**factor**. - An integer is a
**prime**if it is different from 1 and if it is divisible only by 1 and by itself. Otherwise it is called**composite**. So 2, 3, 5, 7, 11, 13, 17, 19, ... are primes, whereas 4, 6, 8, 9, 10, 12, 14, 15, 16, ... are composite. - Two integers are said to be
**relatively prime**if they have no common divisor except 1. So 65 and 18 are relatively prime, whereas 66 and 18 have common divisor 6 and are not relatively prime. - Two integers
*m*and*n*are said to be**congruent modulo***N*(*N*also an integer) if their difference is divisible by*N*. We write*m*=*n*(mod*N*).Examples: 15 = 3 (mod 2), since their difference 12 is divisible by 2. They are also congruent mod 3, mod 4, mod 6, and mod 12. Any two odd numbers are congruent mod 2. Any two even numbers are congruent mod 2. 1234 = 4321 (mod 9).

Practically speaking, any integer is congruent mod

*N*to its remainder after division by*N*. For example, any number is congruent mod 11 to one of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, since these are the only possible remainders.For practice, here is a table of seventh powers (mod 11).

xx^{7}(mod 11) 0 0 1 1 2 128 = 7 (mod 11) 3 2187 = 9 (mod 11) 4 16384 = 5 (mod 11) 5 78125 = 3 (mod 11) 6 279936 = 8 (mod 11) 7 823543 = 6 (mod 11) 8 2097152 = 2 (mod 11) 9 4782969 = 4 (mod 11) 10 10000000 = 10 (mod 11)

Back to:

- From Euclid and Euler ... (page 1)
- How to find out if a given number is prime ... (page 2)
- How does a public-key code work? (page 3)
- Mopping up ... (page 4)