In this chapter we provide the necessary prerequisites from multiplicative number theory regarding primes, divisibility and approximation by rationals.

Divisibility in ℤ. Euclidean algorithm

The basic objects of our story are the set of natural numbers ℕ = {1, 2, 3, …} and the set of integers ℤ. In addition, we often deal with the set of rationals ℚ and the set of real numbers ℝ. An element of ℝ\ℚ is called irrational. Shortly we will need the complex numbers ℂ as well.

The set of integers ℤ forms a ring equipped with the usual addition and multiplication. The operation of division, the inverse to multiplication, applies to pairs (a, b) with b ≠ 0. We say that a number b ≠ 0 divides a (writing b | a) or, equivalently, b is a divisor of a or a is divisible by b or a is a multiple of b, if a = bq holds for some integer q. The number q is called the quotient of a by b. The number 0 is divisible by any integer b ≠ 0. If a ≠ 0 then the number of its divisors is finite. We use the notation b ∤ a to say that b does not divide a.