DI Management Home > Mathematics > Elementary number theory

# Some useful elementary number theory

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.

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

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}$.

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