1. SylabUZ
2. Faculty of Exact and Natural Sciences
3. winter term 2022/2023
4. Mathematics - First-cycle studies leading to Bachelor's degree
5. Number Theory

Generate PDF for this page

Number Theory - course description

Aim of the course

The aim is for the student to get the number theory course provided in the syllabus and to be able to apply it in practice in cryptography and computer science.

Prerequisites

Save changes

Linear Algebra 1 i 2

Scope

Lecture

1. Divisibility relation in the ring of integers (2 hours).
2. Least common multiple. Greatest common divisor and Euclid's algorithm, linear form for greatest common divisor, relationship between greatest common divisor and least common multiple. Coprime numbers. Fundamental theorem of arithmetic (2 hours).
3. Prime numbers. Canonical decomposition of a natural number into prime factors. Sieve of Eratosthenes. Goldbach's conjecture. Dirichlet's theorem. (6 hours).
4. Diophantine equations. (3 hours).
5. Congruences and their properties. Polynomial congruences and Lagrange's theorem. Wilson's theorem (3 hours).
6. Fermat's theorem on the decomposition of prime numbers of the form 4k+1 into the sum of two squares.
7. Chinese Remainder Theorem (3 hours)
8. Euler function and its properties. Euler's theorem and Fermat's little theorem (3 hours).
9. Arithmetic functions and their properties. Möbius and Liouvilla function (5 hours).
10. Legendre's symbol and his properties. Jacobi's symbol and its properties. Mersenne and Fermat numbers. Perfect numbers. Prime factors of Fermat numbers. Generalized sequences of Fermat numbers (5 hours).

Classes:

1. Proving properties of divisibility relations (2 hours).
2. Finding GCD and GCD for pairs of integers using the Euclidean algorithm, representing GCD using an appropriate linear form, and solving problems using the formula illustrating the relationship between GCD and GCD (3 hours).
3. Searching for prime numbers from a given interval using the Sieve of Eratosthenes, applying the canonical decomposition of a natural number, using calculated values of the p(x) function (3 hours).
4. Solving Diophantine equations using the matrix method. (3 hours).
5. Solving problems using the modulo congruence properties, proving certain congruences using Wilson's theorem, and applying the Chinese remainder theorem to problems (5 hours).
6. Calculating the values of the Euler function for natural numbers, calculating the remainder when dividing two natural numbers using Euler's theorem, and calculating the values of individual arithmetic functions (5 hours).
7. Solving congruences using Legendre's symbol (4 hours).
8. Solving problems with proofs using Fermat and Mersenne numbers (5 hours).

Teaching methods

Lectures: traditional lecture.

Exercises: joint solving of tasks related to the subject, exercises illustrating the application of theory, and discussion.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

1. Final test with tasks of varying difficulty, allowing for the assessment of whether the student has achieved the minimum learning outcomes.
2. Participation in lectures and a theoretical test at the last lecture.

The grade for the course consists of positive grades for exercises (60%) and lectures (40%).

Recommended reading

1. L.E. Dickson, Introduction to the theory of numbers, New York 1957.
2. W. Sierpiński, Elementary Theory of Numbers, PWN, Warszawa 1987.

Further reading

1. Ellina Grigorieva, Methods of Solving Number Theory Problems, Birkhäuse, 2018
2. Wacław Sierpiński, 250 Problems in Elementary Number Theory, New York, American Elsevier Pub. Co., 1970

Notes

Modified by dr Sebastian Czerwiński (last modification: 07-02-2024 20:31)