ECTS
6 credits
Component
Faculty of Science
Description
This UE aims to introduce the elementary concepts of arithmetic and enumeration useful for the beginning of the degree in mathematics.
Objectives
Elementary enumeration
- Cardinal of a finite set. Cardinal and set operations. Cardinal and injective, surjective and bijective applications. Cardinal of a set of applications. Number of parts of a set. Indicator function.
- Introduction to infinite cardinals. Bijection between sets. Denumerability. Cantor's diagonal argument. X and P(X) do not have the same cardinal. R is uncountable.
- Arrangements, permutations, combinations (binomial coefficients), Pascal's triangle, binomial formula.
- General screening formula (application to the counting of disturbances, overjections, etc.).
- Binary relation on a set. Equivalence relation, partition in equivalence classes, quotient of a set by an equivalence relation (examples on already known sets). Order relation, partial, total, examples.
- Applications to finite elementary probability examples (number of favorable cases/total number of cases)
Elementary arithmetic in Z
- Whole numbers, writing in a base.
- Divisibility, prime numbers (infinity, sieve algorithm). Euclidean division (Euclid's algorithm).
- PGCD and PPCM. Bézout's theorem (and extended Euclid's algorithm), prime numbers between them, Euclid's lemma, Gauss' lemma. Diophantine equations ax + by = c. Decomposition into product of primes. Application: for n ∈ N, is either an integer or irrational.
- Modular arithmetic (congruences). Fermat's little theorem. Chinese remainder theorem.
- Study of Z/nZ, seen as a ring. Invertible, Z/nZ is a body if and only if n is prime. Reinterpretation of Bézout's theorem. Reinterpretation of Fermat's small theorem (definition of Euler's indicator, Euler's theorem). Reinterpretation of the Chinese remainder theorem.
- Illustration by cryptography.
Necessary pre-requisites
S1 mathematics program (mainly reasoning and set theory) and high school mathematics program (at least first year mathematics specialization)
Recommended prerequisites:
S1 mathematics program (mainly reasoning and set theory) and high school mathematics programs (ideally senior mathematics specialization, or even expert mathematics option).
Additional information
Hourly volumes* :
CM : 30 h
TD : 30 h
TP : 0
Land : 0