7.30. Numbers theory (Mandatory)

7.30. Numbers theory (Mandatory)

Figure 7.30: Connection Map. MA281 Numbers theory

7.30.1. Justification ↑ Back to top

Number Theory is a fundamental branch of pure mathematics that studies the properties of integers, serving as the foundation for numerous applications in computational mathematics, cryptography, and information theory. This course equips students with the theoretical and algorithmic tools to analyze problems of divisibility, primality, congruences, and Diophantine equations, developing rigorous logical-abstract thinking. The computational focus allows for the implementation and validation of theoretical concepts, laying the groundwork for areas such as public-key cryptography and factorization algorithms.

7.30.2. Generales Goals ↑ Back to top

  1. Understand and apply the fundamental principles of divisibility, the Euclidean algorithm, and the fundamental theorem of arithmetic.
  2. Analyze and solve problems involving linear congruences and systems of congruences using the Chinese Remainder Theorem.
  3. Study basic arithmetic functions and their applications in the distribution of prime numbers.
  4. Introduce the concepts of quadratic residues and the law of quadratic reciprocity, understanding their theoretical importance.
  5. Implement basic numerical algorithms (Euclid's algorithm, primality testing, modular exponentiation) to validate theoretical concepts.

7.30.3. Contribution to Outcomes ↑ Back to top

ABET-1) An ability to identify, formulate, and solve broadly defined technical or scientific problems by applying knowledge of mathematics and science and/or technical topics to areas relevant to the discipline. (Usage)

7.30.4. Content ↑ Back to top

7.30.4.1. Divisibility and Congruences (16 hours) [Skills ABET-1] ↑ Back to top

Bibliography: (Rosen, 2011; Apostol, 1976)

Topics

  1. Axioms of the integers: Well-Ordering Principle and Mathematical Induction.
  2. Divisibility: Division Algorithm, Greatest Common Divisor (Extended Euclidean Algorithm) and Bézout's Lemma.
  3. Prime and composite numbers. Fundamental Theorem of Arithmetic. Infinitude of primes.
  4. Congruences: definition, algebraic properties, and residue classes modulo \( n \).
  5. Computational applications: implementation of the Euclidean algorithm and basic primality tests.

Learning Outcomes

  1. Understand the fundamental axioms of the integers and the proof technique of induction [Familiarity].
  2. Use the extended Euclidean algorithm to compute the greatest common divisor and the Bézout identity [Usage].
  3. Prove basic properties of prime numbers and congruences, applying them to elementary problems [Assessment].
7.30.4.2. Diophantine Equations and the Chinese Remainder Theorem (16 hours) [Skills ABET-1] ↑ Back to top

Bibliography: (Rosen, 2011; Burton, 2011)

Topics

  1. Linear Diophantine equations: conditions for solvability and general solution method.
  2. Chinese Remainder Theorem for systems of linear congruences with coprime moduli.
  3. Modular arithmetic: the ring \( Z_n \), units, and zero divisors.
  4. Fermat's and Euler's Theorems. Euler's totient function \( \) and its properties.
  5. Applications in basic cryptography: Caesar cipher and foundations of RSA.

Learning Outcomes

  1. Identify the conditions for the existence of solutions to linear Diophantine equations [Familiarity].
  2. Apply the Chinese Remainder Theorem to solve systems of congruences and calendar problems [Usage].
  3. Use Fermat's and Euler's theorems to simplify modular exponentiation calculations and analyze basic algebraic structures [Assessment].
7.30.4.3. Arithmetic Functions and Multiplicative Number Theory (16 hours) [Skills ABET-1] ↑ Back to top

Bibliography: (Apostol, 1976; Nathanson, 2000)

Topics

  1. Arithmetic functions: Definition and examples (tau, sigma, phi, mu).
  2. Dirichlet convolution and the Möbius inversion formula.
  3. Perfect, amicable, and abundant numbers. Open conjectures.
  4. Orders and primitive roots modulo a prime.
  5. Discrete logarithms: definition and applications in key exchange protocols (Diffie-Hellman).

Learning Outcomes

  1. Recognize the properties of the most important arithmetic functions [Familiarity].
  2. Apply Möbius inversion to solve counting problems in number theory [Usage].
  3. Compute orders and primitive roots, relating them to the cyclic structure of \( Z_p^* \) [Assessment].
7.30.4.4. Quadratic Residues and Computational Applications (16 hours) [Skills ABET-1] ↑ Back to top

Bibliography: (Rosen, 2011; Hoffstein et al., 2008)

Topics

  1. Quadratic residues and non-residues. Legendre symbol and its properties.
  2. Law of Quadratic Reciprocity. Proof and applications in computing the Legendre symbol.
  3. Jacobi symbol and its use in probabilistic primality tests.
  4. Introduction to primality testing: Miller-Rabin test.
  5. Integer factorization: Pollard's \( p-1 \) method and notions of the RSA algorithm.

Learning Outcomes

  1. Determine whether a number is a quadratic residue modulo a prime using the Legendre symbol [Familiarity].
  2. Apply the Law of Quadratic Reciprocity to compute Legendre and Jacobi symbols efficiently [Usage].
  3. Implement basic primality testing and factorization algorithms, analyzing their complexity and limitations [Assessment].

7.30.5. Bibliography ↑ Back to top

Rosen, K. H. (2011). Elementary Number Theory and Its Applications. Pearson, 6th edition. Texto ampliamente utilizado, con un balance excelente entre teoría, ejemplos y aplicaciones computacionales.

Apostol, T. M. (1976). Introduction to Analytic Number Theory. Springer-Verlag, 1st edition. Texto clásico y riguroso para el estudio de funciones aritméticas y teoría analítica de números.

Burton, D. M. (2011). Elementary Number Theory. McGraw-Hill Education, 7th edition. Libro introductorio muy didáctico, con abundantes ejemplos y ejercicios.

Nathanson, M. B. (2000). Elementary Methods in Number Theory, volume 195 of Graduate Texts in Mathematics. Springer. Enfoque en métodos combinatorios y aditivos, con demostraciones elegantes.

Hoffstein, J., Pipher, J., and Silverman, J. H. (2008). An Introduction to Mathematical Cryptography. Springer, 1st edition. Excelente puente entre la teoría de números y la criptografía aplicada.

Spotted a typo, an outdated course, a broken link, or have a suggestion? Let us know.

Scan to open on your phone