Divisibility

Induction

Let us have a closer look at the set N = {0, 1, 2, . . .} of natural numbers. In fact, we have not yet defined this set accurately, and we will refrain from doing it during this course.5 We have taken the set N with some ‘basic properties’, like 0 6= 1 or even 2 < 3 and 3+2 = 5. Now we are to analyze the main property of N—that of induction.
In its most well-known form, the Induction Principle says that

For an arbitrary predicate φ, if φ(0) holds and for each n ∈ N, φ(n) implies φ(n + 1), then φ(n) holds for all n ∈ N.

One can easily put this into symbols (here φ is fixed):

(φ(0)∧∀n∈ℕ*(φ(n)→φ(n+1)))→∀n ∈ℕ*φ(n)

The statement φ(0) is called the base step of induction, while ∀n ∈ℕ*(φ(n)→φ(n+1)) is called the inductive step, and the statement φ(n) for each n is called the inductive hypothesis (which is usually shortened to ‘IH’).
It is possible to rephrase the principle without mentioning any ‘predicates’ but sets:

For an arbitrary set X⊆ℕ, if ∅∈X and for each n∈ℕ, n∈X implies n+1∈X, then X=ℕ.

Indeed, for each predicate φ, we can consider the subset X = {n ∈ N | φ(n)} of N and, conversely, we can put the predicate n ∈ X into correspondence with a set X ⊆ N. Thus, the new statement of the Principle is equivalent to the original one.

Let us give a more concise rewording of the Principle, eliminating any ‘predicates’ by the way. We call a set X ⊆ N progressive, if for each n ∈ ℕ, from ∀m < n m ∈ X, it follows that n ∈ X. We write Prog(X) if X is progressive. Then the principle reads this way:

For an arbitrary set X ⊆ ℕ, if X is progressive, then X = ℕ.

Informally, a set X is progressive if it ‘climbs’ the set ℕ, ‘conquering’ n as soon as it has ‘conquered’ all lesser numbers. Most strikingly, this form of induction apparently lacks the base step. But this is not the case.

Lemma 1. If X is progressive, then 0 ∈ X.
Proof. Suppose that for every n, ∀m < n m ∈ X implies n ∈ X. Let us specify n as 0. Consider the assumption ∀m < 0 m ∈ X, that is, ∀m (m < 0 → m ∈ X). This statement is vacuously true as m < 0is false for each natural m. Hence, 0 ∈ X must be true as well.

The last form of induction for us to consider is the Least Number Principle, which states:

For an arbitrary set X ⊆ N, if X 6= ∅, then there exists a least element min X of X.

If put in symbols (for a certain X fixed), the Principle reads:

∃m m ∈ X → ∃n (n ∈ X ∧ ∀m (m < n → m /∈ X))

In fact, all the three forms of induction introduced hereunto are logically equivalent to each other.

So, each may be looked upon as the principle of induction.
Theorem 1. The following statements are equivalent:
1. the Strong Induction Principle;
2. the Least Number Principle;
3. the Induction Principle.

Divisibility

It is time to apply our knowledge of induction to natural and integer arithmetic. As earlier, we will assume some facts without a proof, like the commutativity law for addition: n + m = m + n for every m, n ∈ ℤ. Such facts can be easily derived by induction from the so called recursive definitions for arithmetical operations. But this topic is a bit bigger than the scope of our Course can contain.

Divisibility. From now on, the term ‘number’ will denote an integer number by default. We say that a number a divides a number b if there exists some k ∈ ℤ such that b = ak. Conversely, b is said to be divisible by a in this case. Also, we call a a divisor of b and call b a multiple of a. We write a | b when a divides b.

Lemma 2. For every a, b, c, the following hold:
1. a | a;
2. if a | b and b | c, then a | c;
3. if a | b and b | a, then a = ±b.
Proof. The fact that a = a · 1 gives us the first statement. For the second one, assume a | b and b | c, that is, b = ak1 or c = bk2 for some numbers k1, k2. Hence we get c = bk2 = (ak1)k2 = a(k1k2), which implies a | c. For the final one, assume both a | b and b | a. Then a = bk1 and b = ak2 for some k1, k2. This yields a = a(k1k2). Now, let us see if a = 0. If it is so, then b = 0 · k2 = 0 = a.
Otherwise, one can cancel a out to obtain 1 = k1k2. We take it as a fact that 1 can be factorized either as 1 · 1 or as (−1) · (−1). Thus, either a = b or a = −b.

Lemma 3. If a | b and a | c, then a |(b + c) and a |(b − c).
Proof. Assuming b=a*(k_1) and c=(a_)*(k_2), we getb±c=a*(k_1)+a*(k_2)=a*((k_1)+(k_2)) by applying the distributivity law (taken without a proof).

