Fundamentals of Combinatorics and Number Theory

Published

18 October 2026

Passport

  • Where and when. Semesters I–II of the 01.03.02 β€œApplied Mathematics and Informatics” program, β€œMathematics” track, in the curriculum for the 2025 intake.
  • Workload. 270 hours, 6 credits: 135 hours and 3 credits in each semester. In total, 120 contact hours (60 lecture hours, 60 seminar hours), 90 hours of independent work and 60 hours of exam preparation.
  • Department. Department of Discrete Mathematics.
  • Lecturer. The publicly available versions of the program name the stream but not a single lecturer for all FPMI streams; the lecturer’s name should be taken from the timetable of the specific semester.
  • Final assessment. The curriculum provides for assessment in both semesters; the exact form for your group should be checked against the current curriculum.

Contents of the published programs

Below are the complete topic lists of the department’s general course: fall 2022 and spring 2023. These are the most detailed documents available, but they do not promise that the program for the 2025 intake is identical.

Semester I: fall 2022 program

  1. Sets, subsets, operations, tuples and the Cartesian product.
  2. Maps, images and preimages, composition, the inverse map and Cartesian powers of a set.
  3. Equinumerosity, the Cantor–Bernstein theorem, countable and uncountable sets, Cantor’s theorem.
  4. Binary relations, equivalence, partial and linear orders, extremal elements.
  5. Operations, properties and isomorphisms of ordered sets.
  6. Preorders, total preorders, quasi-transitivity, acyclicity and lattices.
  7. The sum and product rules, the pigeonhole principle, two-colorings and the problem of pairwise non-orthogonal \((-1,0,1)\)-vectors.
  8. Arrangements, permutations, combinations with and without repetition; the binomial and multinomial formulas, identities and sums of powers.
  9. The inclusion–exclusion formula and alternating identities.
  10. Prime numbers, the infinitude of primes and the fundamental theorem of arithmetic.
  11. Divisor sums and the MΓΆbius function.
  12. The MΓΆbius inversion formula.
  13. Counting cyclic sequences via MΓΆbius inversion.
  14. General MΓΆbius inversion for partially ordered sets.
  15. Linear recurrence relations with constant coefficients.
  16. Integer partitions, Young diagrams, Euler’s theorems, the Hardy–Ramanujan formula.
  17. Formal power series and generating functions; Fibonacci and Catalan numbers and taking roots of series.
  18. The theory of congruences and residue systems.
  19. Binomial coefficients modulo a number.
  20. The Chevalley theorem.
  21. The ErdΕ‘s–Ginzburg–Ziv problem.

Semester II: spring 2023 program

  1. The Euclidean algorithm, the fundamental theorem of arithmetic and Euclid’s lemma.
  2. Congruences, residue systems, Euler’s and Fermat’s theorems.
  3. Linear congruences, the Chinese remainder theorem and Euler’s totient function.
  4. The number of roots of a polynomial modulo a prime and Wilson’s theorem.
  5. Quadratic congruences, quadratic residues and non-residues.
  6. The Legendre symbol and the law of quadratic reciprocity.
  7. Hadamard matrices, their constructions and the Hadamard conjecture.
  8. Binary codes, Hamming distance, the Hamming and Plotkin bounds, codes from Hadamard matrices.
  9. Coloring problems in terms of discrepancy and Hadamard matrices.
  10. Distribution of primes: the functions \(\pi(x)\), \(\theta(x)\), \(\psi(x)\) and Chebyshev’s theorem.
  11. The asymptotic law of distribution of primes and gaps between consecutive primes.
  12. Primitive roots, indices and algorithmic problems of the discrete logarithm.
  13. Dirichlet’s theorem on Diophantine approximation and Minkowski’s theorem.
  14. Finite continued fractions and convergents.
  15. Infinite continued fractions, quality of approximation and periodicity for quadratic irrationals.
  16. Algebraic and transcendental numbers, Liouville’s theorem and Gelfond’s theorem.
  17. Irrationality and transcendence of \(e\).
  18. Lattices, the determinant, the multidimensional Minkowski theorem and the Minkowski–Hlawka theorem.
  19. Sequences uniformly distributed modulo 1.
  20. Trigonometric sums, Weyl’s criterion, Gauss sums.
  21. The Agrawal–Kayal–Saxena primality test and its polynomiality.

Reading list given by the department

N. Ya. Vilenkin, Combinatorics; N. B. Alfutova and A. V. Ustinov, Algebra and Number Theory (Problem Book); M. Hall, Combinatorial Theory; A. M. Raigorodskii, The Linear-Algebraic Method in Combinatorics and Coloring Problems; A. I. Galochkin, Yu. V. Nesterenko, A. B. Shidlovskii, Introduction to Number Theory; I. M. Vinogradov, Elements of Number Theory; K. Chandrasekharan, Arithmetical Functions; J. W. S. Cassels, An Introduction to the Geometry of Numbers; A. Ya. Khinchin, Continued Fractions; A. A. Glibichuk et al., Fundamentals of Combinatorics and Number Theory: Problem Book; L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences; M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P.

Grading

No publicly available grading scheme or single sheet with thresholds was found for this course of the Department of Discrete Mathematics.

Sources and currency

Fall version page, version for programmers, spring 2023 program and 01.03.02 curriculum, 2025 intake.