Elementary Theory of Numbers I Assignments

MTH 345 (645): Elementary Theory of Numbers I
Dr. Elmer K. Hayashi
Spring 2003
Assignments

Jan 15-17	Jan 20-24	Jan 27-31	Feb 3-7	Feb 10-14
Feb 17-21	Feb 24-28	Mar 3-7	Mar 17-21	Mar 24-28
Mar 31-Apr 4	Apr 7-Apr 11	Apr 14-17	Apr 21-25	Apr 28-30

Textbook: David Burton, Elementary Theory of Numbers, Fifth Edition

Wed, 01/15/2003. Well-Ordering Principle.: Learn the Well-Ordering Principle, and study carefully the proofs on page 2 of the text and the proofs done in class.
Use the Well-Ordering Principle to prove
(1) The square root of 11 is irrational.
(2) There are no positive integers between 0 and 1.

Fri, 01/17/2003. Mathematical Induction.: Study the proofs by induction done in class and on pages 3-6.
On pages 6-7, do problems 1(b), 3, 6. Note that you may ignore the hint given on problem 3, but if you choose to use the hint, then you must also prove the equation given in the hint.

Mon, 01/20/2003. Martin Luther King, Jr. Holiday.: No Class

Wed, 01/22/2003. Binomial Theorem.: Read section 1.2 reviewing the binomial coefficient notation and its properties.
Do all parts of problem 5 on page 12 noting that each part builds on what was shown in the previous parts. Be sure to show that you have verified the hints.

Fri, 01/24/2003. Division Algorithm.: Class canceled because of bad weather.
One application of the division algorithm is to reduce divisibility arguments to the consideration of a finite number of cases.
Study the examples given on page 19 carefully, and then
do problems 3abc on pages 19-20 to check your understanding of what you have read.

Mon, 01/27/2003. Division Algorithm.: The division algorithm is proved using the Well-Ordering of the Nonnegative Integers.
Review section 2.1 and begin reading section 2.2.
Write up problems 4 and 8 on page 20 to turn in next Friday.

Wed, 01/29/2003. Greatest Common Divisor.: The gcd of two integers is the largest positive integer that divides both.
Learn Theorem 2.2 and definition of gcd.
Write up problems 2b and 4bc on page 25 to turn in next Monday.

Fri, 01/31/2003. Characterization of Relatively Prime.: Two integers, not both zero are relatively prime if and only if 1 can be written as a linear combination of the two integers.
Review the definitions and theorems in section 2.2.
On pages 25-26, write up problems 13ab, and 20c to turn in next Wednesday.

Mon, 02/03/2003. Euclidean Algorithm.: The Euclidean Algorithm is a convenient and straight forward way to find the gcd of two integers.
Study pages 26-29.
On page 32, write up problems 2d and 4b to turn in next Friday.
&bsp;
Wed, 02/05/2003. Diophantine Equations.: Diophantine equations can be solved by using the Euclidean algorithm. First look at the reduced fundamental equation where the coefficients are relatively prime and the constant term is 1. Then multiply by the desired constant to obtain the solution of the original equation.
Study example 2.4 on pages 35-36.
Do problems 2b, 6a and 8 on page 38 to check understanding.

Fri, 02/07/2003. Fundamental Theorem of Arithmetic.: Every positive integer is either prime or a product of primes, where the product is unique apart from the order of the factors.
On page 44, look at problems 1, 3a, 7, and 12 to check understanding.

Mon, 02/10/2003. Euclid's Proof.: Euclid's proof that there are infinitely many primes can also be used to get a crude upper bound for the nth prime.

Wed, 02/12/2003. First Hour Exam: The first exam will cover material from chapters 1 and 2, but may also use the definition of prime.

Fri, 02/14/2003. Distribution of Primes.: There are many twin primes, possibly infinitely many, and yet for arbitrary n, there are gaps of at least n consecutive composite numbers.
Finish reading chapter 3.
Write problem 3e and 4 on page 44, and problem 12 on page 51 to turn in next Wednesday. Look at problem 4 on page 59 to get a feeling for Goldbach's Conjecture.

Mon, 02/17/2003. Dirichlet's Theorem: Class canceled by bad weather.
Study the proof of Theorem 3.6 and read the statement of Dirichlet's Theorem (Theorem 3.7) on page 56.
Write up problem 13 on page 60 to turn in on Friday, and look at problem 26abc on page 61 to see some applications of Dirichlet's Theorem.

Wed, 02/19/2003. Congruences.: Working with the Division Algorithm can be simplified using the concept of Congruence. Two integers are congruent modulo n if and only if the difference of the integers is divisible by n if and only if the two integers yield the same remainder (residue) when divided by n.
Learn the definition of congruence and the properties of congruence on pages 64-66.
On pages 68-69, do problems 3, 5, 6a to turn in next Monday.

Fri, 02/21/2003.: Solving a linear congruence is equivalent to solving a Diophantine equation. The criteria for existence of solutions is exactly the same. Finding the solution, when it exists, involves using the cancellation theorem, i.e. finding the inverse of the coefficient of the unknown x (or whatever). If the inverse is not easy to guess, then the Euclidean Algorithm followed by back substitution can be used to find the inverse.
Learn the cancellation theorem, Corollary 1 on page 68, and learn how to use Theorem 4.7 to solve a linear congruence.
On pages 68-69, do 1c and 12a, and on page 82, do 1cd to turn in next Wednesday.

