Number Theory

Syllabus

Class Calendar

  • 6/20/2022 – Some Fundamentals of Number Theory Slides: The material covered tonight was from sections 1.5, 3.1 through 3.5, and 3.7 in the textbook. In addition to the material on the slides, we covered the following results which are largely consequences of Bezout’s Theorem:
    • Lemma: Given \(a,b,d\in\mathbb{Z}\), if \(d=(a,b)\), then \((a/d,b/d)=1\).
    • Lemma: Given \(a,b,d\in\mathbb{Z}\), if \(d=(a,b)=ax_0+by_0\), then \(d=ax_t+by_t\) whenever \[x_t=x_0+\frac{b}{d}t\ \text{and}\ y_t=y_0-\frac{a}{d}t.\] Further, all solutions to \(d=ax+by\) are of this form.
    • Lemma: Given \(a,b,d,n\in\mathbb{Z}\), with \(d=(a,b)\), there exist solutions to \(n=ax+by\) if and only if \(d|n\).
  • 6/22/2022 – Modular Equations Slides: In this lecture we covered material from sections 4.1-4.3. Most of what we covered is in the slides except at the end when we looked at how to use the Chinese Remainder Theorem to carry out fast modular exponentiation. We did the example of \(23^{100}\pmod{210}\) by breaking it down to \[\begin{align} 23^{100}\pmod{5}&=(-2)^{100}\pmod{5}\\ 23^{100}\pmod{6}&=(-1)^{100}\pmod{6} \\23^{100}\pmod{7}&=2^{100}\pmod{7}\end{align}\] which are simple enough to do by hand, and then putting the solutions together using the C.R.T.
  • 6/27/2022 – Tonight’s lecture focussed on solving equations. We expanded our ability to solve linear equations; this can be summarized as
    • Lemma: Given \(ax+b\equiv c\pmod{n}\) and \(d=(a,n)\), if \(d\) divided \(c-b\), then there are exactly \(d\) solutions modulo \(n\). Moreover all the solutions are of the form \[x_t=x_0+\frac{n}{d}t\] where \(x_0\) is any one solution.
  • We also explored solving polynomial equations \(f(x)\equiv 0\pmod{n}\) using Hensel’s Theorem to solve these when \(n=p^k\) where \(p\) is prime and \(k\geq 2\) and then stitching these answers together using the Chinese Remainder Theorem.
  • 6/29/2022 – Tonight we covered section 3.6 on Fermat Factorization, 4.6 on the Pollard Rho Method, and 5.1 on divisibility tests. Be sure to look through these sections and try some of the computational exercises in each. For the material in 3.6 and 4.6 you can use the applets here, Factorization and Primality Testing Programs, to help check your work. Finally, recall that Monday is July 4th, so we will not be meeting for class.
  • 7/6/2022 – Tonight we covered material from chapters 6 and 7. Specifically we looked at Wilson’s Theorem (and its converse), Fermat’s Little Theorem, Euler’s \(\phi\)-function, Euler’s Theorem, the number theoretic functions \(\sigma\) and \(\tau\), and the Mobius Inversion function \(\mu\). You should review the material in those chapters and work on the problems from them. In particular you should be familiar with the statements of the theorems, the definitions of the functions, and be able to calculate the values of \(\phi(n)\), \(\sigma(n)\), \(\tau(n)\), and \(\mu(n)\) when given a natural number \(n\) and its prime factorization. Finally, recall that at the end of the session you will be taking an exam on the fundamentals of number theory; we have at this point covered all the content on that exam as listed on the syllabus, so you should start reviewing for that now.
  • 7/11/2022 – Tonight we covered material on Cryptology and Number Theory in these Lecture Slides. Together with our previous discussion about affine ciphers, we have now discussed much of the material in sections 8.1-8.4 and 8.6. On Wednesday we will look at chapter 9 on primitive roots.
  • 7/13/2022 – …

Assignments

Do four problems from each chapter; no more than two from any one section.

  • Chapter 3:
    • \(\S\) 3.1: 10;
    • \(\S\) 3.3: 14,22;
    • \(\S\) 3.4: 6 & 8(a);
    • \(\S\) 3.5: 6, 17 & 18;
    • \(\S\) 3.6: 4abc;
    • \(\S\) 3.7: 2abc, 6, 20
  • Chapter 4:
    • \(\S\) 4.1: 8, 12, 30;
    • \(\S\) 4.2: 2abc, 6, 8, 14(use 13);
    • \(\S\) 4.3: 4ab, 12, 16;
    • \(\S\) 4.6: 2, (#3 for extra credit);
  • Chapter 5:
    • \(\S\) 5.1: 5-8(a)(as one problem, use theorems 5.2 & 5.3), 15&16, 17, 22;
    • \(\S\) 5.4: 1,2;
    • \(\S\) 5.5: 2,4,7,8,25ab(c is extra credit)
  • Chapter 6:
    • \(\S\) 6.1: 4, 8, 14, 20, 22;
    • \(\S\) 6.2: 3 (try using the Chinese Remainder Theorem), 8, 12;
    • \(\S\) 6.3: 2, 4, 12, 14.
  • Chapter 7:
    • \(\S\) 7.1: 4, 8, 20;
    • \(\S\) 7.2: 4, 10, 12, 16;
    • \(\S\) 7.4: 6, 10, 12, 16.
  • Chapter 8:
    • \(\S\) 8.1: 4, 6, 15 & 16 (together)
    • \(\S\) 8.2: 1 & 2 (together), 26 & 27 (together)
    • \(\S\) 8.3: 2, 4
    • \(\S\) 8.4: 2, 6, 8, 12
    • \(\S\) 8.6: 2, 4 & 5 (together)
  • Chapter 9:
    • \(\S\) 9.1: 4, 8, 12&13, 18;
    • \(\S\) 9.2: 6, 10, 13;
    • \(\S\) 9.3:6, 12;
    • \(\S\) 9.4: 4, 10;
  • Chapter 10:
    • …

Fundamentals Exam

Links and Handouts