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

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

In the following, the image means that class was videoed that day 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.

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).

• M:
• Content:
1. Starting example: Pythagoras...
• irrational examples of possible side lengths for a right triangle -- e.g., proof (by contradiction) that $\sqrt{2}$ is irrational
• 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!
2. terms we defined
• rational number, set of which being denoted $\QQ$.
• irrational number
• Pythagorean triple
• primitive Pythagorean triple: count, classify, construct
3. some good, basic Number Theoretic problems:
• primes: counting, twins
• Pythagorean Triples
4. 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
• Miniquiz 0 handed out
• W:
• hand in Miniquiz 0
• Read [before class, as always!]: Chapter 1 of A Friendly Introduction to Number Theory [$4^{th}$ ed.], by Joseph Silverman, © Pearson Education, Inc.
• Content:
1. some basic sets of numbers
1. natural numbers, $\NN$
2. integers, $\ZZ$
3. primes/composites
4. triangular numbers... maybe also square/cube/higher power numbers
2. some basic mathematical notation:
1. "there exits" $\exists$ and "for all" $\forall$
2. set membership, as $x\in\RR$.
3. "$P$ implies $Q$", $P\Rightarrow Q$
3. a little on what makes for good defintion, e.g., for various types of numbers -- observation that it is surprisingly hard to define $\NN$; one way is the Zermelo-Frankel approach which starts with $1$ and has a "successor" function which outputs the next natural number given any particular one as input
4. a basic Number Theoretic problems is the existence of numbers of various "shapes", e.g., triangular numbers; this is not so interesting after Gauss's forumla for the $n$th triangular number $$T_n=\sum_{j=1}^n j = \frac{n(n+1)}{2}$$
5. 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.
6. one thing that seemed to go by in the "$a$ and $b$ cannot both be even" proof was the following part
• Lemma: If $c^2$ is even, then so must be $c$.
which seems intuitively obvious but should probably be explained more carefully...
• Submit T&Q1 on Chapter 1 of A Friendly Introduction [at least an hour before class, as always!]
• Do HW0: Send me e-mail (to jonathan.poritz@gmail.com) telling me:
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.)
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.
10. Anything else you think I should know (disabilities, employment or other things that take a lot of time, etc.)
11. [Optional:] If you could meet one historical figure, who would you choose and why?
• Miniquiz 1
• F:
• Read: Chapter 2 of A Friendly Introduction
• Content:
1. Following Silverman, examining properties of PPTs. Along the way, he seems to use, without satisfactory proof, the following lemmata:
• Lemma: If $a\in\NN$ is such that $a^2$ is even, then $a$ is also even.
• Lemma: If $a,b\in\NN$ have no common factors and if $ab$ is a square, then also $a$ and $b$ are squares.
Silverman's explanation (of the second of these) is to a later chapter, basically to the Fundamental Theorem of Arithmetic.
2. We got the statement of The Pythagorean Triples Theorem. Note that this implies that there are an infinite number of PPTs, and gives a complete description of all of them.
3. Another way to see that there are an infinite number of PPTs:
Theorem: For $n\in\NN$, let $a=2n^2+2n$, $b=2n+1$. Then $(a,b,a+1)$ is a PPT.
[Notes: This amounts to letting $b$ be any odd number, so $b^2$ is also odd, and setting $a=\frac{b^2-1}{2}$. Here we give a version suggested by a question in a student's T&Q2 ... but actually, this approach is the one Euclid used to prove that there are an infinite number of PPTs.]
Proof: Well, just check that $a^2+b^2=(a+1)^2$, it's easy algebra. Also, $a$ and $a+1$ have no common factors -- if $d$ is a factor of $a$, then $d$ goes into $a+1$ with a remainder of $1$ so is not a divisor.   $\Box$
• Submit T&Q2 on Chapter 2 of A Friendly Introduction
• Hand in HW1: 1.2, 1.3 in A Friendly Introduction
• Maxiquiz 1
• Today [Friday] is the last day to add classes.

• M:
• Read: §1.1 of PaR Chapter 1: Well-Ordering and Division (we shall refer to this as PaR1; the "PaR" is short for "Poritz, after Raji", since this is an adaptation by Poritz of an open textbook by Raji.)
• Content:
1. going over:
• Maxiquiz 1:
• There were lots of possible definitions, use one that you will then be happy working with in the proof you were asked to do — often, the easiest definition to work with turns out to be the one which at first seems the most complicated ... because all the moving parts of the definition give you something to grab a hold of.
• Don't forget when you are asked to prove an "if and only if" that there are two directions to prove: i.e., to prove $A\Leftrightarrow B$, you need to prove both $A\Rightarrow B$ and $B\Rightarrow A$.
• Sometimes, proving $A\Rightarrow B$ is not appealing, so you might consider instead proving $\neg B\Rightarrow \neg A$ [where $\neg A$ is the read "not $A$"]. This second statement is the contrapositive of the original, and from basic logic it is in fact entirely equivalent to the original.
• HW1:
• This statement has some relationship to the Twin Prime Conjecture: if there are an infinite number of prime triples, then certainly there are an infinite number of twin primes. On the other hand, there could be only a finite number of prime triples and that would not imply that the Twin Prime Conjecture was true: it is much harder to be a prime triple than to be a twin prime.
• the solution involves fiddling with the possibilities of the number of a potential prime triple being multiples of $3$, by thinking of any $n\in\ZZ$ as equalling $3m$, $3m+1$, or $3m+2$, for some $m\in\ZZ$.
• good careful proofs
• some proof strategies:
1. direct verification ["unpacking"]
3. induction ... and therein lies the Well-Ordering Principle
• The Well-Ordering Principle; note it doesn't always apply, e.g., it doesn't hold if you are working in $\ZZ$ instead of in $\NN$.
• The Pigeonhole Principle
• The Principle of Mathematical Induction, Versions 1 and 2
• example of a proof by induction: problem 1.2 from HW1
• Submit T&Q3 on PaR1 §1.1
• W:
• Content:
1. more on induction, now Version 2
2. quick visit to basic arithmetic properties
3. divisibility, a proof of The Division Algorithm based on the Well-Ordering Principle
• Submit T&Q4 on PaR1 §1.2 or §1.3
• Miniquiz 2
• Hand in HW2:
1. 2.1 in A Friendly Introduction
2. Write down the steps of the proof of the Primitive Pythagorean Triples Theorem from A Friendly Introduction as clearly and completely as you can ... but for cubes, not squares. That is, you are attempting to prove a similar theorem but for triples $(a,b,c)$ satisfying $a^3+b^3=c^3$. Do this by making an outline of the proof following Silverman, stating the version for cubes, and then trying to prove each of the steps for cubes. [You will not be able to prove all of the steps — the cube version of the theorem is false, it's a case of the result know as Fermat's Last Theorem— but more steps along the way are possible that you might at first think.]
3. Exercise 1 from PaR1 §1.1
4. Can you think of a number system which would not satisfy the Well-Ordering Principle? (Other than $\ZZ$, mentioned in class.)
What we're looking for here is a set $\Uu$ of mathematical objects which we'll call "unnatural numbers" which have two operations "${}+{}$" and "${}\cdot{}$" called "unnatural addition" and "unnatural multiplication", both of which take a pair of unnatural numbers and produce another unnatural number, and which together satisfy the same rules that integers satisfy as given in PaR1 §1.2.
Also, on $\Uu$ we have a notion of "${}<{}$" in the sense that given $a,b\in\Uu$, it is always the case that $a<b$, $b<a$, or $a=b$. This is needed to define the word "least" in the Well-Ordering Principle: given a set $S\subset\Uu$, $\ell\in S$ is a least element of $S$ if $\forall x\in S,$ either $x=\ell$ or $\ell<x$.
An Unwell-Ordering example would be a non-empty subset $S\subset\Uu$ for which a least element did not exist.
Try to think of a set of unnatural numbers with an Unwell-Ordering example, in the above sense. That is, write down what will be your set $\Uu$, the operations ${}+{}$ and ${}\cdot{}$, the relation ${}<{}$, and the set $S\subset\Uu$ which has no least element (prove that it has none!).
• F:
• Content:
1. going over Miniquiz 2
2. another proof of The Division Algorithm, this time using the Principle of Mathematical Induction.
3. use the Division Algorithm repeatedly on a number and its successive quotients by the same number $b\in\ZZ$, $b>1$, putting it back together to get the base-$b$ representation of a number $n\in\ZZ$
• Submit T&Q5 also on PaR1 §1.3 [think and question more deeply!]
• Maxiquiz 2 was handed out, please hand it in next Monday; when you do it over the weekend, do not consult anything outside your head (do it like a real quiz!)

• M:
• Content:
1. more on representations of numbers with respect to different bases:
• special names: binary, ternary, octal, decimal, hexadcimal, sexagesimal
• counting on your fingers base $2$
• a bit
• arithmetic in various bases
• non-integral numbers in various bases
2. the greatest common divisor $\gcd(n,m)$ of $n,m\in\ZZ$, definition, basic properties and examples.
3. when two numbers are relatively prime
• hand in Maxiquiz 2
• Submit T&Q6 on PaR1 §1.4
• Today [Monday] is the last day to drop classes without a grade being recorded.
• Miniquiz 3
• W:
• Content:
1. more properties of the $\gcd$.
2. for $n,m\in\ZZ$, $\gcd(n,m)$ as the smallest positive integral linear combination of $n$ and $m$ (think Well-Ordering)
3. several integers being mutually relatively prime or pairwise relatively prime and the relationship
• Submit T&Q7 on PaR1 §1.5
• Miniquiz 4
• Hand in HW3: in PaR1, problems 1.3.8, 1.3.9 [Hint: you may want to use the result from Maxiquiz 2], 1.4.5 [Hint: convert each hexadecimal digit to four bits — explain what are the possibilities and why this works.]
• F:
• Content:
1. the Euclidean Algorithm: statement, proof
2. the Extended Euclidean Algorithm: statement, ideas of proof
• Submit T&Q8 on PaR1 §1.6
• Maxiquiz 3

• M:
• Content:
1. congruences, basic properties
• Submit T&Q9 on PaR2 §2.1
• there was no Miniquiz 5 in class; had there been, it would probably have asked you to state the Euclidean Algorithm or the theorem which characterizes the gcd of two numbers as the minimal element of a particular set of natural numbers.
• Hand in HW4: in PaR1, problems 1.6.1, 1.6.4, 1.6.5
• W:
• Content:
1. linear congruences
• Submit T&Q10 on PaR2 §2.2
• Miniquiz 5
• F:
• Content:
1. more on linear congruences
• Submit T&Q11 on PaR2 §2.2 [again!]
• Maxiquiz 4
• Hand in HW5: in PaR2, problems 2.1.1, 2.1.3, 2.1.5, 2.2.1, 2.2.2, 2.2.3

• M:
• Content:
1. the Chinese Remainder Theorem
• Submit T&Q12 on PaR2 §2.3
• Miniquiz 6
• W:
• Content:
1. another version of working modulo $n$ and linear congruences: equations in "mod $n$ land"
2. defining equivalence relation and sets of equivalence classes
3. definition, basic properties of $\ZZ_n$ (also written $\ZZ/n\ZZ$)
4. restatement of work in §§2.1&2.2 of PaR2 in terms of $\ZZ_n$.
• Submit T&Q13 on PaR2 §2.4
• Hand in HW6: in PaR2, problems 2.3.3 & 2.3.4 (2.3.4 is only in the most recent version of PaR2, go to the online version if you have an older version without that problem)
• Miniquiz 7
• F:
• [Re]Read: PaR2 §§2.4 & 2.5
• Content:
1. Euler's $\phi$ function, also called Euler's totient function
2. Euler's $\phi$ is multiplicative
• Submit T&Q14 on PaR2 §2.5
• Maxiquiz 5

• M:
• Content:
1. basic properties of prime numbers
2. The Fundamental Theorem of Arithmetic
• Hand in HW7: in PaR2, problems 2.4.1, 2.5.1, and 2.5.2
• Submit T&Q15 on PaR3
• Miniquiz 8
• W:
• Content:
1. more on The Fundamental Theorem of Arithmetic
• Submit T&Q16 on any of the readings we have done so far this semester.
• Review for Midterm I; see this page for a review sheet.
• F:
• Midterm I

• M:
• going over Midterm I
• hand in the take-home part of Midterm I, following these steps:
2. Write up a solution to problem 2 or 3 from PaR3 §3.
3. You may use any of the readings assigned for this class (which were Chapters 1 & 2 of A Friendly Introduction and our own in-house readings PaR1, PaR2, and PaR3) and your notes but you may not use any other resource, animate or inanimate! (E.g., do not ask any other human about these problems — e-mail me if you get stuck! — or look at any books or web pages other than the ones specifically permitted.)
4. You will have a much nicer end-product if you write a rough draft of your solution before you write the one you will hand in.
5. Along with the solution you hand in, please attach a signed sheet where you say "I have understood and followed the rules for this take-home test problem."
• W:
• hand in Midterm I revisions, if you like
• Submit T&Q17 on YAINTT §3.2
• F:
• Submit T&Q18 on YAINTT §3.3
• Maxiquiz 6

• M:
• Hand in HW8: in YAINTT, problems 3.3.1, 3.3.2, and either 3.3.3 or 3.3.4 (but not both... unless you want to)
• Submit T&Q19 on YAINTT §3.3
• W:
• Read: YAINTT Chapter 4 Introduction and §4.1
• Submit T&Q20 on today's reading
• Miniquiz 9
• F:
• Submit T&Q21 on today's reading
• Maxiquiz 7 handed out ... please turn in on Monday

• M:
• Submit T&Q22 on today's reading
• don't forget to turn in Maxiquiz 7, which was handed out last Friday
• Hand in HW9: in YAINTT, problems 4.1.1, 4.2.1 — 4.2.3
• Miniquiz 10
• W:
• Reading and T&Qing on hold today, the next textbook section is not yet ready.
• Miniquiz 11
• F:
• Submit T&Q23 on today's reading
• Maxiquiz 8 handed out; it is due in class on Monday
• Today [Friday] is the last day to withdraw (with a W) from classes

• M:
• Submit T&Q24 on today's reading
• don't forget to turn in Maxiquiz 8, which was handed out last Friday
• Hand in HW10: in YAINTT, any two of the three problems 4.4.1 — 4.4.3
• W:
• Submit T&Q25 on today's reading
• F:
• Submit T&Q26 on today's reading
• Maxiquiz 9 was discussed a bit -- it is to be done at home, and consists of your choice of one of the following:
1. Problem 4.5.1 from YAINTT
2. Problem 4.5.2 from YAINTT
3. Send me an e-mail encrypted with my public key, which can be found here. To do this, you will have to download, install, and learn how to use some crypto software: e.g., GnuPG is a great choice, available at gnupg.org, or there are lots of other options, including perhaps your current mail program. So poke around a little in your mail service's help pages, ask google, etc.
4. Send me an e-mail which you sign digitally. You will again need some software to do this — and you will have to get me your public key somehow, so that I can verify the signature. So you will have to run the key-generation part of your crypto software, export the key to an ASCII file, and e-mail that file to me also.

• Spring Break! No classes, of course.
• Don't forget to work on Maxiquiz 9, which was described in class last Friday.

• M:
• review for Midterm II; see this review sheet
• don't forget to turn in Maxiquiz 9 if you chose to do one which is on paper — for details of this maxiquiz, see the entry above for the Friday class before Spring Break.
• W:
• more review for Midterm II
• please have handed in all outstanding HW assignments and be ready to discuss those (and other) problems
• Submit T&Q27 on today's reading through the T&Q on-line forum
• Miniquiz 12 on some crypto vocabulary from Chapter 4 (particular from the last sections which we covered in the week before Spring Break)
• F:
• Midterm II

• M:
• W:
• Submit T&Q31 on today's reading through the T&Q on-line forum
• We had no miniquiz today ... if there had been one, it would have asked for the definition of the term primitive root
• F:
• Submit T&Q32 on today's reading through the T&Q on-line forum
• Maxiquiz 11 turned into a take-home quiz. Please do it in full quiz-like formality: consult no other resource (human, electronic, paper, ...) than is on the quiz sheet itself, and work on it for about 20/25 minutes at the most. Then hand it in on Monday.

• M:
• Submit T&Q33 on today's reading through the T&Q on-line forum
• Miniquiz 14
• don't forget to turn in Maxiquiz 11, which was a take-home quiz this past weekend.
• Hand in HW12: in YAINTT, problems 5.3.2, 5.3.4, and 5.3.5.
• W:
• F: