# 2. Methodical guidelines / Методичні вказівки

This section is **self-contained**: it develops the theory of the work's theme —
elementary number theory, two methods of proof, and function evaluation —
together with algorithms for the tasks in [4task.md](4task.md). No outside
material is required.

---

## Part A — Number theory

### 2.1 Divisibility and parity

For integers $a$ and $b$, we say **$b$ divides $a$** (written $b \mid a$) if
$a = b\cdot k$ for some integer $k$. An integer $n$ is **even** if $2 \mid n$ and
**odd** otherwise; equivalently, the parity is decided by the remainder
$n \bmod 2$:

```text
function parity(n):
    if n mod 2 == 0: return "Even"
    else:            return "Odd"
```

### 2.2 Primes and primality testing

A **prime** is an integer $p > 1$ whose only positive divisors are $1$ and $p$.
To test $n$, it suffices to look for a divisor up to $\sqrt{n}$: if $n = a\cdot b$
with $1 < a \le b$, then $a \le \sqrt{n}$, so a composite number always has a
factor there.

```text
function isPrime(n):
    if n < 2:            return false
    if n == 2 or n == 3: return true
    if n mod 2 == 0:     return false
    i ← 3
    while i*i ≤ n:                 # test only odd i up to √n
        if n mod i == 0: return false
        i ← i + 2
    return true
```

This runs in $O(\sqrt{n})$ time.

### 2.3 Greatest common divisor — the Euclidean algorithm

The **GCD** of $a$ and $b$ is the largest integer dividing both. It rests on the
identity $\gcd(a, b) = \gcd(b,\ a \bmod b)$, with $\gcd(a, 0) = a$: replacing the
larger number by the remainder never changes the common divisors and drives the
pair to zero.

```text
function gcd(a, b):
    a ← |a|;  b ← |b|
    while b ≠ 0:
        (a, b) ← (b, a mod b)
    return a
```

The number of steps is $O(\log \min(a, b))$ — very fast. For example,
$\gcd(48, 18)$: $48 \bmod 18 = 12$, $18 \bmod 12 = 6$, $12 \bmod 6 = 0$, so the
GCD is $6$.

![Euclidean algorithm computing gcd(48, 18) = 6 by repeated remainders](img/euclidean.png)

### 2.4 Least common multiple

The **LCM** is the smallest positive integer that both $a$ and $b$ divide. It is
tied to the GCD by

$$\operatorname{lcm}(a,b) \cdot \gcd(a,b) = |a\cdot b|,
\qquad\text{so}\qquad
\operatorname{lcm}(a,b) = \frac{|a\cdot b|}{\gcd(a,b)}.$$

```text
function lcm(a, b):
    if a == 0 or b == 0: return 0
    return |a * b| / gcd(a, b)      # division is exact: gcd divides a·b
```

For instance $\operatorname{lcm}(15, 20) = \dfrac{300}{\gcd(15,20)} = \dfrac{300}{5} = 60$.

### 2.5 Prime factorization

By the **Fundamental Theorem of Arithmetic**, every integer $n > 1$ has a
**unique** factorization into primes,
$n = p_1^{e_1} p_2^{e_2}\cdots p_k^{e_k}$. Find it by dividing out each prime
starting from $2$; any factor left above $1$ at the end is itself prime.

```text
function primeFactorization(n):
    factors ← empty list of (prime, exponent)
    d ← 2
    while d*d ≤ n:
        if n mod d == 0:
            e ← 0
            while n mod d == 0: n ← n / d;  e ← e + 1
            append (d, e) to factors
        d ← d + 1
    if n > 1: append (n, 1) to factors      # the last prime factor
    return factors
```

Format the result as `p1^e1 * p2^e2 * ...` (an exponent of $1$ may be omitted):
$56 = 2^3 \cdot 7$.

![Factor tree decomposing 56 into the primes 2 · 2 · 2 · 7 = 2³ · 7](img/factor_tree.png)

### 2.6 Euler's totient function

$\varphi(n)$ counts the integers in $\{1, \dots, n\}$ that are **coprime** to $n$
(share no common factor with it). If $n = p_1^{e_1}\cdots p_k^{e_k}$, then

$$\varphi(n) = n \prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right).$$

```text
function totient(n):
    result ← n
    m ← n
    p ← 2
    while p*p ≤ m:
        if m mod p == 0:
            while m mod p == 0: m ← m / p     # remove all copies of p
            result ← result − result / p      # apply factor (1 − 1/p)
        p ← p + 1
    if m > 1: result ← result − result / m    # a final prime factor
    return result
```

For $n = 12 = 2^2\cdot 3$: $\varphi(12) = 12\left(1-\tfrac12\right)\left(1-\tfrac13\right) = 12\cdot\tfrac12\cdot\tfrac23 = 4$ (the coprime numbers are $1, 5, 7, 11$).

![Euler's totient φ(12) = 4, with the numbers 1, 5, 7, 11 coprime to 12 highlighted](img/totient.png)

---

## Part B — Methods of proof

### 2.7 Direct proof

A **direct proof** of "if $P$ then $Q$" assumes $P$ and derives $Q$ by a chain of
definitions and known facts. For the statement *"if a number is even, then it is
divisible by 2"*: assume $n$ is even. By the definition of even, $n = 2k$ for some
integer $k$. Then $n$ has $2$ as a factor, i.e. $2 \mid n$. $\blacksquare$

A program can **validate** such a statement by making the reasoning explicit —
recording each step (hypothesis → definition → conclusion) and, as evidence,
checking that it holds on a range of concrete inputs. Note that testing instances
*illustrates* but does not *replace* the general argument.

### 2.8 Mathematical induction

To prove that $P(n)$ holds for all positive integers $n$:

1. **Base case** — prove $P(1)$.
2. **Inductive step** — assume $P(k)$ (the *induction hypothesis*) and prove
   $P(k+1)$.

Then $P(n)$ holds for every $n \ge 1$. Worked example — *the sum of the first $n$
odd numbers is $n^2$*:

- **Base:** $n = 1$: the sum is $1 = 1^2$. ✓
- **Hypothesis:** assume $1 + 3 + \cdots + (2k-1) = k^2$.
- **Step:** adding the next odd number,
  $$1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + (2k+1) = (k+1)^2. \ \blacksquare$$

A program can **facilitate** the proof by verifying the base case and checking the
inductive step's algebraic identity (or verifying $P(n)$ for $n = 1, 2, \dots, N$
as supporting evidence).

---

## Part C — Functions

### 2.9 Evaluating a function on its domain

A **function** $f$ assigns to each input in its **domain** a single output; the
set of outputs is its **range**. To evaluate, substitute the value and simplify —
for $f(x) = x^2 + 2x + 1 = (x+1)^2$ we get $f(3) = 3^2 + 2\cdot3 + 1 = 16$. Its
domain is all real numbers and its range is $[0, \infty)$. When evaluating,
respect the domain: guard against operations that are undefined there (division
by zero, the square root of a negative number, and so on).

---

## 2.10 Complexity summary

| Routine | Cost |
|---|---|
| `parity` | $O(1)$ |
| `isPrime` (trial division) | $O(\sqrt{n})$ |
| `gcd` (Euclid) | $O(\log \min(a,b))$ |
| `lcm` (via GCD) | $O(\log \min(a,b))$ |
| `primeFactorization` | $O(\sqrt{n})$ |
| `totient` (via factorization) | $O(\sqrt{n})$ |