MA 335 - Intro to Number Theory
This is an introductory course to number theory. Topics include divisibility, prime numbers and modular arithmetic, arithmetic functions, the sum of divisors and the number of divisors, rational approximation, linear Diophantine equations, congruences, the Chinese Remainder Theorem, quadratic residues, and continued fractions.
Prerequisites: MA 232
The purpose of the course is to give a simple account of classical number theory, prepare students to graduate-level courses in number theory and algebra, and to demonstrate applications of number theory (such as public-key cryptography). Upon completion of the course, students will have a working knowledge of the fundamental definitions and theorems of elementary number theory, be able to work with congruences, solve congruence equations and systems of equations with one and more variables, and be literate in the language and notation of number theory.
- Divisibility. Understand the concept and properties of divisibility. Know the definitions and properties of gcd and lcm.
- Euclid algorithm and Bezout's identity. Be able to compute the greatest common divisor and least common multpiples.
- Linear Diophantine equations. Describe the set of all solutions to linear Diophantine equations.
- Primes, distribution of primes, and prime power factorization. Determine if a number is prime. Compute the prime power factorization of a number.
- Modular arithmetic, congruences. Understand the concept of a congruence. Be able to perform basic operations with congruences (addition, multiplication, subtraction).
- Linear congruences, systems of linear congruences, and Chinese remainder theorem (CRT). Compute the set of all solutions to linear congruence. Be able to apply CRT and reduce general systems of linear congruences to systems studied by CRT.
- Simultaneous non-linear congruences. Describe the set of solutions of non-linear congruence equations (with relatively small moduli) and be able to solve systems of such equations.
- The arithmetic of Zp. Student’s must understand and be able to use the founding theorems: Lagrange theorem, Fermat's little theorem, Wilson's theorem.
- Primality-testing, pseudoprimes, and Carmichael numbers. Understand the concept of a pseudoprime and be able to determine if a number is pseudoprime or Carmichael.
- Units. Euler's function phi. Understand the definition of a unit, know characterization of units, be able to compute a group of units directly. Compute Euler’s function phi, be able to use a formula for phi to study relations between numbers n and phi(n). Understand Euler's generalization of Fermat's little theorem.
- The group of units Un. Understand the concepts of the order of an element, primitive root, generating set for a group, Cayley graph for a group. Be able to determine if a group Un has a primitive root and find it. Be able to find a generating set for Un and draw the Cayley graph relative to the chosen set.
- The group of quadratic residues Qn. Construct the group Qn directly. Determine the size of Qn. Compute Legendre symbol, know the properties of Legendre symbol. Know and be able to use the law of quadratic reciprocity.
- Arithmetic functions. Mobius inversion formula and its properties.
- RSA cryptography. Understand the basics of RSA security and be able to break the simplest instances.
Jones, G. and M. Jones, Elementary Number Theory, Springer.
Burton, D., Elementary Number Theory, McGraw-Hill.