Some useful elementary number theory
Recommended reading
- Elementary Number Theory by Gareth A. Jones and J. Mary Jones
- The Higher Arithmetic: An Introduction to the Theory of Numbers by H. Davenport
- Concrete Mathematics: a foundation for computer science by Ronald L. Graham, Donald E. Knuth and Oren Patashnik
Join Amazon Student FREE Two-Day Shipping for College Students
Affiliate disclosure: we get a small commission for purchases made through the above links
We use most of these principles of number theory on our page on the mathematics behind the RSA algorithm.
- The integer n divides the integer a if and only if there exists an integer d such that a = nd. We say that a is divisible by n, and that n is a divisor or factor of a, and that a is a multiple of n. The notation n|a means that n divides a, and n|a - b means that n divides (a - b). For any integer a we have 1|a, a|a and a|0.
- If mn|a then m|a and n|a for any integers m, n. This follows since mn|a ⇒ a = mnd for some d, hence m|a and n|a.
- A prime number is defined as an integer, greater than one, which only has positive integer divisors of the number one and itself. For example, both 7 and 11 are prime but 4 and 9 are not. An integer > 1 which is not prime is called a composite number. The number one is neither prime nor composite. The first thousand and ten thousand primes are listed here.
- The Fundamental Theorem of Arithmetic: Every integer n > 1 can be represented in exactly one way as a product of primes except for the order of the factors. That is, we can write n uniquely in the form n = p_{1}^{k1}p_{2}^{k2}...p_{r}^{kr} for primes p_{1} < p_{2} < ... < p_{r} and positive integers k_{1}, ..., k_{r}. For example, 360 = 2^{3}3^{2}5^{1} and 1323 = 3^{3}7^{2}.
- Two numbers a and b which have no common factors other than one are said to be coprime or relatively prime. For example, 4 and 9 are coprime but 15 and 25 are not.
- The greatest common divisor of two integers a and b is the largest integer that divides both numbers and is denoted by ‘gcd(a, b)’. For example, gcd(25, 15) = 5 and gcd(4, 9) = 1. Some texts use the equivalent term highest common factor denoted by ‘hcf(a, b)’. Other texts, where there is no chance of confusion, use the shorter notation ‘(a, b)’, e.g. (25, 15) = 5.
- a and b are coprime if and only if gcd(a, b) = 1.
- ‘mod’ as a binary operation: The notation ‘a = b mod n’ defines a binary operation where a is equal to the remainder on dividing b by n, 0 ≤ a < n.
- ‘mod’ as a congruence relation: The notation ‘a ≡ b (mod n)’ means
a and b have the same remainder when divided by n, or, equivalently,
n|a - b, or
a - b = nk for some integer k.
We say that a is congruent to b modulo n, where n is the modulus
of the congruence.
The two ways of using ‘mod’ are related:
a ≡ b (mod n) ⇔ a mod n = b mod n
[see note 1]. - Every integer is congruent modulo n to exactly one of the integers in the set of least positive residues {0, 1, 2, ..., n-1}. This set of n integers is denoted Z_{n} [see note 2].
- Properties of congruence: for a fixed positive integer n and any
integers a, b, c, d.
- Reflexive property: a ≡ a (mod n).
- Symmetric property: If a ≡ b (mod n) then b ≡ a (mod n).
- Transitive property: If a ≡ b (mod n) and b ≡ c (mod n) then a ≡ c (mod n).
- Addition and multiplication rules: If a ≡ b (mod n) and c ≡ d (mod n) then a±c ≡ b±d (mod n) and ac ≡ bd (mod n).
- Cancellation rule: If ac ≡ bc (mod n) and c ≠ 0 then a ≡ b (mod n / gcd(c, n)). If gcd(c, n) = 1 then a ≡ b (mod n) [see note 3].
- Associative and distributive properties: (a + b) + c ≡ a + (b + c) (mod n), (ab)c ≡ a(bc) (mod n), and a(b + c) ≡ ab + ac (mod n).
- If a ≡ b (mod n) then a^{r} ≡ b^{r} (mod n), for any integer r ≥ 1.
- a ≡ 0 (mod n) if and only if n|a.
- If m and n are coprime and a ≡ b (mod m) and a ≡ b (mod n), then a ≡ b (mod mn).
- The Euler totient function (or Euler phi function) of a positive integer n, denoted φ(n), is defined to be the number of positive integers not exceeding n which are relatively prime to n. For example, φ(12) = 4 as the 4 integers {1, 5, 7, 11} are coprime to 12; and φ(7) = 6 as the 6 integers {1, 2, 3, 4, 5, 6} are coprime to 7.
- For any prime p, φ(p) = p - 1, since all numbers less than p are relatively prime to it.
- If m and n are coprime, then φ(m)φ(n) = φ(mn).
- Fermat's Little Theorem: If p is a prime and a is any integer, then a^{p} ≡ a (mod p). If gcd(a, p) = 1, then a^{p-1} ≡ 1 (mod p).
- Euler-Fermat Theorem: If n is a positive integer and a is any integer with gcd(a, n) = 1, then a^{φ(n)} ≡ 1 (mod n).
- The Carmichael function of a positive integer n, denoted λ(n), is defined as the smallest positive integer m such that a^{m} ≡ 1 (mod n) for all integers a relatively prime to n. It can be shown that λ(n) divides φ(n).
- The least common multiple of the non-zero integers a and b, denoted lcm(a, b), is the smallest positive integer that is a multiple of both a and b. For example, lcm(10, 15) = 30. For any pair of integers a and b, lcm(a, b) x gcd(a, b) = |ab|.
- If n is the product of two distinct primes p and q, n = pq, then λ(pq) = lcm(p-1, q-1).
- The modular multiplicative inverse or modular inverse of an integer a modulo n is an integer x such that ax ≡ 1 (mod n). We write x = a^{-1} mod n or x = (1/a) mod n. A modular inverse exists if and only if gcd(a, n) = 1.
Notes
1. Note that ‘a = b mod n’ is satisfied by a unique integer 0 ≤ a < n, but the congruence ‘a ≡ b (mod n)’ is satisfied by any integer of the form b + nk for any integer k. For example, 16 mod 12 = 4, but the congruence a ≡ 16 (mod 12) is satisfied by a = 4, 16, 28, 40, ... and a = -8, -20, -32, ...
2. Strictly speaking, Z_{n} is the set of equivalence classes modulo n. The set Z_{n} always has n members, all incongruent to each other.
3. Be careful when trying to 'divide through' the two sides of a congruence by what seems to be a common factor. It only works in the way you'd expect if the common factor is coprime to the modulus.
For example, suppose we want to solve the linear congruence 9x ≡ 6 (mod 11) for x. The coefficients 9 and 6 have the common factor 3, and 3 is coprime to 11, since gcd(3, 11) = 1, so we can 'divide through' by 3 to get 3x ≡ 2 (mod 11), leaving the modulus 11 unchanged. This has the single solution x ≡ 8 (mod 11) and this is also the solution to the original congruence. To see this note that 3 x 8 = 24 ≡ 2 (mod 11) and 9 x 8 = 72 ≡ 6 (mod 11).
However, if we want to solve 9x ≡ 6 (mod 12), we use the cancellation rule to obtain 3x ≡ 2 (mod 4) (this time gcd(9, 12) = 3 ≠ 1 so we must divide the modulus 12 by 3 as well). This latter congruence is solved by x ≡ 2 (mod 4), and the original congruence modulo 12 is therefore solved by the three solutions x ≡ 2, 6, 10 (mod 12). That is, x = 2 + 4i for i = 0, 1, 2. See that 3 x 2 = 6 ≡ 2 (mod 4), but this time we have three solutions modulo 12; namely, 9 x 2 = 18 ≡ 6 (mod 12), 9 x 6 = 54 ≡ 6 (mod 12), and 9 x 10 = 90 ≡ 6 (mod 12).
Bibliography
- Bornshtein and Semendyayev, Handbook of Mathematics, 5th ed., Springer-Verlag, 2007
- Davenport, H, The Higher Arithmetic: An Introduction to the Theory of Numbers, Cambridge University Press, 1999
- Graham, Knuth, Patashnik, Concrete Mathematics: a foundation for computer science, 2nd ed, Addison-Wesley, 1994
- Jones, Gareth A. and J. Mary Jones, Elementary Number Theory, Springer-Verlag, 1998
- M381 Mathematics and Computing: A Third Level Course, Number Theory Handbook, The Open University, 1996.
Contact us
For more information or to comment on this page, please send us a message.
This page last updated 22 June 2016