Divisibility

Number theory is an area of mathematics that has grown from studies of natural numbers

$$1, 2, 3, \ldots$$or, slightly more generally, studies of integers

$$0, \pm 1, \pm 2, \pm 3, \ldots$$to much more complicated structures, but you still can trace the origins of its problems to the set of integers (denoted by $\mathbb{Z}$). We meet integers for the first time in childhood, and they can seem well-known, boring, and useful only for counting things. None of this is right if we take a closer look. There are still a lot of unsolved problems concerning integers, they exhibit surprising patterns and relationships. And, unexpectedly, in the 20th-century number theory has become crucial for computer security.

Let's learn some basic number theory concepts.

Divisibility

We can add, subtract and multiply integers. But we are not always able to divide one integer by another if we want the result to stay within the realm of integers. This leads us to a fundamental definition:

Given two integers $a$ and $b$, we say that $a$ divides $b$, or that $b$ is divisible by $a$, if there is some integer $k$ such that $b = ak$ (we also say that $b$ is a multiple of $a$).

If $a$ divides $b$, we denote it as $a \mid b$. For example, $5 \mid 65$, because $65 = 5 \cdot 13$. Also, $7 \mid 119$ (check it!), but $7$ doesn't divide $86$, because no multiple of $7$ is equal to $86$.

Using only the definition, we can derive the property of transitivity:

If $a \mid b$ and $b \mid c$, then $a \mid c$.

Indeed, $b = ak$ for some integer $k$ and $c = bm$ for some integer $m$, so, $c = (ak)m = a(km)$ is a multiple of $a$.

If $a \mid b$, we also say that $a$ is a divisor of $b$. For instance, $12$ has 6 positive divisors ($1, 2, 3, 4, 6, 12$) and the same number of negative divisors ($-1, -2, -3, -4, -6, -12$).

Prime numbers and the unique factorization

Let $n$ be a positive integer and $n \neq 1$. Trivially, $1$ and $n$ divide $n$. If $1$ and $n$ are the only positive integers dividing $n$, we say that $n$ is a prime number, or simply a prime. If $n \neq 1$ but is not a prime, we say that $n$ is composite. The number $1$ is not considered to be either prime or composite. The first few primes are $2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots$

Now let's look at a famous theorem with a solemn name:

The Fundamental Theorem of Arithmetic: Every positive integer can be written uniquely (except for the order of factors) as a product of primes.

For instance, $600 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 \cdot 5$. We wrote primes in this factorization in the increasing order, it's a common practice. Also, it is convenient to bunch together all equal factors: $600 = 2^3 \cdot 3 \cdot 5^2$.

So, the primes act as ''building blocks'' for all positive integers (and if we can also apply negation — for all non-zero integers). But surprisingly, we do not have an efficient algorithm for factoring an arbitrary integer into a product of primes. This fact is extremely important for modern cryptography.

The greatest common divisor

Suppose we have two integers, such as $16$ and $24$. We can look for common divisors, i.e., integers that divide both of them. For example, $8$ is their common divisor, and you can easily notice it is their largest common divisor. Similarly, $5$ is a common divisor of $20$ and $50$, but it is not the largest, since $10$ is also a common divisor.

Mathematicians usually use "the greatest common divisor" instead of "the largest common divisor", and this simple concept turns out to be extremely important in applications.

Definition: The greatest common divisor of two integers $a$ and $b$ (at least one different from zero) is the largest integer that divides both of them.

The greatest common divisor of $a$ and $b$ is denoted by $\gcd(a,b)$. If $\gcd(a,b) = 1$, we say that $a$ and $b$ are relatively prime. Try to check, for example, that $\gcd(16, 27) = 1$ (i.e., these numbers are relatively prime) and $\gcd(36, 27) = 9$.

We'll soon study a simple, but efficient algorithm to compute the greatest common divisor of any two integers. The extended version of this algorithm is crucial for some modern cryptosystems.

Conclusion

In this piece of theory, we have started exploring a more advanced part of the number theory and got acquainted with the concept of divisibility more thoroughly. Let's now quickly go over the most notable points:

• Divisibility is denoted by $a \mid b$ and reads as "$a$ divides $b$", which also means that $b$ is divisible by $a$ without a remainder.
• Divisibility is transitive, which means that if $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$.
• According to the Fundamental Theorem of Arithmetic every positive number can be uniquely represented as a product of primes.
• The greatest common divisor of two integers $a$ and $b$ or the largest integer that divides both $a$ and $b$ is denoted by $gcd(a,b)=n$.