[past] Number Theory 1 & 2

The following is abridged from Wikipedia, the free encyclopedia

Diophantus of Alexandria - (Greek: Διόφαντος ὁ Ἀλεξανδρεύς , circa 200/214 – circa 284/298) was a Greek mathematician of the Hellenistic era. Little is known of his life except that he lived in Alexandria, Egypt ...

He was known for his study of equations with variables which take on rational values and these Diophantine equations are named after him. Diophantus is sometimes known as the father of Algebra. He wrote a total of thirteen books on these equations. Diophantus also wrote a treatise on polygonal numbers.

In 1637, while reviewing his translated copy of Diophantus' Arithmetica (pub. ca.250) Pierre de Fermat wrote his famous Last Theorem in the page's margins. His copy with his margin-notes survives to this day.

Although little is known about his life, some biographical information can be computed from his epitaph. He lived in Alexandria and he died when he was 84 years old. Diophantus was probably a Hellenized Babylonian.

A 5^th and 6^th century math puzzle involving Diophantus' age: He was a boy for one-sixth of his life. After one-twelfth more, he acquired a beard. After another one-seventh, he married. In the fifth year after his marriage his son was born. The son lived half as many as his father. Diophantus died 4 years after his son. How old was Diophantus when he died?

What is the answer, with reasoning? (It is in the source-file.)

Our Teaching Page has important information for my students. (It has the Notes, Exams and Links from all of my previous courses.)
The Teaching Page has my schedule, LOR guidelines, and Usually Useful Pamphlets. One of them is the Further information is at our class-archive URL (I email this private URL directly to students).

In all of my courses, attendance is absolutely required (excepting illness and religious holidays). In the unfortunate event that you miss a class, you are responsible to get all Notes / Announcements / TheWholeNineYards from a classmate, or several. All my classes have a substantial class-participation grade.

Number Theory topics

First week of class: Memorize the Math-Greek alphabet (pdf), which we will use in class frequently.
First week of class: Read and throughly understand w:Set-builder notation (up through “Equivalent predicates...”).
First week of class: Read w:NT through the end of section titled “Fermat”.
Modular arithmetic and repeated-squaring. Also: The h-orbit of a point, where h() is a function.
The Euclidean algorithm can be presented in table-form; I call this form the Lightning-bolt algorithm (pdf), because the update-rule looks like a lightning-bolt (used thrice). Here is a practice sheet for LBolt (pdf).

