This is 400 level proof course. You are expected not only to understand the materials covered in class but also
- to ponder the contents,
-to grasp the math principles behind,
-to be able to apply the principles to other questions.
In short, you are expected to deepen mathematical maturity.
Mathematical Induction (First principle), two different wordings, and applications; Proof of the identity (1) on p.2.
Factorial, Binomial coefficients, Pascal's Rule, Binomial Theorem
Divisibility and its properties, Common divisors and greatest common divisor, definition.
The #s in the homework list below are from PROBLEMS at the end of each section and are valid in both the 6th ed. and the 7th ed. of Burton's.
Read Sections 1.1 and 1.2.
Read Section 2.3
You are required to follow HW Submission Rule and HW Discussion and Solution Rules from the Course Information and Syllabus 410 Sp25.
In your proofs, you can use any result covered in class, the class handouts, and the relevant sections of the Burton text (but not, for example, a result found in another book). When using such a result in the course of a proof, say so, and cite the specific result used (e.g., “by Theorem 2.2(g) in Burton” or “by Property of the Linear Combinations in Divisibility done in class").
Problems 1.1 #10(a)
Problems 1.2 #3(a)(b)(e), #5(a)
Problems 2.3 #2(c), #3, #4(a), #6(c)
Greatest common divisor, and some of elementary properties
Well-ordering principle, The set of linear combinations of a and b
Prove one of the Elementary Properties of gcd mentioned in class:
gcd(a,b)=gcd(plus/minus a, plus/minus b); see Problem 2.3 #11
Read Section 2.2 Division Algorithm(Statement and its proof that makes use of Well-Ordering Principle.)
None; we didn't cover enough materials. However, do the "Suggested homework" above, which will help homework that will be assigned next week.
Well-Ordering Principle
Two properties of gcd that are deduced from the proof of Lin.comb.&gcd. a&b being relative prime is equivalent to having a integral linear combination ax+by=1. A few useful properties on a&b and their gcd. Euclid Lemma and related lemma
Euclidean Algorithm. Using the Euclidean Algorithm to express gcd(a,b) as a linear combination of a & b.
The least common multiple.
You are required to follow HW Submission Rule and HW Discussion and Solution Rules from the Course Information and Syllabus 410 Sp25.
In your proofs, you can use any result covered in class, the class handouts, and the relevant sections of the Burton text (but not, for example, a result found in another book). When using such a result in the course of a proof, say so, and cite the specific result used (e.g., “by Theorem 2.2(g) in Burton” or “by Property of the Linear Combinations in Divisibility done in class").
Problems 2.3 #12, #13a,b, #19b (optional), #20f, #23
Problems 2.4 #2(b)(c), #4b, #6, #11 (optional).
Supplemental Homework #2, #3
The second proof of "ab/d, where d=gcd(a,b), is equal to lcm(a,b)".
The first proof, done last week, is on our textbook. It makes use of ax+by=d.
The second proof uses one of the divisibility properties (Corollary 2 of Section 2.3). The method used is versatile.
Diophantine equation ax+by=c
Prime and composite numbers, Useful corollaries of Euclid's Lemma for primes,
Fundamental Theorem of Arithmetic - existence and uniqueness (The proof of FTA includes Existence of prime factors of positive integers)
Problems 2.5 #2(a), #4
Problems 3.1 #3(d), #4, #6(b), #11
Canonical prime factorization of a positive integers, FTA variations , gcd, lcm, and their relationship using Fundamental Theorem of Arithmetic,
Irrationality of sqrt(2)
Primality test (Algorithms to find primes), Sieve of Erastothenes -quick discussion, Infinitude of primes and Euclid's proof method
Bounds on P_n in terms of earlier primes and in terms of just n, some elementary bounds on p_n. Bertrand's Conjecture (proved by Tchebycheff) without proof and its application to bounding p_n. (During class, we discussed how to see the main growth of these bounds; Once recognizing such growths, the rigorous proofs can be easily done via Induction; See Thm 3.5 and the paragraphs between Cor. of Thm 3.5 and the beginning of Problems 3.2)
Section 3.2 Read pp.46--47 (7th edition), starting from p^#+1 after Thm3.4 (Euclid) till n_k=n_1n_2...n_{k-1}+1 before the n-th prime p_n starts in the bottom of p.47.
Problems 3.1 #16
Problems 3.2 #3, #7 , #12(c) (Comment: #8 (not required) will help to solve #12(c) )
Gaps between primes: Twin prime conjecture, Arbitrarily long gaps between primes.
Gaps between primes, Arithmetic Progression (AP) and Primes.
Dirichlet's Theorem (no proof), Infinitude of primes of form 4n+3; Two proofs, one as a corollary of Dirichlet's Theorem, and the other as application of Euclid's proof method,
No infinite AP consists solely of primes (An infinite AP must contain infinitely many composite numbers), Arbitrarily long but finite APs of primes; what's known and a necessity condition (Thm 3.8 - its proof is elementary but contains a hidden difficulty as of now; will become easy after learning congruence arithmetic in Ch.4)
A few famous Conjectures on primes: Mersenne primes, Fermat primes, Twin prime conjecture, Goldbach's conjecture.
Congruence relation, Characterization of congruence relation in terms of equal remainders
Supplemental Homework #5, #7
Problems 3.3 #10, #12, #13, #24, #25
Supplemental Homework #4 and #6
Basic properties of congruence relation and their applications, Cancellation laws for congruence relations. Handout: Compare Arithmetic.
Linear congruence ax=b (mod n) and its relation to b being a linear combinations of a and n (this relation has its own importance!), Existence and the number of solutions of a linear congruence,
Multiplicative inverse (MI). Discussion of 'versatile strategy' to solve a linear congruence (a) utilizing multiplicative inverse plus (b) algebraic manipulations to transform a given linear congruence to a MI-applicable linear congruence.
Chinese Remainder Theorem (CRT) and the formula for unique solution for system of linear congruences,
(i) System of simultaneous linear congruences and how to transform it into the standard CRT- applicable form.
(ii) One linear congruence with possibly large composite modulo number and how to transform it into a system of simultaneous linear congruences into (i).
(i) and (ii) are part of CRT applications, hence place the item here FYI. But we couldn't get to it and will do next week.
Problems 4.2 #3,
Problems 4.2 One of #10 or #12(a) (read the definition of "a complete set of residues mod n" in the paragraph above Theorem 4.1 in Section 4.2 - middle on p.64 of the 7th ed.),
Problems 4.2 #13, #15
Chinese Remainder Theorem (CRT) and the formula for unique solution for system of linear congruences,
(i) System of simultaneous linear congruences and how to transform it into the standard CRT- applicable form.
(ii) One linear congruence with possibly large composite modulo number and how to transform it into a system of simultaneous linear congruences into (i).
Complete set of residues modulo n (or, complete residue system modulo n), Least non-negative residue of an integer a modulo n; definitions and concepts,
Fermat's little theorem (FLT) and its Extended version (two different proofs for the extended version). Example to apply FLT, Example to show that FLT fails for a composite number.
Fermat's Theorem Prime vs. Composite, Pseudoprime, Carmichael Number (I will probably revisit this topic after Spring break)
The list is quite long. So, 5.2 #2 is turned into optional but I recommend you try them as warm-up. 5.2 #15(a), #18(a) will be due 4/2, a week after 3/26.
Problems 4.4 #6, #11, #18
Problems 5.2 are categorized into three parts for your convenience.
Problems 5.2 #11, #21 (n=p a prime as in Fermat's Theorem)
Problems 5.2 #2 (Optional, no need to submit), #5, #13 (n is a composite)
Hint: Use the commonly used principle "X=Y (mod m), X=Y (mod n) and m&n are relatively prime iff X=Y (mod mn)", as seen before, such as
Example 4.6 as an application of CRT in Section 4.4
Showing n=561 is a Carmichael Number in Section 5.2
Problems 5.2 #15(a), #18(a) (Pseudoprimes and Carmichael numbers) These questions will be due 4/2. Let me list here for those who would like to try over Spring break.
Fermat's Theorem Prime vs. Composite, Psudoprimes, Carmichael's Number
Wilson's theorem, Converse to Wilson's Theorem, Examples to apply Wilson's Theorem.
Wilson's Theorem and its Converse, Fermat's Theorem and its Converse
Application of Wilson's Theorem to solving certain quadratic congruences
Reduced residue system; Definition and its property that is closed under multiplications
6.1 Number-theoretic Functions (a.k.a. Arithmetic Functions)
Problems 5.2 #15(a), #18(a) (Pseudoprimes and Carmichael numbers)
Problems 5.3 #5(a), #18 (<-- These problems are direct applications of only the results of Wilson's Thm)
Problems 5.3 #10, #12 (<-- These problems need your understanding of the proof techniques appeared in Wilson's Thm or Quadratic congruences)
A good mix of the techniques from Chapter 3 and Theorem 5.5.
Hint: As done in Chapter 3, assume, for a contradiction, that only a finite number of primes of the form 4k+1 exist, then construct an integer N utilizing the assumption. A clever setting N will enable to apply Theorem 5.5.
6.0 Preparatory discussions on Sums and Products and their Combinatorial interpretations.
Ch6 & Ch 7 Arithmetic Functions (AF) - aka Number-Theoretic Functions in our textbook: Introduction
three basic AFs: 1(n), id(n). delta(n)
four AFs that we will study in details: tau(n), sigma(n), Euler phi(n), Moebius mu(n),
Not exactlyan AF but behaves like one: greatest integer function
6.1 tau(n), sigma(n) when n=p or p^k
6.1 Explicit formulas for tau(n), sigma(n) with the first proof via direct counting
6.1 Useful lemma: Positive divisors of a product of relatively prime integers (p.108, the 6th & 7th ed.)
6.1 Multiplicative and Completely multiplicative AFs
6.1 Summations of a multiplicative arithmetic functions over divisors, and its multiplicativity
6.1 The multiplicativies of tau(n) and sigma(n) using Summations of a multiplicative arithmetic functions over divisors
6.1 Explicit formulas for tau(n), sigma(n) with the second proof using the multiplicativies of tau(n) and sigma(n);
Notice that two different proofs for the formulas. Both proofs have aspects to learn.
Problems 6.1 #7,#8, #16, #20, #22, #23(Additional Hint for #23: if f_1 and f_2 are multiplicative AFs, then the product f_1f_2 is also multiplicative. )
6.1 Useful lemma: Product over positive divisors; While d runs through the positive divisors of n exactly once, so does n/d.
7.2-7.3 Reminder: to be used in 7.2 and 7.3. Also good exercises for the upcoming exam
The complete set of residues mod n and its permutation by multiplying an integer that is relatively prime to n.
The reduced set of residues mod n (i.e. The subset of the complete set of residues mod n whose elements are relatively prime to n) and its permutation by multiplying an integer that is relatively prime to n. On the exams, I always give a full description of the set in order to avoid any confusion
7.2 Euler's phi(n) when n=p or p^k
7.2 The multiplicativity of Euler phi(n) with proof by double counting
7.2 Explicit formulas for phi(n) using the multiplicativity of phi
7.3 Proof of Euler's theorem as a generalization of the proof of Fermat's Little theorem,
7.3 Three examples to apply Euler's theorem
You are allowed to use these formulas in your calculations; however, as seen in an example from class, sometimes it gives the result quickly, but sometimes you still need to go back to Fermat's Theorem followed by "Relatively Prime Divisors/Relatively Prime Modulos". It all depends on the exponent and the phi-value of n.
You will find most of the 7.2, 7.3 (and 7.4 Part 1 next week) contents in this Lecture Note 7.2-7.3-7.4Part1 Arithmetic Euler phi. It is a scan of my lecture note written on a paper for myself, hence a bit messy. Yet, most of the parts are written decent and let me share with you in case it helps some of you.
Problems 7.2 #4(e), #10, #13
Problems 7.3 #4, #10
7.2 phi(n) is always even for n>2, followed by a brief introduction to Carmichael's conjecture
7.4 Part 1: Guass identity (n=summation of phi over divisors of n). Two proofs have been presented & compared: (i) using the multiplicativity of the and (ii) via direct counting
6.2 The multiplicativity of Moebius mu(n) with (an easy) proof, Compared with Louville lambda(n).
6.2 Summation of mu over divisors of n
6.2 Detailed discussion of exchanges of double sums; To be used in the Moebius Inversion Formula. This combinatorial aspect makes the topic look difficult that it is.
6.2 Moebius Inversion Formula; The Burton's book introduces only one direction in Thm 6.7. Its converse indeed holds but its proof is slightly more difficult (but not so much) because the exchange of double sums involved is slightly more difficult.
6.2 Converse of Moebius Inversion Formula without proof but the relevant double-sum was discussed.
6.2 & 7.4 Part 2. Non-trivial identities of AFs, including Mobius Inversion for Euler phi (Thm 7.8), via Moebius Inversion Formula.
6.2 Converse of the construction of multiplicative function F (f is multiplicative iff F is multiplicative)
We have started Section 8.1 but I will add the contents on Week 14.
You will find most of the 6.2 & 7.4 Part2 contents in this Lecture Note 6.2 7.4 Part 2 Arithmetic Moebius mu. It is a scan of my lecture note written on a paper for myself, hence a bit messy. Yet, most of the parts are written decent and let me share with you in case it helps some of you.
8.1 Order of a modulo n,
When does order of a modulo n exist and when does it not exist.
Properties of order - elementary properties, divisibility condition on the exponents, i congruent to j modulo order of a iff a^i congruent to a^j modulo n, order of power of a in terms of order of a,
8.1 Primitive root of n, Characterization of positive integers relatively prime to n in terms of the powers of a primitive root of n, The number of primitive roots of n, how to find all primitive roots of n given one primitive root,
8.2 Lagrange's theorem for the number of solutions of a polynomial congruence, Exact number of solutions for functional congruence with f(x) = x^d - 1 modulo p.
8.2 The number of incongruent integers of order d modulo p, number of primitive roots of p,
8.2 Discussion of: Smallest primitive root of a prime,
The last homework set. It is on several sections and long, hence some questions have been converted to 'optional', meaning NOT required to submit though I recommend you attempt them.
Problems 7.4 #11 (The "proof" in the question refer to the combinatorial proof done in our class (I did two proofs in class))
7.4 Part 1 Supplemental Homework #8 (optional)
Problems 6.2 #4(b)(c) (Do #4 without using Problem 3; however, #3 could be a hint), #7, #8(b)(See the definition of the AF w(n) in #5)
Problems 6.2 #6(optional)
Problems 6.2 #2 (Moebius Inversion needed)
Problems 7.4 #4 (Moebius Inversion needed)
Problems 8.1 Choose TWO among these four: #3, #4, #5, #11(b); from the 7th ed. Exercises 8.1 has different numbering in the 6th ed.