# 1. Objective / Мета роботи

**Apply elementary number theory and formal methods of proof by implementing
them as programs, and evaluate a function with regard to its domain.**

By the end of the work the student should be able to:

- determine the **parity** of an integer and test an integer for **primality**
  efficiently (trial division up to $\sqrt{n}$);
- compute the **greatest common divisor** with the **Euclidean algorithm** and
  the **least common multiple** through its relation to the GCD;
- produce the **prime factorization** of an integer in the form
  $p_1^{e_1}\cdot p_2^{e_2}\cdots$ and compute **Euler's totient** $\varphi(n)$;
- construct and validate a **direct proof** and a proof by **mathematical
  induction** (base case, hypothesis, inductive step);
- **evaluate a function** at a point while reasoning about its **domain and
  range**;
- explain the **algorithm** behind each routine and analyse its **time
  complexity**.

The work draws the number-theoretic facts together with the proof techniques of
the course, turning both into running, testable code.