Some useful elementary number theory

We use most of these principles of number theory on our page on the mathematics behind the RSA algorithm.

1. 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$.
2. 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$.
3. 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.
4. 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$.
5. 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.
6. 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$.
7. $a$ and $b$ are coprime if and only if $\gcd(a, b) = 1$.
8. ‘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$.
9. ‘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].
10. 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].
11. Properties of congruence: for a fixed positive integer $n$ and any integers $a, b, c, d$.
    1. Reflexive property: $a \equiv a \pmod n$.
    2. Symmetric property: If $a \equiv b \pmod n$ then $b \equiv a \pmod n$.
    3. Transitive property: If $a \equiv b \pmod n$ and $b \equiv c \pmod n$ then $a \equiv c \pmod n$.
    4. 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$.
    5. 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].
    6. 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$.
    7. If $a\equiv b\pmod n$ then $a^r \equiv b^r \pmod n$ for any integer $r\ge 1$.
    8. $a\equiv 0 \pmod n$ if and only if $n\mid a$.
12. If $m$ and $n$ are coprime and $a \equiv b \pmod m$ and $ a\equiv b\pmod n$, then $a\equiv b \pmod {mn}$.
13. 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].
14. For any prime $p$, $\varphi(p) = p - 1$, since all numbers less than $p$ are relatively prime to it.
15. If $m$ and $n$ are coprime, then $\varphi(m)\varphi(n) = \varphi(mn)$.
16. 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.
17. 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$.
18. 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)$.
19. 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|$ .
20. If $n=pq$ is the product of two distinct primes $p$ and $q$, then $\lambda(pq) = \text{lcm}(p-1, q-1)$.
21. 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

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