## Homework Number Theory Problems

## Fall 2015, UIUC: MATH 453 Elementary Theory of Numbers

**Time:** MWF 12:00-12:50 **Place:** 443 Altgeld **Instructor:** Nicolas Martinez Robles (247A Illini Hall) **Office hours:** (tentative) Tuesday 11:15 to 12:15 or by appointment **Grader:** Vlad Sadoveanu (273 Altgeld, sadovea2@illinois.edu)

**Email:** niroblesillinois.edu**Course webpage with syllabus:**https://faculty.math.illinois.edu/Bourbaki/Syllabi/syl453.html

**Books:** There is a large number of books on elementary number theory. The textbook for this course will be

- J. K. Strayer,
*Elementary Number Theory*, Waveland Press, 1994/2002, ISBN 1-57766-224-5.

- G.H. Hardy and E.M. Wright,
*Introduction to the Theory of Numbers* - S. J. Miller and R. Takloo-Bighash,
*An Invitation to Modern Number Theory* - H. Rademacher,
*Lectures on Elementary Number Theory*

**Syllabus:**Course content and prerequisites This course is an introduction to number theory, the branch of pure mathematics that deals with properties of integers. Officially, the prerequisite is "Math 241 or equivalent"; however, a good level of mathematical maturity will be sufficient. You should be familiar with standard proof techniques, such as induction and proof by contradiction, and be able to properly write up a mathematical argument. This is a rigorous mathematical course, so there will be a certain amount of definitions, theorems, and proofs. Nevertheless, there will also be a good deal of concrete, hands-on computations, not to mention interesting and fun applications. It is highly recommended that you participate actively in lectures, and put in a lot of effort into solving the homework problems on your own before discussing with others. It will not be possible to succeed in this course merely by memorizing the techniques you see in class or in the textbook. The first four chapters in the Strayer text form the core material. We will cover these chapters, and selected topics from the rest of the text, depending on the time available and students' interest. In the official link above you can find a more detailed description of the content of each chapter.

**Weekly written homework:**The written homework is a chance to work on problems independently and assess your progresses. To succeed in the course, it is necessary to put effort into the homework. Always make sure that you know the definitions of all the words in the question, have consulted the relevant sections in your class notes and textbook, and spent a significant amount of time thinking about how different concepts in the problem link together. Be sure that your final write-up is clean and clear and effectively communicates your reasoning to the grader (Vlad Sadoveanu). In particular, proofs should be written in full sentences and contain all the necessary details. You can discuss the homework problems with others, but you must write up solutions independently, on your own. No late assignments will be accepted; however, your lowest two homework scores will be dropped.

**Weekly Reading:**The goal of the weekly reading assignments is to help you learn and retain the material. The presentation in the class will usually differ slightly from the presentation of the material in the textbook.

**Exams:**This offering of MATH 453 has three 50 minute midterm exams (you may drop one of these 3 midterms instead of dropping 1 homework set) and one 3 hour final exam. The midterms will take place in class, and will be announced at least two weeks in advance. Information on exact times, as well as sample exams, will be posted on this webpage. The final exam is scheduled for Monday, 12/14/15, from 19:00 to 22:00, room 443 of Altgeld. There will be no make-up exams. Instead, if you miss an exam and have a valid excuse, the exam will be marked as excused. An "excused" exam means that it will not not be taken into account in the computation of your grade. Valid excuses include illness, an out-of-town job interview, etc., and must be documented by a letter from the Dean or Emergency Dean; see the Emergency Dean's website for more information on this.

**Grading:**Your grade will be computed by combining scores from your written homework, midterm exam, and final exam according to the following percentages: Homework (15%), Midterms (22.5% each, total 45%), Final (40%).

**Resources:**Office hours: You are welcome to bring any questions you have to office hours.

Email: My email is above. I try to have a good response time to emails.

**ASSIGNMENTS:**

Homework assignments and rough outlines of homework solutions will be posted here. Be sure to consult the syllabus for homework policies, especially with regards to collaboration, write-up standards and submission.

The warm-up questions are not to turn in - they are usually quick computational problems with answers at the back of the book. However, they are valuable practice, and you should know how to do these for the exam. Turn in homework at the beginning of Wednesday's lecture; if you need to miss that class for any reason, please ask someone to bring it in for you or contact me in advance to make alternate arrangements.

