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.

Laboratory/Laboratory5/1purpose.md · 1.1 KB · updated 2026-07-31 21:14