Number Theory

At the end of this course, the students should be able to:

• Understand the logic and methods behind the major proofs in Number Theory;

• construct mathematical proofs of statements and find counterexamples to false statements in number theory;

• collect and use numerical data to form conjectures about the integers;

• prove results involving divisibility and greatest common divisors;

• solve systems of linear congruences;

• find integral solutions to specified linear Diophantine equations;

• Apply Euler-Fermat's Theorem to prove relations involving prime numbers and integers;

• apply Wilson's theorem; and,

• demonstrate knowledge of the Legendre symbol and quadratic reciprocity law.

1. Preliminaries

• The number system

• Some important notations*

• The principle of mathematical induction and the pigeonhole principle

• Divisibility and the division algorithm

• Representation of integers*

• GCDs, LCMs, and the Euclidean algorithm

2. Primes

• Prime numbers

• The fundamental theorem of arithmetic

• Primality testing and factorization

• Linear Diophantine equations

3. Congruences, Roots, and Indices

• Modular arithmetic and congruence

• Linear congruences

• The Chinese remainder theorem

• Systems of linear congruences

• Wilson's theorem and Fermat's little theorem

• Euler's theorem

• Primitive roots and indices

• Computing powers and roots

4. Quadratic Reciprocity and Other Topics

• Quadratic congruences

• Quadratic residues and nonresidues

• Reciprocity laws

• Arithmetic functions

• Pythagorean triples

• Fermat's last theorem

5. Cryptology

• Introduction to cryptology and affine ciphers

• Block ciphers

• RSA and public key cryptography

Abstract Algebra is a prerequisite of this course. Results obtained from the structure of modular groups and fields are applied in the topics covered here. Basic arithmetic, elementary algebra, and sometimes linear algebra might also be useful in this course.

Technology will be used extensively for the whole semester. Hence, the availability of electronic devices (such as smartphones or laptops) and internet connectivity will be advantageous.

• 27 Lecture Exercises

• 9 Quizzes

• 4 Major Examinations

• 2 Projects

Cut-off score is 50% for all course requirements.

Answers to lecture exercises and quizzes shall be written in sheets of 1/4 of short-sized bond paper. Take a photo of each page and send them as attachment to my e-mail address julius.selle@ctu.edu.ph or jdselle@up.edu.ph with subject properly indicating which course requirement is being submitted (for example "Math-C 228 Quiz No. 1"). Then, in the body of the mail, write your full name, course, year, and block section (I encourage you to do this in formal and complete sentences). The reason why it is required to write in 1/4 sheets is to enhance visibility. (Photos of whole-sized paper are sometimes difficult to read). You are allowed to use as many 1/4 sheets as you would need.

• Rosen, K.H. (2011). Elementary number theory [6th Ed.]. Pearson

• Burton, D.M. (2011). Elementary number theory [7th Ed.]. McGraw-Hill

• Hardy, G.H., et al. (2008). An introduction to the theory of numbers [6th Ed.]. Oxford University Press

• Baldoni, Ciliberto & Cattaneo (2009). Elementary number theory, cryptography, and codes. Springer