Arithmetic and Counting

This course unit aims to introduce the basic concepts of arithmetic and counting that are useful for the beginning of the bachelor’s degree in mathematics.

Basic Counting

• Cardinality of a finite set. Cardinality and set-theoretic operations. Cardinality and injective, surjective, and bijective functions. Cardinality of a set of functions. Number of parts of a set. Indicator function.
• Introduction to infinite cardinals. Bijection between sets. Countability. Cantor's diagonal argument. X and P(X) do not have the same cardinality. R is uncountable.
• Arrangements, permutations, combinations (binomial coefficients), Pascal's triangle, the binomial formula.
• General screening formula (application to counting disruptions, over-injections, etc.).
• Binary relation on a set. Equivalence relation, partition into equivalence classes, quotient of a set by an equivalence relation (examples using sets already introduced). Order relation, partial, total; examples.
• Applications to examples of elementary finite probability (number of favorable outcomes / total number of outcomes)

Elementary Arithmetic in Z

• Integers, writing in a base.
• Divisibility, prime numbers (infinity, sieve algorithm). Euclidean division (Euclid's algorithm).
• GCD and LCM. Bézout’s theorem (and the extended Euclidean algorithm), relatively prime numbers, Euclid’s lemma, Gauss’s lemma. Diophantine equations of the form ax + by = c. Prime factorization. Application: For n ∈ N, is either an integer or irrational.
• Modular arithmetic (congruences). Fermat's Little Theorem. The Chinese Remainder Theorem.
• Study ofZ/nZ, viewed as a ring. Inverses:Z/nZ is a field if and only if n is prime. Reinterpretation of Bézout’s theorem. Reinterpretation of Fermat’s Little Theorem (definition of Euler’s indicator, Euler’s theorem). Reinterpretation of the Chinese Remainder Theorem.
• An example from cryptography.

First-semester mathematics curriculum (primarily Reasoning and Set Theory) and high school mathematics curricula (at a minimum, the mathematics track for the 11th grade)

Recommended prerequisites:

First-semester mathematics curriculum (primarily Reasoning and Set Theory) and high school mathematics curricula (ideally the mathematics specialization in the final year, or even the advanced mathematics elective).

Hourly volumes*:

            CM: 30 hours

            TD: 30 hours

            TP: 0

            Land: 0