Aug 26: Homework 01, due on 09/02/2015. Solutions here.

Aug 27: Additional notes 1

Sep 2: Additional notes 2

Sep 2: Homework 02, due on 09/09/2015. Solutions here

Sep 9: No homework.

Sep 18: Homework 03, due on 09/25/2015. Solutions here

Sep 28: Homework 04, due on 10/07/2015. Solutions here

Oct 7: Additional notes 3 You can also find a proof by induction here.

Oct 7: Homework 05, due on 10/14/2015. Solutions here

Oct 13: Additional notes 4

Oct 16: Homework 06, due on 10/23/2015. Solutions here

Oct 23: Homework 07, due on 10/30/2015. Solutions here

Oct 30: Homework 08, due on 11/06/2015. Solutions here

Nov 6: Homework 09, due on 11/13/2015. Solutions here

Nov 21: Homework 10, due on 12/02/2015. Solutions here

**ANNOUNCEMENTS:**

Aug 24: First day of class. Introduction of the syllabus, grading system, homework, office hours etc...

Introduction to divisibility.

Aug 26: Emergency and fire instructions distributed to the students

Division algorithm, introduction to prime numbers, Euclid's theorem (statement and proof).

Aug 28: Criterion for prime numbers, Eratosthenes' sieve, square root primality test, consecutive composite positive integers, twin prime conjecture, prime number theorem (statement), Goldbach conjecture

Aug 31: Agreed first mid term: Wednesday September 16th 2015. Greatest common divisor introduced. Early properties and relation to integral linear combinations of integers. Extension to more than 2 integers (definition).

Sep 2: Euclidean algorithm (statement, proof and examples). Connection with linear combinations.

Sep 4: Euclid's lemma (p|ab) and its extension, Fundamental Theorem of Arithmetic (statement, proof and examples).

Sep 7: Labor Day. No class.

Sep 9: Solutions to HW1 distributed. Least common multiple, definition and properties, relation to fundamental theorem of arithmetic.

Sep 10: Email sent. No homework. Email sent. Practice midterm attached.

Sep 11: Statement of Dirichlet's theorem on primes in arithmetical progressions. Closing remarks on Chapter 1. Introduction to congruences (definition, some examples, elaborated examples, Fermat primes) and early properties.

Sep 12: Email sent. Solutions to midterm attached and some elaborations.

Sep 14: Solutions to HW2 distributed. More properties on congruences. Residue classes. Complete residue classes (examples mod 4).

Sep 16: Midterm 1.

Sep 18: Main theorem on complete residue classes (connection with division algorithm). Definition of linear congruence in one variable, examples of solvable and non-solvable congruences. Incongruent solutions.

Sep 21: Full theory of the solutions of linear congruences in one variables (theorem, proof and example).

Sep 22: Email sent. Agreed second mid term: Wednesday October 21st 2015. Material covering only up to Friday 9th October.

Sep 23: Replaced by Amita Malik (inverse from congruence and introduction to Chinese Remainder Theorem).

Sep 25: Discussion of solutions of first midterm. Review of inverses and review and of CRT.

Sep 28: Wilson's theorem (statement, proof and example), discussion of primality testing.

Sep 30: Fermat's theorem (statement, proof and example). Carmichael numbers introduced.

Oct 2: Euler's theorem (statement, proof and example), its special case as Fermat's theorem. Reduced residue systems and connection to Euler totient function.

Oct 5: Introduction to arithmetical functions. Introduction to the Mobius function and recall of the Euler totient function. First properties of divisor sums of Mobius and Euler functions.

Oct 7: Summation and product formula for Euler totient function. Review of inclusion-exclusion principle.

Oct 9: Finalization of the proof of product formula for the Euler totient function. Introduction to multiplicative functions. Proof that Mobius function is multiplicative.

Oct 12: More arithmetical functions (divisor function, sum of divisors) and their multiplicativity. Connection to perfect numbers (statement of Euclid-Euler theorem)

Oct 14: Proof of the Euclid-Euler theorem on perfect numbers. Moebius inversion (statement and proof).

Oct 16: Examples of Moebius inversion. Exploration on Wolfram Mathematica (projector) of arithmetic functions and misc.

Oct 19: Midterm questions. Clarification of the proof of Euler's theorem. Introduction to quadratic congruences.

Oct 21: Midterm 2.

