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

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.

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.

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

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

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.

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

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

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

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 #

Laboratory/Laboratory5/2method.md · 6.5 KB · updated 2026-07-31 21:14