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|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$.
2. If $mn|a$ then $m|a$ and $n|a$ for any integers $m, n$. This follows since $mn|a \implies a = mnd$ for some $d$, hence $m|a$ and $n|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. See also A quick check that a number is prime.
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|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|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.

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. To compute $\varphi(n)$ for an arbitrary integer $n$, use the Fundamental Theorem of Arithmetic ($\S 4$ above) and the formula

    $\varphi(p^k) = p^{k-1}(p-1) = p^k\left(1-\frac{1}{p}\right)$.

    For example, to find $\varphi(24)$ note that $24 = 2^3 3^1$ by $\S 4$, $\varphi(3) = 3 - 1 = 2$ by $\S 14$, and $\varphi(2^3) = 2^{3-1}(2-1) = 2^2(1) = 4$. So, using $\S 15$, $\varphi(24) = \varphi(3) \varphi(8) = 2 \times 4 = 8$. Check: the 8 coprime integers $\lt 24$ are $\{1,5,7,11,13,17,19,23\}$. [see also note 4]
17. 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.

18. 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$.
19. 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)$.
20. 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|$, where $|ab|$ denotes the absolute value of $a \times b$.
21. If $n=pq$ is the product of two distinct primes $p$ and $q$, then $\lambda(pq) = \text{lcm}(p-1, q-1)$.
22. 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

To contact us, please send us a message. To make a comment see below.

This page last updated 9 September 2025