Quizzes are 50 minutes (a full class period). Closed book, no calculators. You must not collaborate or use other sources of help. You can use any correct method to solve a problem, but if it is not a method explained in the text or in class, be sure to explain your method fully so I can figure it out. If it is a method used in text or class, still keep it tidy and clear and in the expected format, so I can follow your arguments. Proofs should be written clearly with English sentences. The more clearly you present your work, the more likely I can assign partial credit.
Quiz Fri Feb 1st (Solutions)
- Describe and use the Euclidean algorithm to find the gcd, using either smallest positive or smallest absolute value remainders, showing your work.
- State and use the definitions of floor, divisibility, greatest common divisor (gcd), least common multiple (lcm)
- Prove propositions about floor, divisibility, gcd and lcm and their uses. Examples are given in the course notes (for example, the division algorithm and the “gcd replacement” proposition from class), the proofs for the Linear Diophantine Equations worksheet, as well as Propositions/Lemmas 0.14, 0.15, 0.18, 0.19, 0.26-0.31, 1.9-1.10, 1.18-1.19, or the proofs on your homework. I may ask these, variations on these, or novel proofs which are similar.
- State and prove general theorems about the solution of Linear Diophantine Equations (as on the worksheet or in the lecture summary which will follow).
- Solve Linear Diophantine Equations (finding all integer solutions to ax+by=c), demonstrating and explaining your process.
- Questions on the content of Chapter 0 and 1 in your textbook (with an emphasis on the topics above, but possibly covering anything).
Quiz Fri Feb 22nd – (Solutions)
- In general, you are responsible for anything covered in class, homework and the relevant portions of the textbook. The list below is to help you focus on the highlights, but it is not exhaustive.
- Chapters 2, entire, and Chapter 3, as much as we cover before the quiz.
- I may ask homework problems or variations on homework problems.
- The list below of topics may change over the next week to match what we cover or do not get to before Friday. Please reload this page.
- Prime factorizations of integers and rational numbers.
- The use of prime factorizations to prove facts about gcd, lcm etc., such as Corollary 2.24, 2.25 and similar.
- Prove every integer greater than 1 is divisible by a prime, and there are infinitely many primes.
- Euclid’s lemma, with proof.
- Basic facts about prime counting function, e.g. growth estimates (without proof).
- Proof of unique factorization in the integers, including all the lemmas that go into it.
- Theorem 2.27. Understand the proof from class; don’t need to reproduce it.
- Theorem 2.28 and proof (we gave an alternate proof in class).
- Compute sum of divisors functions, and Corollary 2.22, with proof.
- Theorem 2.31 and proof (we gave a formal proof in class).
- Define the rationals as equivalence classes on the Cartesian product of integers with integers. Know what needs to be checked and be able to verify it (e.g. it is an equivalence relation, sums are well-defined, etc.)
- Proof of unique reduced form for rationals.
- Basic proofs about whether sums/differences/products/quotients of irrationals/rationals are rational/irrational, and examples.
- Prove that certain n-th roots of rationals are irrational (general proof or specific examples).
- Prove that between any two real numbers, there is both a rational and an irrational number.
- The proof that there exist two irrational numbers a and b so that ab is rational.
- Constructible numbers will not be covered.
- Pythagorean triples, the basic construction (take a slope, get a triple and vice versa) and proof of the bijection we did in class. Be able to explain all the parts of the bijection, and know the formula.
- Commensurability (definition and ability to test it)
- Rational Root Theorem and its applications to irrationality (use it to prove certain numbers are irrational, e.g. Problem 3.9 on page 84 and Chapter 3, exercise 3).
- The notion of a mediant and of kissing fractions. Be able to develop the rationals on the real line via mediants and draw the Bubbles / Farey Tree / Rational Rays / Ford circles (decently well, but not necessarily expertly!) to explain the arrangement.
- Be able to find kissing fractions by changing the question into a Linear Diophantine Equation.
Quiz Fri Mar 15th – (Solutions)
- Every quiz is at least potentially cumulative. In this case, our previous quiz came in the middle of studying kissing fractions etc. So that material may reappear on this quiz, now that we have finished it.
- Be able to prove that the integers generate all reduced fractions via mediants (Theorem 3.21).
- Be able to state and prove Proposition 3.22 and Theorem 3.23 (Dirichlet’s Approximation Theorem).
- Be able to state Theorem 3.25 (Thue-Siegel-Roth Theorem), and use it to demonstrate that something is transcendental (we did an example with a power of 2 in class; you re-did this with powers of 10 in your homework).
- Modular arithmetic. Be able to do it reliably (e.g. filling out addition and multiplication tables), including knowing such things as when it is safe to simplify, that cancelling can be dangerous, and you can’t simplify exponents.
- Be able to be clever about modular computations so they can be done by hand (see Example 5.7, 5.8).
- Know what is meant by natural and minimal representatives.
- Definition of congruence modulo n, and the fact that it gives an equivalence relation. Be able to prove it gives an equivalence relation.
- Be able to state and prove that addition and multiplication are well-defined modulo n.
- Everything that is covered on our most recent worksheet up to the end of Section 5 of that worksheet (we will summarize this in class on Monday), including all the theorems.
- Be able to solve linear congruences (ax = b mod n) of all types (no solution, one solution, several solutions), be able to restate these problems as linear diophantine equations (so you need to review how to solve those), and be able to predict the number of solutions even without solving.
- Be able to show that a Diophantine equation has no solution by examining the equation modulo n for a well-chosen n.
- Definition of a multiplicative inverse, be able to find multiplicative inverses, and use them to cancel or simplify.
- Be able to produce novel proofs that rely on definitions and techniques that are familiar from class material.
Quiz Fri Apr 12th – (Solutions)
- Modular arithmetic in general, including how to find a multiplicative inverse, and do computations efficiently by hand, know when it is safe to cancel, etc.
- Be able to draw additive or multiplicative dynamics as on the worksheets and in the book.
- Definition of the additive or multiplicative order of an element.
- Definition 6.4.
- Fermat-Euler Theorem and Fermat’s Little Theorem, statements.
- Be able to use the Fermat-Euler Theorem to simplify computations.
- Be able to compute the Euler phi function for small numbers (where you can basically just count).
- Corollary 6.14 and its proof.
- Testing primality based on FLT and ROO (top of page 160 and Proposition 6.21 in book; or see Primality Testing worksheet). Be able to test primality in this way.
- Problems such as Problem 6.17 and 6.18.
- Definition of a discrete logarithm, ability to compute these (see our worksheets).
- Know where the discrete logarithm really lives (modulo what?) and why.
- Be able to describe and execute the Diffie-Hellman key exchange, or know what you need to compute to break it.
- Be able to prove that there are primitive roots modulo p, for p prime. Note that we deviated from the proof of the book, in order to give a self-contained proof (the proof in the book requires more background on polynomials from a previous chapter, namely the proof of Lemma 6.23 calls on Theorem 5.39; therefore, please obtain class notes or View the handout here.
- We will not cover Chinese Remainder Theorem.
Final Exam
- The final exam is cumulative. It will cover everything above, plus the following. It will have a small emphasis on the material since the last quiz.
- Chinese Remainder Theorem, statement and proof.
- Formulas for Euler’s phi (totient), in general, with proof. This includes proof of multiplicativity of phi (which uses Chinese Remainder Theorem).
- Compute Euler phi function.
- Applications of Chinese Remainder Theorem:
- to solve multiple linear congruences
- to solve other equations mod n
- to simplify complicated expressions mod n, e.g. last two digits of 3^3^5 as in class
- Lifting congruences (i.e. what does info mod n tell you about info mod nm?)
- Going down (i.e. what does info mod nm tell you about info mod n?)
- Lifting multiplicative inverses (there’s a general theorem Lemma 7.16; or you can use the method I demonstrated which motivated the theorem instead of memorizing; but you should be able to do this efficiently, not by exhaustive search through lifts)
- Wilson’s Theorem, statement and proof (there is a proof in the solutions to the last quiz, last problem).
- Definition of Quadratic Residue and Quadratic Non-Residue (0 doesn’t count as either) modulo an odd prime p.
- Notion of an a-partner and how this can be used to prove Euler’s Criterion.
- State and prove Euler’s Criterion for Squareness.
- The Legendre Symbol: definition, and why it is multiplicative.
- State and prove reciprocity for -1.
- State reciprocity for 2.
- State Quadratic Reciprocity for two odd primes p and q.
- Permutations: definitions of permutation, identity permutation, transposition, sign of permutation, braid representation, adjacent transposition, inversions
- Know basic facts about these definitions, i.e. Proposition 8.12, Lemma 8.13, Theorem 8.14, Corollary 8.15, Lemma 8.18, Theorem 8.19. Understanding the proofs is an excellent way to make sure you understand the definitions, since each proof is quick and easy in terms of those definitions. I may ask a small proof like this just based on the expectation that you can create it from your understanding of the definitions (i.e. I don’t expect you to memorize or need to memorize).
- Be able to decompose a permutation into transpositions (braid representation)
- Compute the sign of a permutation three ways: (a) by lengths of cycles (b) by decomposing as transpositions (c) by counting all inversions
- Give the proof of Zolotarev’s Lemma.
- Be able to use the Legendre Symbol and its properties (including multiplicativity, quadratic reciprocity (general, -1 and 2), reduce top modulo bottom), to compute the value of a large Legendre symbol by hand. For example, Problems 8.27, 8.28, 8.29, 8.30.
- You are not responsible for a proof of Quadratic Reciprocity in general (know just the -1 case only). You don’t need to know the funny bracket notations from that proof.
- Hint: Check out the Lectures page, where there are course notes for the last day which have a nice summary of some of this material.
- Hint: Since we didn’t have homework on the most recent material, here are some good computational exercises from the book that will prepare you well for the computational aspects of this material. Chapter 7, #1,2,3,4,6,7,8,9,11 and Chapter 8, #1,2,3.