# 6. Control questions and tasks / Контрольні запитання і завдання

## Divisibility, primes, GCD/LCM

1. Define **$b \mid a$** ("$b$ divides $a$"). When is an integer **even**? How
   does the parity follow from $n \bmod 2$?
2. Define a **prime number**. Why is it enough to test divisors only up to
   $\sqrt{n}$ when checking primality?
3. State the identity the **Euclidean algorithm** is based on. Use it to compute
   $\gcd(48, 18)$, showing each step.
4. State the relation between $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$. Use it to
   find $\operatorname{lcm}(15, 20)$.

## Factorization and totient

5. State the **Fundamental Theorem of Arithmetic**. Give the prime factorization
   of $56$.
6. Define **Euler's totient** $\varphi(n)$. Write the product formula in terms of
   the distinct prime factors of $n$, and use it to compute $\varphi(12)$.
7. Which integers in $\{1, \dots, 12\}$ are counted by $\varphi(12)$? List them.

## Methods of proof

8. Describe the structure of a **direct proof** of a statement "if $P$ then $Q$".
   Give a direct proof that if $n$ is even then $2 \mid n$.
9. State the **principle of mathematical induction** (base case and inductive
   step). What is the *induction hypothesis*?
10. Prove by induction that the sum of the first $n$ odd numbers equals $n^2$.
11. Why does verifying a statement for many specific inputs **not** constitute a
    proof, whereas an induction argument does?

## Functions and complexity

12. What are the **domain** and **range** of a function? Give the domain and range
    of $f(x) = x^2 + 2x + 1$, and evaluate $f(3)$.
13. State the time complexity of `isPrime`, `gcd`, and `totient`, and justify each
    in one sentence.

## Tasks by hand

14. Compute $\gcd(84, 30)$ and then $\operatorname{lcm}(84, 30)$.
15. Give the prime factorization of $360$ and use it to compute $\varphi(360)$.