The first page of Algorithms in Number Theory (pdf) uses LBolt iteratively to compute the GCD of a list of integers, together with a list of Bézout multipliers. Page 2 uses LBolt to solve linear congruences: Find all x where 33x is mod-114 congruent to 18.
Euler phi function. Fermat's Little Thm. Euler-Fermat Thm (EFT).
The important Chinese Remainder Theorem (pdf) [CRT] tells us the structure of Zed_M. The CRT is an example of a Ring-isomorphism. (Time permitting, we may learn that Finite fields have cyclic multiplicative groups (pdf). This pamphlet also proves the Primitive Root Thm, and Korselt's Thm characterizing the Carmichael numbers.)
Possibly: Notes-in-progress on Fermat's SOTS (Sum-Of-Two-Squares) thm.
Slides showing how the Euclidean Algorithm writes a given N as a Sum Of Two Squares (pdf). Such an N is a SOTS in the notes.
In pamphlet Multiplicative Functions (pdf) you need to know defns of the divisor-count, divisor-sum and Euler-phi fncs, and formulas for them.
But you may ignore (and probably should) the rest of the material, for the time being.
Miller-Rabin probabilistic factorization algorithm.
Pollard-ρ factorization algorithm.

Descent-from-the-Top

Algebraic structures: Ring basics, which has the defns of Group, Ring Field, as well as zero-divisor, unit, and the especially important notion of irreducible and prime elements.
Diophantine equations: Algebraic equations where the only solutions that we allow are using integers. We will find all Pythagorean Triples (pdf) (a,b,c) of positive integers for which

a² + b² = c² .

We will discover that there is a two-parameter family of such solutions.
Fermat Sum-Of-Two-Squares thm (SOTS thm). The related Lagrange 4-square thm.
Possibly: Pell's equation.
Partial Theorem List (pdf) [LBolt. Irred vs. prime. FLiT. ERT. Wilson's thm. LST. Quadratic-reciprocity thm.] for Number Theory. A topics guide (txt) for an exam from Spring 2013.

Summer 2018, Number Theory 1:

Number Theory czars who help out.

Projector	Phone-list	Chalk	E-Probs	Time	Humor	Haberdasher
Lizzie	Big Al	Roma	DanDan & Brandon	Jared	DJ	Scott

In one convenient location: All 9 NT 2018s quizzes so far (pdf),
By Tues., 03July please learn the Euclidean Algorithm, in the form of the Lightning-bolt algorithm (pdf) [so called, because the update-rule looks like a lightning-bolt], using our practice sheet for LBolt (pdf) and LBolt answers (txt),
Please have fully-understood (grokked) Algorithms in Number Theory (pdf). It uses LBolt iteratively to compute the GCD of a list of integers, together with a Bézout-list.
Page 2 uses LBolt to solve linear congruences, e.g: Find all x where 33x is mod-114 congruent to 18.
While microquizzes are typically unannounced, here are the first three:
Microquiz on Thurs., 05July, testing Lightning-bolt, and basic modular arithmetic.
MQ on Fri., 06July, testing Iterated-Lightning-bolt, modular arithmetic, Math-Greek alphabet (pdf).
MQ on Mon., 09July, testing Iterated-Lightning-bolt, modular arithmetic, and the Fund. theorem of Arithmetic (e.g, its proof using Bézout multipliers).
By Monday, 09July, please have read Ring basics, which has the defns of Group, Ring Field, as well as zero-divisor, unit, and the especially important notion of irreducible and prime elements.
In pamphlet Multiplicative Functions (pdf) you need to know defns of the divisor-count, divisor-sum and Euler-phi fncs, and formulas for them.
But you may ignore (and probably should) the rest of the material, for the time being.
The delightful Home-A was followed by the cute Class-A (pdf).
The amusing Class-B might make use of our b² + 5c² list-of-primes. It was preceded by the nifty-cool Home-B.
Class-C, a paper-and-hensel exam, provided hours of entainment.
Shuffling in to view is the Individual Optional Project (IOP-D), due [if you choose to do it] at 2PM, on Friday, 10Aug2018, at the beginning of class/party.

Summer 2016, Number Theory 1:

Folks, I had a great time working with you this summer on Number Theory. Stop by in the Spring and tell me how you are doing. --Prof. K.

(There is another class-photo at the end of this section. )

The friendly puzzles of our congenial Games-party continued on Friday with the mind-expanding Class-C (pdf), bringing our Number Theoretic summer to a satisfying finale (knowing that there is still much to learn).

Newspaper headlines across the country proclaimed, The perfect sequel! The right parenthesis... to the left-parenthesis of Class-A.

One contestant waxed lyrical, It had my favorite characters, in action-packed circumstances. The mathematical and emotional equivalent of a good James Bond movie ... --I was stirred, but not shaken.. With a twinkle in his eye, he quipped And, finally, someone gave Hensel a lift....
The Microquizzes (pdf), as well as (E7), (Q Nein) and (Q Bonus).
Over a pleasant day at the beach, we linger. Over a marvelous meal with friends, we linger. By this criterion, Monday's leisurely Class-B (pdf), was the root cause of sustained universal pleasure.

Newspaper headlines across the country proclaimed, Class-B revolutionary --Time stands still!. Opined one participant, It has everything! he enthused deliriously, Including one Fusion too many ,,, (Prof. K is evidently proFusion). Eager puzzle-solvers worldwide breathfully await the next installment.
Exam preparation, and the Class-B memorial Tee Shirt.
Shouts of Joy greeted the beguiling Class-A (pdf), whetting people's appetite for further Number Theoretic gems. Flowers and gold coins were tossed on the stage by an appreciative audience, as crowds gathered to cheer the elegance of the exam.

Newspaper headlines across the country proclaimed, Class-A a triumph!, splashed across the front page in 19-point font. It has everything!, gushed one audience member, Mystery!, Sophistication!, Suspense!. Avid readers everywhere are looking forward to the next installment.
Our Course Syllabus has exam dates.

Number Theory czars who helped out.

Projector	Phone-list	Blackboard	E-Probs	Time	Humor/Chocolate
Mark	Hunter	(Everyone)	Ariana	Ariana	Andrea aka Bubba

Spring 2007, Number Theory:

The various Number Theory czars who helped out.

Projector	Phone-list	Chalk	Blackboard	H-Probs	Time
Rebecca	Cameron	Charlye	Marshall	Jimmy-C & Dream	Cameron

Here are the sometimes-challenging Extra NT Problems (txt).
The joyous Home-A (pdf), exists.

General gaity and acclaim greeted the smooth Class-A (pdf) with its CRT computation.
The fabulous Home-B (pdf), was due Thurs., 01March.

The Fascinating Class-B (pdf) was moved later to Mon., 26March. Please have brought lots of lined-paper and a calculator, since some of the numbers may have been large.

The point-producing Bonus-B (pdf), after the extension, was due Tuesday, 10Apr.
The spiffy Home-C (pdf) (the final project, done individually [typed]) was due by 4PM, Fri., 27Apr2007.

Spring 2006, Number Theory 1 We may use more advanced computing devices...

May the Force be with you! Since time-travel into the Future is now possible, you may wish to visit the Spring 2007 webpage for the Time-Travel version of this course.

NT1 will have a continuation emphasising Computational Number Theory (NT2), in Fall 2006.

Our NT1 syllabus (txt) lists approximately what we will cover.
The wonderful A-Home (pdf) came into being, engendering Extra A-Home (pdf), for those who want to work on extra stuff.
Gorgeous A-Class (pdf) is available for soln-posting. (Sumeet already has TWO solns posted.)
The fabulous B-Home(pdf) was followed by the astonishing B-Class(pdf). Accept no substitutes! Get your copy today!
Voila! C-Home (pdf), for your thinking and writing pleasure.

We started with textbook

Fundamentals of Number Theory.

Author:	William J. Leveque	ISBN:	0-486-68906-9
Year:	1996	Publisher:	Dover

and switched part way through to Shoup's text.

Autumn 2006, Computational Number Theory We may use more advanced computing devices...

Welcome! to a continuation of my Number Theory 1 of Spring2006.

Our textbook is A Computational Introduction to Number Theory and Algebra.

Author:	Victor Shoup	ISBN:	0-521-85154-8
Year:	2005	Publisher:	Cambridge University Press

The author has made freely available a PDF copy of his text for those who wish to print a copy.

Extra Problems are kindly maintained by Isaac and Amos.
The fabulous Home-W exists, as well as Class-W.
The Gently Gorgeous Home-X has arrived, along with its thoughtful confrere Class-X.
The Final project Home-Y, which needed to be carefully typed, was due…

…by 2PM, Friday, 08Dec2006.

Spring 2000, Number Theory 1 We may use more advanced computing devices...

[I taught a Continuation of this course, NT2, in Spring 2001.]

Our textbook was An Introduction to the Theory of Numbers (Fifth Edition).

Authors:	Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery	ISBN:	978-0-471-62546-9
Year:	1991	Publisher:	John Wiley & Sons

This is a classic number theory textbook (Niven & Zuckerman), updated by Hugh Montgomery. It is renowned for its excellent problems.

Syllabus

The plan is to cover chapters 1-4, and parts of chap. 5.

Prof. Hugh Montgomery maintained an errata sheet (pdf) for the NZM text.

Prof. Ken Ribet's has a guide to several NT books. His references to “Math 115” refer to his number theory course, not mine! (Note that I and my are Prof. Ribet speaking.)

Homework and reading.

The E-problems (txt) You may present an E-prob whenever you wish: Simply come to class early and put your solution on the blackboard.

Homework assignments (txt).

Homework due Wedn., 20Mar2000 (pdf).

Exams and Projects (Number Thy)

There will be N exams, for some small positive integral value of N.

(2000)
Mon. 07Feb	Exam-Z (pdf): [In class.] The exam may cover material through the end of the Binomial section, NZM 1.4.
Fri. 18Feb	Quiz Q1: Soln to Q1 (txt).
Wed. 22Mar	Exam-Y (pdf): Held in room LIT368 from 5PM-6:30PM. Please bring a hand-held calculator for this open-brain closed-book exam.
TBS	Exam-X (pdf): There will be no final-exam during exam week.

Spring 2001, Number Theory 2 We may use more advanced computing devices...

Welcome! This is the continuation of my Number Theory 1,

Exam A

There were 6 questions, Q0,Q1,…,Q5. q0-1.NT2001g (txt), q2-NT2001g (txt), q3-NT2001g (txt), and q4-5.NT2001g (txt).

Exam B

Exam B (pdf, 2 pages), is our final exam.

Grading

I plan to run this more as a seminar than as a standard Learn/Exam/Learn/Exam… course. While I expect that I will present the lion's share of the material, I hope to encourage students to perhaps give some prepared talks on a particular problem or subject.

As such, I expect that every student who attends regularly and participates in the discussions will earn an A. There will be some graded homework, and you can do homework singly or jointly, as you choose.

Syllabus

We plan to cover much of Chapter 5 of our textbook An Introduction to the Theory of Numbers (5^th edition) by Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery.

We'll review modular arithmetic and the Chinese Remainder Thm. Then cover the Legendre and Jacobi symbols. We'll then solve certain Diophantine equations (DE), roughly following chapter 5 of NZM.

We will prove Lagrange's theorem that every positive integer is a sum of exactly 4 perfect squares (allowing the square of zero). Exercise: How is 150 a sum of four squares? Lagrange's proof using the beautiful and elementary "proof by Infinite Descent" method of Fermat. It gives an algorithm for finding four such squares.

Author:	James K. Strayer	Edition:	2002
ISBN:	1577662245	Publisher:	Waveland (Reissue edition, blue & purple cover)