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
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\mid a$ means that $n$ divides $a$, and $n\mid a - b$ means that n divides $(a - b)$. For any integer $a$ we have $1|a$, $a|a$, and $a|0$.
- If $mn\mid a$ then $m\mid a$ and $n\mid a$ for any integers $m, n$. This follows since $mn\mid a \implies a = mnd$ for some $d$, hence $m\mid a$ and $n\mid 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^{k_1}p_2^{k_2}\cdots p_r^{k_r}$ for primes $p_1 < p_2 < \ldots < p_r$ and positive integers $k_1, \ldots, k_r$. For example, $360 = 2^33^25^1$ and $1323 = 3^37^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 ‘$\text{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 \bmod n$’ defines a binary operation where $a$ is equal to the remainder on dividing $b$ by $n$, with $0 \le a < n$.
- ‘mod’ as a congruence relation: The notation ‘$a \equiv b \pmod n$’ means
$a$ and $b$ have the same remainder when divided by $n$, or, equivalently,
$n\mid 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 \equiv b \pmod n \iff a \bmod n = b \bmod 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 $\Bbb{Z}_n$ [see note 2].
- Properties of congruence: for a fixed positive integer $n$ and any
integers $a, b, c, d$.
- Reflexive property: $a \equiv a \pmod n$.
- Symmetric property: If $a \equiv b \pmod n$ then $b \equiv a \pmod n$.
- Transitive property: If $a \equiv b \pmod n$ and $b \equiv c \pmod n$ then $a \equiv c \pmod n$.
- Addition and multiplication rules: If $a \equiv b \pmod n$ and $c \equiv d\pmod n$ then $a\pm c \equiv b\pm d \pmod n$ and $ac \equiv bd \pmod n$.
- Cancellation rule: If $ac \equiv bc \pmod n$ and $c\ne 0$ then $a\equiv b \pmod {(n \mathbin{/} \gcd(c,n))}$. If $\gcd(c,n)=1$ then $a\equiv b\pmod n$ [see note 3].
- Associative and distributive properties: $(a+b) + c \equiv a + (b+c) \pmod n$, $(ab)c \equiv a(bc) \pmod n$, and $a(b+c) \equiv ab + ac \pmod n$.
- If $a\equiv b\pmod n$ then $a^r \equiv b^r \pmod n$ for any integer $r\ge 1$.
- $a\equiv 0 \pmod n$ if and only if $n\mid a$.
- If $m$ and $n$ are coprime and $a \equiv b \pmod m$ and $ a\equiv b\pmod n$, then $a\equiv b \pmod {mn}$.
- The Euler totient function (or Euler phi function) of a positive integer $n$, denoted $\varphi(n)$, is defined to be the number of positive integers not exceeding $n$ which are relatively prime to $n$. For example, $\varphi(12) = 4$ as the 4 integers $\{1, 5, 7, 11\}$ are the only integers coprime to and not greater than 12; and $\varphi(7) = 6$ as the 6 integers $\{1, 2, 3, 4, 5, 6\}$ are coprime to and not greater than 7 [see also note 4].
- For any prime $p$, $\varphi(p) = p - 1$, since all numbers less than $p$ are relatively prime to it.
- If $m$ and $n$ are coprime, then $\varphi(m)\varphi(n) = \varphi(mn)$.
- Fermat's Little Theorem: If $p$ is a prime and $a$ is any integer, then $a^p \equiv a\pmod p$. If $\gcd(a,p)=1$, then $a^{p-1} \equiv 1\pmod p$. The latter is a special case of the Euler-Fermat Theorem below.
- Euler-Fermat Theorem: If $n$ is a positive integer and $a$ is any integer with $\gcd(a, n) = 1$, then $a^{\varphi(n)}\equiv 1\pmod n$.
- The Carmichael function of a positive integer $n$, denoted $\lambda(n)$, is defined as the smallest positive integer $m$ such that $a^m \equiv 1\pmod n$ for all integers $a$ relatively prime to $n$. It can be shown that $\lambda(n)$ divides $\varphi(n)$.
- The least common multiple of the non-zero integers $a$ and $b$, denoted $\text{lcm}(a, b)$, is the smallest positive integer that is a multiple of both $a$ and $b$. For example, $\text{lcm}(10, 15) = 30$. For any pair of integers $a$ and $b$, $\text{lcm}(a, b) \times \gcd(a, b) = |ab|$ .
- If $n=pq$ is the product of two distinct primes $p$ and $q$, then $\lambda(pq) = \text{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 \equiv 1 \pmod n$. We write $x = a^{-1} \bmod n$ or $x = (1/a) \bmod n$. A modular inverse exists if and only if $\gcd(a, n) = 1$. For example, 7 is a modular inverse of 3 modulo 20 since $3\times 7 = 21\equiv 1\pmod {20}$. We can write $7=3^{-1}\bmod {20}$ or $7=(1/3)\bmod {20}$.
Notes
1. Note that the expression ‘$a = b \bmod n$’ is satisfied by a unique integer $0 \le a < n$, but the congruence ‘$a \equiv b \pmod n$’ is satisfied by any integer of the form $b + nk$ for any integer $k$. For example, $16 \bmod 12 = 4$, but the congruence $a \equiv 16 \pmod {12}$ is satisfied by $a = 4, 16, 28, 40, \ldots$ and $a = -8, -20, -32,\ldots$.
2. Strictly speaking, $\Bbb{Z}_n$ is the set of equivalence classes modulo $n$. The set $\Bbb{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 \equiv 6 \pmod {11}$ for $x$. We have $n=11$ and the coefficients 9 and 6 have the common factor $c=3$, and 3 is coprime to 11 since $\gcd(c,n)=\gcd(3, 11) = 1$, so we can 'divide through' by 3 to get $3x \equiv 2 \pmod {11}$, leaving the modulus 11 unchanged. This has the single solution $x \equiv 8 \pmod {11}$ and this is also the solution to the original congruence. To see this note that $3x = 3\times 8 = 24 \equiv 2 \pmod{11}$ and $9x=9\times 8 = 72 \equiv 6\pmod{11}$.
However, if we want to solve $9x \equiv 6 \pmod {12}$, we have $n=12$ and common factor $c=3$, so we use the cancellation rule to obtain $3x \equiv 2 \pmod 4$. This time $\gcd(c,n) =\gcd(3, 12) = 3 \ne 1$, so we must divide the modulus 12 by 3. This latter congruence modulo 4 is solved by the single congruence $x\equiv 2\pmod 4$, and therefore the original congruence modulo 12 is solved by the three solutions $x = 2,6,10 \pmod{12}$. That is, $x = 2 + 4i$ for $i=0,1,2$. See that $3x=3\times 2 = 6 \equiv 2\pmod 4$, but this time we have three solutions modulo 12; namely, $9\times 2 = 18 \equiv 6\pmod{12}$, $9\times 6 = 54 \equiv 6\pmod{12}$, and $9\times 10 = 90 \equiv 6\pmod{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 21 December 2019