Oct 23: Discussion of solutions of second midterm. Third midterm agreed on November Friday 13th. Continuation of quadratic congruences.

Oct 26: Reduction of quadratic congruence with linear term to quadratic congruence without linear term.

Oct 28: The Legendre symbol. Euler's criteria for the Legendre symbol (statement, proof and examples) and useful properties.

Oct 30: Second supplementary law of the Legendre symbol (statement, proof and examples).

Nov 2: Application of second supplementary law to Legendre(2/p). Introduction to quadratic reciprocity law (statement and examples).

Nov 4: Einsestein's lemma for the proof of quadratic reciprocity (statement, proof and example). Proof of quadratic reciprocity law.

Nov 6: Introduction to primitive roots.

Nov 9: Continuation of primitive roots

Nov 11: Continuation of primitive roots (number of primitive roots)

Nov 13: Midterm 3 and solutions.

Nov 16: Continuation of primitive roots, existence for 1, 2, 4, p^a, 2p^a, where p is a prime

Nov 18: Continuation of primitive roots, existence for 1, 2, 4, p^a, 2p^a, where p is a prime

Nov 20: Continuation of primitive roots, existence for 1, 2, 4, p^a, 2p^a, where p is a prime

Nov 30: Continuation of primitive roots: exclusion of other primitive roots

Dec 2: Continuation of primitive roots: table of primitive roots

Dec 4: Introduction to group theory

Dec 7: Introduction to characters

Dec 9: Characters and number theory.

Dec 14: Final and solutions.

Back to main

#### General Information

### Announcements

- Wed August 8th: extended office hours 1-3 PM

#### Prerequisites

Math 53 and 54, officially, but some experience writing proofs and working with abstract concepts (e.g, 55, 110, 113, etc) will be very helpful.#### Textbook

"Introduction to The Theory of Numbers", 5th Ed., by Niven, Zuckerman, and Montgomery. The book is unfortunately rather expensive. You may use the 4th edition, which you can find much cheaper used. It omits some material that we will cover, but I will provide extensive notes so that you will not be at a disadvantage for using this older edition. I will also print out all HW problems for those of you using the older edition, to avoid any confusion.#### Grading

Grades will be calculated on a 600-point scale, as follows:- Midterm Exam - 180 points (30%)
- Final Exam - 180 points (30%)
- Quizzes - 30 points each. There will be five; your lowest score will be dropped. (20%)
- Homework - 20 points each. There will be seven assignments; your lowest score will be dropped. (20%)

You *must* take the final exam to pass the course. In the event of a serious medical emergency, you may miss the midterm if you have written documentation of your illness. However, in this case the final exam will then count for 60% of your grade.

#### Homework

Homework is due every Tuesday (except the first week) at the beginning of class. There are seven assignments in all. Late HW*will not*be accepted. I will drop the lowest HW score in case you have to miss one week for some reason.

There is a *lot* of homework in this class - it is essential that you start early each week. You should work with others, but please write the names of your collaborators at the top of the assignment. You must write clearly - points will be taken off if your explanations are confusing or illegible. When writing proofs, you must use complete sentences.

#### Exams

There are two exams, weighted equally at 30% each. They will be on July 18th and August 9th, in class, for two hours each. There are no make-up exams. If you miss the midterm, you must provide written evidence from a doctor of serious illness. In this case I will count your second exam at 60% instead.#### Lectures

Schedule of LecturesWe meet for two hours each session. The first fifty minutes will be a lecture. After a ten minute break, the second hour will be a problem session.

*Important*: The first half of the course is standard material. The second half of this course consists of extra topics, which vary depending on the instructor. I will focus on geometric and algebraic aspects, since this is where my own interests lie. This subject matter ties in nicely with an abstract algebra class, but I do not presume you have taken this class already. Some common topics that I *will not* cover are: analytic methods (Prime Number Theorem, Moebius Inversion Formula, etc.), and cryptography (there is a separate course for this if you're interested). These are beautiful areas of mathematics, also, and if you have a particular desire to see this material, you may want to wait and take the course in the fall, when the instructor's choices may differ from my own.

I will cover a few topics not covered in the text, so it essential that you attend every lecture. I will provide my notes below in pdf form for you to use as a reference, so you can focus on thinking more and writing less during the lectures. Also in my notes can be found definitions of terms not used in the textbook.

## One thought on “Homework Number Theory Problems”