Colorado State University, Pueblo; Spring 2015
Math 319 — Number Theory
Course Schedule & Homework Assignments

Here is a link back to the course syllabus/policy page.

This schedule is will be changing very frequently, please check it at least every class day, and before starting work on any assignment (in case the content of the assignment has changed).

Unless otherwise specified, all reading assignments, sections, and page numbers below refer to the course textbook, Yet Another Introductory Number Theory Textbook, v2.0, by Poritz, available here.

If you see the symbol below, it means that class was videoed and you can get a link by e-mailing me. Note that if you know ahead of time that you will miss a class, you should tell me and I will be sure to video that day for you.

• M:
  • bureaucracy and introductions; particularly:
    • no paper textbook
    • different written parts of the course
    • keep an eye on the homework page
    • revision of written work
    • what would make a good T&Q
    • well, it's really all in the syllabus
  • Content:
    1. terms we defined
       • natural number, set of which being denoted $\NN$.
       • integer, set of which being denoted $\ZZ$.
       • rational number, set of which being denoted $\QQ$.
         • this is actually a subtle set, hence students' problems with fractions!
    2. gave a fairly complete, albeit somewhat informal, proof that $\sqrt{2}$ is not rational
    3. some notation:
       • $x\in S$ means $x$ is an element of the set $S$.
       • $\forall$ should be read "for all"
       • $\exists$ should be read "there exists"
       • We write $A\subset B$ if $A$ is a subset of $B$.
       • s.t. stands for "such that"
  • As soon as possible, please do HW0: Send me e-mail (to jonathan.poritz@gmail.com) telling me:
    1. Your name.
    2. Your e-mail address. (Please give me one that you actually check fairly frequently, since I may use it to contact you during the term.)
    3. Your year/program/major at CSUP.
    4. The reason you are taking this course.
    5. What you intend to do after CSUP, in so far as you have an idea.
    6. Past math classes you've had.
    7. Other math and science classes you are taking this term, and others you intend to take in coming terms.
    8. Your favorite mathematical subject.
    9. Your favorite mathematical result/theorem/technique/example/problem.
    10. Anything else you think I should know (disabilities, employment or other things that take a lot of time, etc.)
    11. [Optional:] The best book you have read recently.
• W:
  • Miniquiz 0 handed out
  • Read [before class, as always!]: §1.1 of YAINTT
  • Submit T&Q1 on today's reading [at least an hour before class, as always!]
  • Content:
    1. some more basic sets of numbers
       1. point of view of needing new sets of numbers in order to solve more and more complicated equations.
       2. real numbers, set of which being denoted $\RR$.
          • this is also a subtle set...
       3. irrational numbers
       4. complex numbers
    2. some more basic mathematical notation:
       1. $P\Rightarrow Q$, read as "$P$ implies $Q$" or "If $P$, then $Q$."
       2. $P\Leftrightarrow Q$, read as "$P$ if and only $Q$"
       3. "iff", read as "if and only if"
    3. Starting example: Pythagoras...
       • The Pythagorean Theorem, Euclid's proof
       • irrational examples of possible side lengths for a right triangle -- e.g., use what we've proven about $\sqrt{2}$
       • rational solution would give integer solution by clearing all the denominators
       • a single solution gives many others by multiplying all side lengths by the same number; if the first solution was integral, we can use this to get an infinite number of new integral solutions by multiplying by an integral scale factor
       • $\{3, 4, 5\}$ is an integral solution!
       • define Pythagorean triple and primitive Pythagorean triple [PPT]
    4. starting to analyze PPTs: first, we saw that a PPT $(a,b,c)$ cannot have all numbers being even (violates primitivity), nor even just $a$ and $b$ being even (because then $c$ would be as well, so they would all be even). started looking at the case of $a$ and $b$ being odd.
  • Miniquiz 1
• F:
  • Read: §1.2 of YAINTT
  • Submit T&Q2 on today's reading
  • Hand in HW1: 1.1.1 and either 1.1.2 or 1.1.3 in §1.1 of YAINTT
  • Content:
    1. a method to generate infinitely many (but not all!) PPTs
  • Maxiquiz 1
  • Today [Friday] is the last day to add classes.

• M:
  • Read: §1.3 of YAINTT
  • Submit T&Q3 on today's reading
  • Content:
    1. Euclid's approach to PPTs.
  • Miniquiz 2
• W:
  • Read: §1.4 of YAINTT
  • Submit T&Q4 on today's reading
  • Content:
    1. Additional problems: triangular numbers, and a first hit of the addictive drug which is the study of the primes
  • Miniquiz 3
• F:
  • Read: §2.1 of YAINTT
  • Submit T&Q5 on today's reading
  • Content:
    1. Induction
  • Hand in HW2: one problem from each of the sections §1.2, §1.3, and §1.4, all in YAINTT
  • Maxiquiz 2

