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

- gave a fairly complete, albeit somewhat informal, proof that $\sqrt{2}$ is not rational
- 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"

- terms we defined
- As soon as possible, please 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:] 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:*- some more basic sets of numbers
- point of view of needing new sets of numbers in order to solve more and more complicated equations.
**real numbers**, set of which being denoted $\RR$.- this is also a subtle set...

**irrational numbers****complex numbers**

- some more basic mathematical notation:
- $P\Rightarrow Q$, read as "$P$ implies $Q$" or "If $P$, then $Q$."
- $P\Leftrightarrow Q$, read as "$P$ if and only $Q$"
- "iff", read as "if and only if"

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

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

- some more basic sets of numbers
**Miniquiz 1**

*F:*

*M:**W:***Read:**§1.4 of YAINTT**Submit T&Q4**on today's reading*Content:*- Additional problems:
*triangular numbers*, and a first hit of the addictive drug which is the study of the*primes*

- Additional problems:
**Miniquiz 3**

*F:*

*M:***Read:**§2.2 of YAINTT**Submit T&Q6**on today's reading*Content:*- Going over Maxiquiz 2
- Going over HW2
- Counting presents in a famous holiday song
- More on Induction:
- The alternate form of the inductive step
- Common sources of error in inductive proofs,
*e.g.,*proof that**All pigs are yellow**.

- 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:***divisor**,**factor**,**multiple**, and the notations $a\mid b$ and $a\nmid b$**even**and**odd**- divisibility of linear combinations

**Miniquiz 5**

*F:*

*M:**W:***Read:**§2.5 of YAINTT**Submit T&Q10**on today's reading*Content:*- the
**greatest common divisor**, $\gcd(a,b)$

- the
- no miniquiz today, but you should be able to define and explain the base-$b$ expansion of a number!

*F:*

*M:***Read:**§3.1 of YAINTT**Submit T&Q12**on today's reading*Content:*- congruences: definition, basic properties and examples

**Miniquiz 7**

*W:***Reread:**§3.1 of YAINTT**Submit T&Q13**on today's reading*Content:*- more basics of congruences

**Miniquiz 8**

*F:***Read:**§3.2 of YAINTT**Submit T&Q14**on today's reading*Content:*- linear congruences [
*i.e.,*linear congruence equations]

- linear congruences [
- 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:*- more on linear congruences
- multiplicative inverses mod $n$

**Miniquiz 9**

*W:***Read:**§3.3 of YAINTT**Submit T&Q16**on today's reading*Content:*- The Chinese Remainder Theorem

**Miniquiz 10**

*F:***Read:**§3.4 of YAINTT**Submit T&Q17**on today's reading*Content:*- 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:*- 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:*- 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. - (more) basics about primes
- a
**Euclid's Lemma**-type result where the divisor is prime - the (justifiably famous)
**Fundamental Theorem of Arithmetic**

- 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

- No

*M:***Read:**§4.2 of YAINTT**Submit T&Q20**on today's reading**Miniquiz 12***Content:*- the uniqueness part of the
**Fundamental Theorem of Arithmetic** **Wilson's Theorem**-- an odd condition for primality with a fun proof.

- the uniqueness part of the

*W:***Read:**§4.3 of YAINTT**Submit T&Q21**on today's reading**Miniquiz 13***Content:*- the definition of
**multiplicative order** - an analogue of
**Lagrange's Theorem**in the current context

- the definition of

*F:***Reread:**§4.3 of YAINTT**Submit T&Q22**on today's reading**Maxiquiz 8***Content:***Euler's Theorem****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:*- basic history, ideas, and terminology of cryptology

*W:***Read:**§5.2 of YAINTT**Submit T&Q24**on today's reading**Miniquiz 15***Content:***Caesar**and**Vigenère**cryptosystems**one-time pads**

*F:***Reread:**§5.3 of YAINTT**Submit T&Q25**on today's reading**Maxiquiz 9***Content:*- cryptanalysis by
**frequency analysis**

- cryptanalysis by
- 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)?

**Spring Break!**No classes, of course.

*M:**W:***Read:**the rest of §5.4 of YAINTT**Submit T&Q27**on today's reading**Miniquiz 16***Content:*- the
**RSA public key cryptosystem** - [
**cryptographic**]**salt**

- the

*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:***digital signatures**

*M:***Read:**§5.6 of YAINTT**Submit T&Q29**on today's reading- Hand in
**Maxiquiz 10**. *Content:***man-in-the-middle attacks****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:*- 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)^*$.

- Recall from before, working inside $(\ZZ/n\ZZ)^*$ for some
$n\in\NN$: [
- 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:*- a
**primitive root mod $n$** - theorems on the existence and non-existence of primitive roots mod $n$ for various $n$

- a

*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:*- the
**index**of $b$ relative [a**discrete logarithm**]

- the

*W:***Read:**§6.5 of YAINTT**Submit T&Q32**on today's reading**Miniquiz 19***Content:***Diffie-Hellman key exchange**[**DHKE**]**Sophie Germain prime**- 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.

**Exam week**, no classes.- Our
**FINAL EXAM**is scheduled for**Monday, April 27**.^{th}, 1-3:20pm, in our usual classroom