# Laboratory Work 5 — Number Theory and Proof Methods

> Fifth laboratory work of **Computer Discrete Mathematics**. You implement a
> suite of elementary **number-theory** routines (parity, primality, GCD/LCM,
> prime factorization, Euler's totient), demonstrate two formal **proof methods**
> (direct proof and mathematical induction), and evaluate a function on its
> domain.

## At a glance

| | |
|---|---|
| **Topic** | Elementary number theory, methods of proof, function evaluation |
| **Prerequisite lectures** | [L08 — Number theory](../../Lectures/CDM-L08.md) and [L07 — Proofing (methods of proof)](../../Lectures/CDM-L07.md) (proof methods, Tasks 6 & 8) |
| **Deliverable** | Source code + report (see [5report.md](5report.md)) |
| **Grading** | Banded: Easy 60–74 / Medium 75–89 / Hard 90–100 (see [4task.md](4task.md)) |

## Contents

| # | Part | File |
|:--:|---|---|
| 1 | Objective | [1purpose.md](1purpose.md) |
| 2 | Methodical guidelines (theory & algorithms) | [2method.md](2method.md) |
| 4 | Task and order of execution | [4task.md](4task.md) |
| 5 | Report contents | [5report.md](5report.md) |
| 6 | Control questions | [6questions.md](6questions.md) |

## Conventions

- **Language** — source code and the report are in **English**.
- **Implement it yourself — no built-in shortcuts.** Do not call a library or
  built-in that performs the core task for you (e.g. no `HashSet`/`set()`/`Set`
  for sets, no library graph/relation type, no `math.gcd`, no `eval`). Build the
  mechanism from basic primitives — arrays/lists, loops, arithmetic, strings.
- **Deliverable** — submit the source code **and** a report structured as in
  [5report.md](5report.md); the code must reproduce the example outputs in
  [4task.md](4task.md).
- **Self-contained theory** — everything needed is in [2method.md](2method.md);
  no external material is required.

## Summary

Number theory is the study of the integers — divisibility, primes, and the
functions built on them — and it is the classical training ground for
**mathematical proof**. This work pairs the two: you compute with integers
(parity, primality by trial division, the Euclidean algorithm for the GCD, the
LCM via the GCD, prime factorization, and Euler's totient), and you make
statements about them rigorous through a **direct proof** and a proof by
**induction**. A final task evaluates a function while respecting its domain and
range. The tasks are grouped into three difficulty bands.