• M:
  • Read: §2.2 of YAINTT
  • Submit T&Q6 on today's reading
  • Content:
    1. Going over Maxiquiz 2
    2. Going over HW2
    3. Counting presents in a famous holiday song
    4. More on Induction:
       1. The alternate form of the inductive step
       2. Common sources of error in inductive proofs, e.g., proof that All pigs are yellow.
    5. Mention of basic arithmetic rules in $\NN$: know the terms Commutativity, Associativity, Distributivity, additive inverse, and multiplicative inverse
  • Miniquiz 4
  • Today [Monday] is the last day to drop classes without a grade being recorded.
• W:
  • Read: §2.3.1 of YAINTT
  • Submit T&Q7 on today's reading
  • Content:
    1. divisor, factor, multiple, and the notations $a\mid b$ and $a\nmid b$
    2. even and odd
    3. divisibility of linear combinations
  • Miniquiz 5
• F:
  • Read: §2.3.2 of YAINTT
  • Submit T&Q8 on today's reading
  • Content:
    1. The Division Algorithm: statement, proof, examples.
    2. some applications, such as a few of the exercises from §2.3 of YAINTT
  • Hand in HW3: 2.1.7, 2.3.4, and 2.3.11
  • Maxiquiz 3

• M:
  • Read: §2.4 of YAINTT
  • Submit T&Q9 on today's reading
  • Content:
    1. numbers in different bases
  • Miniquiz 6
• W:
  • Read: §2.5 of YAINTT
  • Submit T&Q10 on today's reading
  • Content:
    1. the greatest common divisor, $\gcd(a,b)$
  • no miniquiz today, but you should be able to define and explain the base-$b$ expansion of a number!
• F:
  • Read: §2.6 of YAINTT
  • Submit T&Q11 on today's reading
  • Content:
    1. The Euclidean Algorithm Here is an on-line implementation.
  • Hand in HW4: 2.3.10, 2.4.{1,5}, and 2.5.5
  • Maxiquiz 4

• M:
  • Read: §3.1 of YAINTT
  • Submit T&Q12 on today's reading
  • Content:
    1. congruences: definition, basic properties and examples
  • Miniquiz 7
• W:
  • Reread: §3.1 of YAINTT
  • Submit T&Q13 on today's reading
  • Content:
    1. more basics of congruences
  • Miniquiz 8
• F:
  • Read: §3.2 of YAINTT
  • Submit T&Q14 on today's reading
  • Content:
    1. linear congruences [i.e., linear congruence equations]
  • Hand in HW5: 3.1.{1,3,4,5}
  • Maxiquiz 5

• M:
  • Reread: §3.2 of YAINTT
  • Submit T&Q15 on today's reading
  • Content:
    1. more on linear congruences
    2. multiplicative inverses mod $n$
  • Miniquiz 9
• W:
  • Read: §3.3 of YAINTT
  • Submit T&Q16 on today's reading
  • Content:
    1. The Chinese Remainder Theorem
  • Miniquiz 10
• F:
  • Read: §3.4 of YAINTT
  • Submit T&Q17 on today's reading
  • Content:
    1. equivalence relations/classes
  • Hand in HW6: 3.2.{2, 3, 4}, 3.3.{1, 4}
  • Maxiquiz 6

• M:
  • SNOW EMERGENCY: NO CLASS!
• W:
  • Read: §3.5 of YAINTT
  • Submit T&Q18 on today's reading
  • Miniquiz 11
  • Content:
    1. Euler's $\phi$ function
• F:
  • Reread: §3.5 of YAINTT
  • Submit T&Q19 on today's reading
  • Maxiquiz 7
  • Hand in HW7: 3.4.{1, 4}, 3.5.{1, 2}
  • Review for test I; see this review sheet

• M:
  • Test I in class
• W:
  • Test I post-mortem.
  • Note: good definition style and content is very important! Here is a handout from a class a little while ago which discusses some important issues in this area.
• F:
  • No maxi- or miniquiz today.
  • Hand in Test I revisions, if you so choose. For these, hand in the original exam sheet, unchanged, and new pages with your new solutions. Note that there is a much higher expectation of completeness and good mathematical style in these revisions, since they are prepared by you without time pressure.
  • Content:
    1. We will be discussing §4.1 of YAINTT in class -- but (this time only!) you do not need to read it ahead of time nor do you need to submit a T&Q on it.
    2. (more) basics about primes
    3. a Euclid's Lemma-type result where the divisor is prime
    4. the (justifiably famous) Fundamental Theorem of Arithmetic

• M:
  • Read: §4.2 of YAINTT
  • Submit T&Q20 on today's reading
  • Miniquiz 12
  • Content:
    1. the uniqueness part of the Fundamental Theorem of Arithmetic
    2. Wilson's Theorem -- an odd condition for primality with a fun proof.