Theorem 2. For every natural numbers a and b≠0, there exists a unique pair (q,r)∈ℕ2 such that a=b*q+r and 0≤r<b.
Proof. Consider the set X={s∈ℕ|a<b*s}. We take as a fact, that multiplying by a positive number b is monotonic, i. e., b*x<b*y when x<y. Hence, b*(a+1)>b*a≥1⋅a=a and a+1∈X. So, X is non-empty. By the Least Number Principle, there exists some (s^′)=min(X). If (s^′)=0, then a<b*(s^′)=0, which is impossible for a natural a. Otherwise, (s^′)=q+1 for some q∈ℕ, where b*q≤a. Hence, 0≤a-b*q. If a-b*q≧b, there would be a-b*(s^′)=a-b*(q+1)≧0, that is, a≥b*(s^′), which is not the case. Therefore, 0=a-b*q<b and one can safely put r=a-b*q. The existence of a required pair is thus proved.
Suppose there are two such pairs (q,r) and ((q^′),(r^′)). We have both a=b*q+r and a=b*(q^′)+(r^′), while 0≤r,(r^′)<b. If q=(q^′), then, clearly, r=(r^′) as well. Otherwise, without loss of generality, we assume that q<(q^′), that is, q+1≤(q^′). Hence, r-(r^′)=b*(q^′)-b*q=b((q^′)-q)≥b. Then r≥b+(r^′)≥b, which is not so.

Such a number q is called the partial quotient and r is called the remainder after division of a by b. This result can be easily generalized to arbitrary integers: For every numbers a and b≠0, there exists a unique pair (q,r)∈ℤ⨉ℕ such that a=b*q+r and 0≤r<|b|.

Modular arithmetic

Let m be a positive number. We say that a is congruent to b modulo m if m |(a − b). We write a ≡ b (mod m) and call the number m a modulus in such a case.

Remark: As each number is divisible by 1, x≡y (mod 1) for all numbers x and y. This makes congruence modulo 1 a trivial, uninteresting property. Therefore, we will usually suppose m>1 in x ≡ y (mod m).
While it is possible to consider congruence modulo 0, where x ≡ y (mod 0) means 0|(x − y), that is, x − y = 0, this predicate is no more interesting: every number is only congruent to itself modulo 0. Congruence for negative moduli is not needed either since m|(x − y) is equivalent to −m|(x − y).

Lemma 4. For any numbers a, b, m, it holds that a≡b(mod m) iff a and b leave the same remainder when divided by m.
This lemma has some corollaries:
1. No two of the numbers 0, 1, . . . , m − 1 are congruent modulo m.
2. Suppose r is the remainder after dividing a by m. Then a ≡ r (mod m).
3. For any numbers a, b, m, the following hold:
1. a ≡ a (mod m);
2. if a ≡ b (mod m), then b ≡ a (mod m);
3. if a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m).

The most interesting and most important point about congruence is that it ‘respects’ the arithmetical operations.
Lemma 5. Suppose that a ≡ b (mod m) and c ≡ d (mod m). Then the following hold:
1. a+c≡b+d(mod m);
2. a*c≡b*d(mod m);
3. an≡bn(mod m) for every n∈ℕ.

Prime numbers and factorization. A number p > 1 is called prime if it is divisible by ±1 and by ±p but nothing else. Otherwise, a number greater than 1 is called composite.
A representation of the form n=(p_1)(a_1)*(p_2)(a_2)…(p_s)(a_s) for a number n>1, where (p_i) are pairwise distinct primes and (a_i)∈ℕ, is called a (prime) factorization of n. One may naturally suppose that every prime number p takes part in a factorization of n but just finitely many of them have non-zero degrees a. It is possible to factorize 1 as well, but each prime shall have degree 0 then. Two factorization are distinct iff some prime number has different degrees in these.

There are a few theorems, which are crucial for this topic.
Theorem 3. (Fundamental Theorem of Arithmetic). For each number n>1, there exists a unique prime factorization.
Theorem 4. There are infinitely many prime numbers.
Lemma 6. (Divisibility Criterion). For any non-zero numbers a and b, a divides b iff (α_i)≤(β_i)for each prime (p_i), where (α_i) (or (β_i)) is the degree of pi in the factorization of a (respectively, b).

A few more classical theorems

We say that a number d∈ℕ is a greatest common divisor of numbers a and b if (1) d|a and d|b, and (2) for each (d^′)∈ℕ, from (d^′)|a and (d^′)|b, it follows that (d^′)|d. We write gcd(a,b)=d in such a case. In other words, d is such a common divisor of a and b that is a multiple of any (other) common divisor (d^′). A priori, it is not obvious why such a number d exists.
Lemma 7. For every a and b, there exists a unique number d such that d=gcd(a,b).

We say that a number m∈ℕ is a least common multiple of numbers a and b if (1) a|m and b|m and (2) for each (m^′)∈ℕ, from a|(m^′) and b|(m^′), it follows that m|(m^′). We write lcm(a,b)=m in such a case. In other words, m is such a common multiple of a and b that divides any (other) common multiple (m^′).