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)$.

Laboratory/Laboratory5/6questions.md · 1.9 KB · updated 2026-07-31 21:14