Mon, 02/24/2003. Chinese Remainder Theorem.: The Chinese Remainder Theorem asserts that a system of linear congruences with pairwise relatively prime moduli has a unique solution modulo the product of these relatively prime moduli. The proof of the theorem is constructive in the sense that it spells out exactly how to find the unique solution.
Read the proof of the Chinese Remainder Theorem, and study the examples 4.8 and 4.9 on pages 78-80.
Write up problems 4d and 10 on page 82 to turn in Friday.

Wed, 02/26/2003. Fermat's Factorization Method.: Using the fact that a factorization of a number into two positive integer factors can be used to write the number as the difference of the squares of two integers and vice versa, we have an algorithm to factor an integer that works well when the number has factors that are somewhat close to each other.
Write up 16 on page 69, 8 on page 74, 8 on page 82, and 1ab on page 90 to turn in on Monday.

Fri, 02/28/2003.: Class canceled because of bad weather.

Mon,03/03/2003. Fermat's Little Theorem: Fermat's Little Theorem is one of the most important and useful theorems in elementary number theory.
Learn precisely Fermat's Little Theorem (5.1) and it's corollary on page 92. Note carefully the difference in the hypotheses. Fermat's Little Theorem can be used to detect some integers that are composite, but the existence of pseudoprimes means that this method is not foolproof.
Write up 3, 16a, 17 on pages 96-97 to turn in on Friday.

Wed, 03/05/2003. Wilson's Theorem.: Wilson's Theorem like Fermat's Little Theorem provides a congruence that is satisfied by prime moduli. Unlike Fermat's Little Theorem, the converse of Wilson's Theorem is true thus providing a method to test the primality of an integer. Unfortunately, the method requires so much computation that it is not practical for testing large integers.
Do problem 19 on page 97 and problem 1 on page 101 to check understanding.

Fri, 03/07/2003. Primes of the form 4k+1.: There are infinitely many primes of the form 4k+1.
Look at problems 4, 11 on page 101 to check understanding.

Mon, 03/17/2003. Multiplicative Functions.: If an arithmetic function is multiplicative, it suffices to know the function on powers of primes.
Do problems 7, 8, 23 on page 109 to check understanding.
Write up problems 8 and 23a on page 109 to turn in next Monday.

Wed, 03/19/2003. Mobius Inversion.

Fri, 03/21/2003.: No class.

Mon, 03/24/2003.

Wed, 03/26/2003.

Fri, 03/28/2003.: Hour Exam covering Chapters 3-6.
Topics include the Fundamental Theorem of Arithmetic, primes, congruences, solving linear congruences, the Chinese Remainder Theorem, Fermat's Little Theorem, pseudoprimes, Carmichael numbers, Wilson's Theorem, arithmetic functions, multiplicative arithmetic functions, and Mobius Inversion.

Mon, 03/31/2003. Euler's Phi Function is multiplicative.: Do problem 3 on page 133 to review arithmetic functions.
Write up problems 4cd, 5, 10 on page 133 to turn in on Friday.

Wed, 04/02/2003. Euler's Theorem.: Euler's Theorem generalizes Fermat's Little Theorem to composite moduli with exponent phi(n), since phi(p)=p-1 when p is prime.
Write up problems 1c, 2, 5 on page 138 to turn in on Monday

Fri, 04/04/2003. The order of an integer modulo n.: Do problems 1 on page 161 to check understanding.
Write up problem 2, 4 on page 161 to turn in on Wednesday.

Mon, 04/07/2003. Primitive Roots.: Learn Lagrange's Theorem and its corollary.
Do problem 10 on page 162 to check understanding.
Write up problem 12 on page 162 and problem 4 on page 168 to turn in on Friday.

Wed, 04/09/2003. Primitive Roots and Indices.: Every prime modulus has a primitive root. Learn the definition of the index of an integer relative to a primitive root.
Look at problem 1 on page 177 to check understanding.
Write up problem 6 on page 168 to turn in next Monday.

Fri, 04/11/2003. Properties of Indices.: Indices are used like logarithms to simplify the solving of equations and calculating of residues.
Study examples 8.4 and 8.5 on pages 175-177.
On page 177, do 2c, 3ab, 4 to turn in next Wednesday.

Mon, 04/14/2003. Euler's Criterion.: Euler's Criterion is an important theoretical tool for proving theorems about quadratic residues and non residues.
Write up problem 9 on page 184 and problem 1 on page 194 to turn in next Monday.

Wed, 04/16/2003. Gauss' Lemma.: Gauss' Lemma is a technical theorem that we need to prove the Quadratic Reciprocity Theorem.
Do problem 2 on page 194 to gain an understanding of what Gauss's Lemma asserts.

Fri, 04/18/2003. Good Friday Holiday: No Class

Mon, 04/21/2003. Quadratic Reciprocity Theorem.: The quadratic reciprocity theorem gives us the last property we need to make the Legendre symbol the useful tool that it is for determining the solvability of quadratic congruences.
On page 200-201, do problems 1 and 3 to check understanding.

Wed, 04/23/2003. Review.: The exam on Friday will cover chapters 7-9. Important topics to know include, Fermat's Little Theorem, Wilson's Theorem, Euler's Phi function, Euler's Theorem, the order of an element, Theorems 8.1, 8.2, 8.3, the corollary to Lagrange's Theorem, primitive roots, theory of indices, property of indices, quadratic residues and nonresidues, Euler's criterion, Legendre symbol and its properties, Quadratic Reciprocity.

Fri, 04/25/2003. Hour Exam.

Mon, 04/28/2003. RSA Cryptosystems.
Wed, 04/30/2003.

Saturday, 05/10/2003. Final Examination.: 9:00 a.m.-12:00 p.m.
Location to be announced.

Created 01/02/2003. Last modified 04/21/2003. Email to ekh@wfu.edu