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:*- 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!

- irrational examples of possible side lengths for a right
triangle --
- terms we defined
**rational number**, set of which being denoted $\QQ$.**irrational number****Pythagorean triple****primitive Pythagorean triple**: count, classify, construct

- some good, basic Number Theoretic problems:
- primes: counting, twins
- Pythagorean Triples

- 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**

- Starting example: Pythagoras...
**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:*- some basic sets of numbers
- natural numbers, $\NN$
- integers, $\ZZ$
- primes/composites
- triangular numbers... maybe also square/cube/higher power numbers

- some basic mathematical notation:
- "there exits" $\exists$ and "for all" $\forall$
- set membership, as $x\in\RR$.
- "$P$ implies $Q$", $P\Rightarrow Q$

- 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 - 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}$$ - 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.
- 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$.

- some basic sets of numbers
**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*:- Your name.
- 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.)
- Your year/program/major at CSUP.
- The reason you are taking this course.
- What you intend to do after CSUP, in so far as you have an idea.
- Past math classes you've had.
- Other math and science classes you are taking this term, and others you intend to take in coming terms.
- Your favorite mathematical subject.
- Your favorite mathematical result/theorem/technique/example/problem.
- Anything else you think I should know (disabilities, employment
or other things that take a lot of time,
*etc.*) - [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:*- 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.

- We got the statement of
. Note that this implies that there are an infinite number of PPTs,**The Pythagorean Triples Theorem****and**gives a complete description of all of them. - 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$

- Following Silverman, examining properties of PPTs. Along the way,
he seems to use, without satisfactory proof, the following lemmata:
**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:*- 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$.

- This statement has some relationship to the
- good careful proofs
- some proof strategies:
- direct verification
*["unpacking"]* - contradiction
- induction ... and therein lies the
*Well-Ordering Principle*

- direct verification

- some proof strategies:
**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*

- going over:
**Submit T&Q3**on*PaR1 §1.1*

*W:***[Re}Read:***PaR1 §§1.1—1.3**Content:*- more on induction, now Version 2
- quick visit to basic arithmetic properties
- 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**:- 2.1 in
**A Friendly Introduction** - 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.] - Exercise 1 from PaR1 §1.1
- 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!).

- 2.1 in

*F:***[Re]Read:***PaR1 §1.3**Content:*- going over
*Miniquiz 2* - another proof of
*The Division Algorithm*, this time using the Principle of Mathematical Induction. - 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$**

- going over
**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:***Read:***PaR1 §§1.4&1.5**Content:*- 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

- special names:
- the
**greatest common divisor $\gcd(n,m)$ of $n,m\in\ZZ$**, definition, basic properties and examples. - when two numbers are
**relatively prime**

- more on representations of numbers with respect to different
bases:
- 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:***[Re]Read:***PaR1 §1.5**Content:*- more properties of the $\gcd$.
- for $n,m\in\ZZ$, $\gcd(n,m)$ as the smallest positive integral
linear combination of $n$ and $m$ (think
*Well-Ordering*) - 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:***Read:***PaR1 §1.6**Content:*- the
**Euclidean Algorithm:**statement, proof - the
**Extended Euclidean Algorithm:**statement, ideas of proof

- the
**Submit T&Q8**on*PaR1 §1.6***Maxiquiz 3**

*M:***Read:***PaR2 §2.1**Content:*- 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:***Read:***PaR2 §2.2**Content:*- linear congruences

**Submit T&Q10**on*PaR2 §2.2***Miniquiz 5**

*F:*

*M:**W:***Read:***PaR2 §2.4**Content:*- another version of working modulo $n$ and linear congruences: equations in "mod $n$ land"
- defining
**equivalence relation**and sets of**equivalence classes** - definition, basic properties of $\ZZ_n$ (also written $\ZZ/n\ZZ$)
- 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:*- Euler's $\phi$ function, also called Euler's totient function
- Euler's $\phi$ is multiplicative

**Submit T&Q14**on*PaR2 §2.5***Maxiquiz 5**

*M:**W:**F:***Midterm I**

*M:*- going over
**Midterm I** **hand in the take-home part of**, following these steps:*Midterm I*- Read your favorite religious or philosophical text for 10 minutes to engage your moral sense.
- Write up a solution to problem 2
**or**3 from*PaR3 §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.) - 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.
- 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."

- going over
*W:**F:*

*M:**W:***Read:***YAINTT Chapter 4 Introduction and §4.1***Submit T&Q20**on today's reading**Miniquiz 9**

*F:***Read:***YAINTT §4.2***Submit T&Q21**on today's reading**Maxiquiz 7**handed out ... please turn in on Monday

*M:**W:***Read**ing and**T&Q**ing on hold today, the next textbook section is not yet ready.**Miniquiz 11**

*F:***Read:***YAINTT §4.4***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:**W:***Read:***YAINTT §4.5***Submit T&Q25**on today's reading

*F:***Read:***YAINTT §4.6***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:- Problem 4.5.1 from YAINTT
- Problem 4.5.2 from YAINTT
- 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.* - 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.

- review for
*W:*- more review for
**Midterm II** - please have handed in all outstanding
**HW**assignments and be ready to discuss those (and other) problems **Read:***YAINTT §3.4***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)

- more review for
*F:***Midterm II**

*M:*- going over
**Midterm II**

- going over
*W:***Read:***YAINTT Chapter 5 Intoduction*and*§5.1***Submit T&Q28**on today's reading through the T&Q on-line forum**Miniquiz 13**- hand in
**Midterm II**revisions, if you like

*F:***Read:***YAINTT §5.1***Submit T&Q29**on today's reading through the T&Q on-line forum**Maxiquiz 10**

*M:***Read:***YAINTT §5.2***Submit T&Q30**on today's reading through the T&Q on-line forum- Hand in
**HW11**: in YAINTT, problems 5.1.1, 5.1.2 and 5.1.4.

*W:***Read:***YAINTT §5.3***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:***[Re]Read:***YAINTT §5.3***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:***Read:***YAINTT §5.4***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:***Read:***YAINTT §5.5***Submit T&Q34**on today's reading through the T&Q on-line forum**Miniquiz 15**

*F:***Read:***YAINTT §5.6***Submit T&Q35**on today's reading through the T&Q on-line forum**Maxiquiz 12**- Hand in
**HW13**: in YAINTT, problems 5.4.1(do only two of parts**(a)**—**(f)**, your choice which two), 5.4.2, 5.5.1, and 5.5.2

**Exam week**, no classes.- Here is a review sheet for the final.
- Our
is scheduled for*FINAL EXAM***Wednesday, April 30th 10:30-12:50 in our usual classroom**.