Ateneo - UPO

Elementary number theory. Some basic notions of linear algebra.

Recommended textbooks:
+ Bramanti, Pagani, Salsa, "Analisi matematica 1 con elementi di geometria e algebra lineare", Ed. Zanichelli.
+ Teacher's notes uploaded to the DIR platform.

The course aims to provide students with the fundamental knowledge of linear algebra and elementary number theory, introducing essential mathematical concepts and methods for a basic education in Computer Science. The course covers the main topics of vector and matrix calculus, systems of linear equations, vector spaces, and linear transformations, together with fundamental concepts from number theory, such as divisibility, prime numbers, congruences, and modular arithmetic. At the end of the course, students will have acquired the ability to use appropriate mathematical language and to apply the algebraic tools introduced in order to formalize and solve simple problems. The educational objective of the course is to develop students’ skills in abstraction, logical reasoning, and mathematical modelling, providing them with the mathematical foundations necessary to undertake the study of subsequent computer science subjects and to understand the use of algebraic structures and methods in the design and analysis of computational solutions.

Basic mathematical knowledge acquired during upper secondary education, with particular reference to the fundamental properties of integers, arithmetic, elementary algebra, equations and inequalities, as well as the basic properties of the Cartesian plane and analytic geometry. Students are also expected to be able to read and produce short written texts in Italian and to understand simple mathematical arguments.

The course will be delivered through traditional blackboard lectures, including both a theoretical component and a component devoted to the discussion and solution of exercises. Each topic will be introduced through a general discussion aimed at promoting an intuitive understanding of the concepts and highlighting their meaning and underlying motivations. Subsequently, the definitions, fundamental results, and methodological tools relevant to each topic will be presented, together with examples aimed at clarifying their application and interpretation. Part of the lectures will be devoted to exercises, which will be proposed and discussed with the active participation of students in order to develop analytical skills, critical thinking, and autonomy in problem solving.

Students with physical disabilities, Learning Disabilities or Special Education Needs can request specific services and tools via the Staff Sviluppo e Coordinamento Carriere e Servizi alle Studentesse e agli Studenti, consulting the University webpage: https://uniupo.it/it/servizi/servizi-studentidisabili-e-dsa

Students with disabilities, learning disabilities or special education needs, once they have contacted the University Staff, can refer to the tutor in charge of the course to define the examination modalities, concerning academic aspects.

The examination consists of two written tests, each lasting 30 minutes: one test containing exercises related to Modular Arithmetic and one test containing exercises related to Linear Algebra. Each test covers most of the topics addressed during the course and may be taken in different examination sessions, provided that both tests are completed no later than December 2027.

During the written tests, only the use of a calculator is allowed.

The Linear Algebra test consists of two exercises, each worth 16 points. The Modular Arithmetic test consists of three exercises and a quiz; the points assigned to each exercise are specified in the examination paper. Incorrect answers in the quiz do not result in penalties. Even if an exercise is not solved completely correctly, the correct parts of the solution process will still be assessed.

A passing grade is achieved with a mark of 18/30 or higher. This corresponds to the achievement of the minimum learning objectives of the course: the student demonstrates an essential knowledge of the fundamental topics covered and is able to apply the main methods and results introduced to solve standard problems. Minor inaccuracies or non-substantial calculation errors are acceptable, provided that the solution approach demonstrates an adequate understanding of the concepts and a correct formulation of the problem.

A grade between 18/30 and 20/30 indicates a sufficient preparation, with a basic knowledge of the topics and a still limited ability to apply the methods independently.

A grade between 21/30 and 24/30 indicates a fair preparation: the student demonstrates a good knowledge of the course contents, is able to correctly apply the main techniques, and approaches exercises with a reasonable degree of autonomy.

A grade between 25/30 and 27/30 indicates a good or very good preparation: the student demonstrates mastery of the topics covered, the ability to connect different concepts, and good autonomy in problem solving.

A grade between 28/30 and 30/30 indicates an excellent preparation: the student possesses an in-depth knowledge of the topics, applies mathematical tools confidently and rigorously, solves exercises completely, and uses appropriate mathematical language.

Honors (30 cum laude) may be awarded to students who, in addition to achieving an excellent grade, demonstrate particular mastery of the contents, independent reasoning skills, and clarity of exposition.

In cases of uncertainty, or whenever the written tests do not allow the student’s level of preparation to be assessed with sufficient clarity, the instructor reserves the right to require an additional oral examination aimed at verifying the actual acquisition of the knowledge and skills specified in the learning objectives of the course.

To pass the module examination, students must achieve a passing grade in both tests. The final grade for the module will be determined collegially and shared among the instructors of the Modular Arithmetic and Linear Algebra components, taking into account the results of the written tests and any additional oral examinations, as well as the overall level of achievement of the knowledge and skills defined by the learning objectives of the course.

The lecture notes and course handouts constitute the main reference material for exam preparation; the textbook is recommended as a support for consolidating understanding of the topics and further exploring the theoretical aspects.

Modular Arithmetic

Integers.
Divisibility and prime numbers.
Greatest common divisor and Euclidean algorithm.
Least common multiple.
Diophantine equations.
Congruences and residue classes.
Divisibility criteria.
Representation of numbers in bases other than base ten.
Chinese Remainder Theorem.
Secret sharing using systems of congruences.
Euler’s theorem.
The discrete logarithm problem.
Diffie–Hellman protocol.
RSA cryptosystem.

Linear Algebra

Matrices, determinants, rank, and inverse matrices.
Vector spaces, bases, and linear dependence.
Linear maps and inner products.
Systems of linear equations.
Gaussian elimination method.
Applications of linear algebra to systems of linear equations.

The expected learning outcomes are consistent with the objectives of the Bachelor’s Degree Programme in Computer Science, as they provide students with the basic mathematical tools necessary to understand, formalize, and address problems of a computational nature. In particular, the skills acquired in elementary number theory and linear algebra constitute a fundamental support for the study of subsequent subjects within the degree programme, such as algorithms, cryptography, cybersecurity, data processing, and other application areas in which these tools are directly employed.

+ Knowledge and understanding:

At the end of the course, students will be able to:

- define and describe the main concepts of elementary number theory, such as divisibility, prime numbers, greatest common divisor, congruences, and residue classes;
- understand the main results and methods of number theory covered in the course, including the Euclidean algorithm, the Chinese Remainder Theorem, and Euler’s theorem;
- describe the fundamental concepts of linear algebra, such as matrices, determinants, rank, systems of linear equations, vector spaces, bases, and linear maps;
- recognize the role of these mathematical tools in the modelling and solution of simple computational problems.

Minimum level of achievement: students know the fundamental definitions, understand the meaning of the main concepts introduced, and are able to use basic mathematical terminology correctly.

Advanced level: students demonstrate a deeper understanding of the mathematical tools studied, are able to establish connections between different concepts, and recognize their role in application contexts related to computer science.

+ Applying knowledge and understanding:

At the end of the course, students will be able to apply the concepts and methods introduced to the solution of basic mathematical and computational problems, in particular:

- apply algorithms and results from elementary number theory to problems involving modular arithmetic and simple cryptographic schemes;
- solve systems of linear equations using matrix-based methods;
- use linear algebra tools to analyse simple mathematical structures and models;
- assess the appropriateness of simple algorithms based on the concepts studied;
- clearly and concisely communicate the procedures followed and the results obtained.

Minimum level of achievement: students are able to apply the main methods presented in the course to standard problems, correctly setting up the solution procedure and interpreting the results obtained.

Advanced level: students are able to independently select the most appropriate tools for solving a problem, critically evaluate simple methods and algorithms, and present complete solutions with adequate mathematical rigour.