Skip to Main Content

From Euclid to Public-Key Codes 2

From Euclid and Euler to Public-Key Codes


Some basic concepts in number theory

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). 

      x             x7   (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: