CDM/Laboratory/Laboratory5/main
Raw

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 and L07 — Proofing (methods of proof) (proof methods, Tasks 6 & 8)
Deliverable Source code + report (see 5report.md)
Grading Banded: Easy 60–74 / Medium 75–89 / Hard 90–100 (see 4task.md)

Contents

# Part File
1 Objective 1purpose.md
2 Methodical guidelines (theory & algorithms) 2method.md
4 Task and order of execution 4task.md
5 Report contents 5report.md
6 Control questions 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; the code must reproduce the example outputs in 4task.md.
  • Self-contained theory — everything needed is in 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.

Laboratory/Laboratory5/main.md · 2.4 KB · updated 2026-08-01 17:39