ALGORITHMIC NUMBER THEORY

MA526

Course Description

         

This course presents number theory from an historical point of view and emphasizes significant discoveries from ancient to modern times, as well as presenting unsolved problems and areas of current interest.  Topics include: prime numbers and related theorems; Euclidean algorithm and quadratic reciprocity; Pythagorean numbers and continued fractions.

 

Goals of the Course

 

1.     To develop the mathematical skills to solve number theory problems and to develop the mathematical skills of divisions, congruences, and number functions.

2.     To introduce the art of constructing proofs.

3.     To learn the history of number theory and its solved and unsolved problems.

4.     To investigate applications of number theory and the use of computers in number theory.

 

Instructional Procedures

 

a.      Lecture/Discussion

b.     Homework problems from text

 

Course Content

 

A.   Divisibility

1.     Greatest Common Factor and Least Common Multiple

2.     Division Algorithm

3.     Euclidean Algorithm

4.     Linear Combinations

5.     Congruences

6.     Mathematical Induction

B.  Prime Numbers

1.     Prime Factorization

2.     Factorization in other systems

3.     Fundamental Theorem of Arithmetic

4.     Prime Power Factorization

5.     Set of Primes is Infinite

6.     A Formula for d(n)

C.   Numerical Functions

1.     Sum of the Divisors

2.     Multiplicative Functions

3.     Perfect Numbers

4.     Mersenne and Fermat Number

5.     Euler Phi Functions

6.     Mobius Inversion Formula

D.   Algebra of Congruences Classes

1.     Solving Linear Congruences

2.     Chinese Remainder Theorem

3.     More than Two Congruences

4.     Theorems of Fermat and Euler

5.     Public Key Cryptography

E.  Congruences of Higher Degree

1.     Polynomial Congruences

2.     Congruences with Prime Power Moduli

3.     Quadratic Residues

4.     Quadratic Reciprocity

 

Evaluation Measures

a.      Hourly Exams

b.     Homework

c.     Final Exam

d.     Project

 

Bibliography

 

A.  Required Texts

Vanden Eynden, Charles, Elementary Number Theory, Random House, N.Y.  1987

 

B.  Supporting Bibliography

Grosswald, Emil, Topics from the Theory of Numbers, Random House, 1986

Niven, Ivan and Zuckerman, Herbert, An Introduction to the Theory of Numbers, 4th Ed, John Wiley & Sons, 1980

Rosen, Kenneth, Elementary Number Theory & Its Applications, 3rdEd, Addison Wesley, Reading, Mass. 1993

Spencer, Donald D, Computers in Number Theory, Rockville, Md., Computer Science Press, 1982

Strayer, James, Elemntary Number Theory, PWS Pub. Co., 1994

Weil, Andre, Number Theory, Random House, N.Y.  1986