• W:
  • Read: §4.3 of YAINTT
  • Submit T&Q21 on today's reading
  • Miniquiz 13
  • Content:
    1. the definition of multiplicative order
    2. an analogue of Lagrange's Theorem in the current context
• F:
  • Reread: §4.3 of YAINTT
  • Submit T&Q22 on today's reading
  • Maxiquiz 8
  • Content:
    1. Euler's Theorem
    2. Fermat's Little Theorem
  • Hand in HW8: 4.1.{2, 3}, 4.3.{2 & (3 or 4)}
  • Today [Friday] is the last day to withdraw (with a W) from classes

• M:
  • Read: §5.1 of YAINTT
  • Submit T&Q23 on today's reading
  • Miniquiz 14
  • Content:
    1. basic history, ideas, and terminology of cryptology
• W:
  • Read: §5.2 of YAINTT
  • Submit T&Q24 on today's reading
  • Miniquiz 15
  • Content:
    1. Caesar and Vigenère cryptosystems
    2. one-time pads
• F:
  • Reread: §5.3 of YAINTT
  • Submit T&Q25 on today's reading
  • Maxiquiz 9
  • Content:
    1. cryptanalysis by frequency analysis
  • Hand in HW9: 5.1.3 5.2.3; this is quite a small homework set ... why don't you take this moment to do a revision of a previous assignment, such as an old homework set (or even just problem) or maxiquiz, on which you could do a better job now (and on which you lost a significant number of points)?

• M:
  • Read: §5.4, only up to Definition 5.4.4 on p. 99 of YAINTT
  • Submit T&Q26 on today's reading
  • No miniquiz today.
  • Content:
    1. going over some recent homeworks and quizzes
    2. symmetric and asymmetric cryptosystems — also known as private key and public key cryptosystems
• W:
  • Read: the rest of §5.4 of YAINTT
  • Submit T&Q27 on today's reading
  • Miniquiz 16
  • Content:
    1. the RSA public key cryptosystem
    2. [cryptographic] salt
• F:
  • NOTE: today only, class will meet 4-5pm instead of our usual time, but in our usual classroom.
  • Read: §5.5 of YAINTT
  • Submit T&Q28 on today's reading
  • Maxiquiz 10 will be handed out today; it is due on Monday. [If you are unable to be in class, send me an e-mail after the class time and I will reply with the quiz.]
  • Hand in HW10: 5.3.{1, 3} 5.4.4
  • Content:
    1. digital signatures

• M:
  • Read: §5.6 of YAINTT
  • Submit T&Q29 on today's reading
  • Hand in Maxiquiz 10.
  • Content:
    1. man-in-the-middle attacks
    2. certificates and certificate authorities
• W:
  • Review for test II; see this review sheet
  • Hand in HW11: 5.5.3, 5.6.1
• F:
  • Test II, in class part.

• M:
  • Hand in the take-home part of Test II at the beginning of class — it will not be accepted later!
  • Test II post-mortem.
  • No miniquiz or T&Q today.
• W:
  • Read: Chapter 6 Intro and §6.1 of YAINTT
  • Content:
    1. Recall from before, working inside $(\ZZ/n\ZZ)^*$ for some $n\in\NN$: [multiplicative] order and cyclic subgroup $\left<a\right>$ for $a\in(\ZZ/n\ZZ)^*$.
  • No miniquiz or T&Q today.
  • Hand in Test II revisions, if you so choose. Remember, for these, hand in the original exam sheet, unmodified, and new pages with your new solutions. Note that there is a much higher expectation of completeness and good mathematical style in these revisions, since they are prepared by you without time pressure.
• F:
  • Read: §6.3 of YAINTT
  • Submit T&Q30 on today's reading
  • Miniquiz 17 (Yes, this is a mini-, not maxiquiz.)
  • Content:
    1. a primitive root mod $n$
    2. theorems on the existence and non-existence of primitive roots mod $n$ for various $n$

• M:
  • Read: §6.4 of YAINTT
  • Submit T&Q31 on today's reading
  • Miniquiz 18
  • Hand in HW12: 6.1.{1,2,3}, 6.3.{2,5,6}
  • Content:
    1. the index of $b$ relative [a discrete logarithm]
• W:
  • Read: §6.5 of YAINTT
  • Submit T&Q32 on today's reading
  • Miniquiz 19
  • Content:
    1. Diffie-Hellman key exchange [DHKE]
    2. Sophie Germain prime
    3. the Diffie-Hellman problem [DHP]
• Θ:
  • Note special day for this last class meeting. We will start at 1pm and go on as long as students would like.
  • Hand in HW13: any three of (a)-(f) in 6.4.1, and 6.5.2
  • Review for final exam; see this review sheet
• There will be no class on Friday this week; instead, note the above special last class on Thursday.