Parker Glynn-Adey

Math Club Number Theory Training Session

Posted in Lecture Notes, Math by pgadey on 2019/01/31

These are some questions that I prepared for Math Club. The problems follow Paul Zeitz’s excellent book The Art and Craft of Problem Solving. You can find this hand-out is here: (tex)

1. Advice and Suggestions

  • Try out lots of examples.
  • The small numbers are your friends.

2. Facts and Questions

Fact 1 If {a, b \in \mathbb{Z}} we write {a | b} for the statement “{a} divides {b}.”
Formally, {a|b} means {b = ka} for {k \in \mathbb{Z}}.

Question 2 What is the largest {n} such that {n^3 + 100} is divisible by {n+10}? Idea: Find a factorization {n^3+100 = (n+10)( ... ) \pm C} where {C} is a small constant.

Fact 3 The “divisors” of {k} are all {d} such that {d | k}. We say {p} is “prime” if its divisors are {\{1, p\}}. We say that {k} is “composite” if it is not prime.

Fact 4 (Fundamental Theorem of Arithmetic) Any natural number {n} is a product of a unique list of primes.

Question 5 Show that {\sqrt{2}} is irrational. Generalize!

Question 6 Show that there are infinitely many primes. Euclid’s idea: Suppose there are finitely many {\{ p_1, p_2, \dots, p_n\}} and consider {N = p_1 p_2 \dots p_k + 1}.

Question 7 Show that there are arbitrarily large gaps between primes. That is, show that for any {k} there are {k} consecutive numbers {n, n+1, \dots, n+k} which are all composite.

Question 8 (Germany 1995) Consider the sequence {x_0 = 1} and {x_{n+1} = ax_n + b}. Show that this sequence contains infinitely many composite numbers.

3. Congruence

Fact 9 (The Division Algorithm) For any {a, b \in \mathbb{N}} there is a unique pair {(k,r)} such that {b = ka + r} and {0 \leq r < a}.

Fact 10 We write {a \equiv b \mod n} if {n | (a-b)}. For any {a \in \mathbb{Z}} there is \mbox{{r \in \{0, 1, \dots, n-1\}}} such that {a \equiv r \mod n}. We say that “{a} is congruent to {r} modulo {n}”. Congruence preserves the usual rules of arithmetic regarding addition and multiplication.

Question 11 Suppose that {n} has digits {n = [d_1 \dots d_k]} in decimal notation.

  1. Show that {n \equiv d_1 + d_2 + \dots + d_k \mod 9}.
  2. Show that {n \equiv d_k \mod 10}.
  3. Show that {n \equiv \sum_{k=0}^n (-1)^k d_k \mod 11}.
  4. Show that {n \equiv [d_{k-1}d_k] \mod 100}.

Question 12 What are the last two digits of {7^{40001}}?

Question 13 Show that any perfect square {n^2} is congruent to {0} or {1 \mod 4}. Conclude that no element of {\{11, 111, 1111, \dots\}} is a perfect square.

Question 14 Show that 3 never divides {n^2 + 1}.

4. The Euclidean Algorithm

Fact 15 The “greatest common divisor” of {a} and {b} is:

\displaystyle  \gcd(a,b) = \max\{ d : d|a \textrm{ and } d|b \}

Question 16 Show that {\gcd(a,b) = \gcd(a,r)} where {b = ak + r} and {(k,r)} is the unique pair of numbers given by the division algorithm.

Question 17 The Fibonacci numbers are defined so that {F(1) = 1, F(2) = 1}, and {F(n) = F(n-1) + F(n-2)} for {n>2}. Show that {\gcd(F_n, F_{n-1}) = 1}.

The Fibonacci numbers have the following curious property: Consecutive Fibonacci numbers are the worst-case scenario for the Euclidean Algorithm. In 1844, Gabriel Lamé showed: If {a \leq b \leq F_n} then the Euclidean algorithm takes at most {n} steps to calculate {\gcd(a,b)}. Check out this great write-up at Cut the Knot.

4.1. Parity

Question 18 Suppose that {n = 2k + 1} is odd and {f : \{1, 2, \dots, n\} \rightarrow \{1, 2, \dots, n\}} is a permutation. Show that the number

\displaystyle  (1 - f(1))(2 - f(2)) \dots (n - f(n))

must be even.

Question 19 A room starts empty. Every minute, either one person enters or two people leave. Can the room contain {2401} people after {3000} minutes?
Idea: Consider the “mod-3 parity” of room population.

5. Contest Problems

Question 20 Show that {\displaystyle 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}} is not an integer for any {n > 1}.

Idea: Consider the largest power {2^k < n}. Divide out by this largest power. This will make all of the denominators odd. (In fancy number theory terms, you’re using a 2-adic valuation.)

Question 21 (Rochester 2012) Consider the positive integers less than or equal to one trillion, i.e. {1 \leq n \leq 10^{12}}. Prove that less than a tenth of them can be expressed in the form {x^3 + y^3 + z^4} where {x} , {y} , and {z} are positive integers.

Idea: None of {x}, {y}, or {z} can be very big. For example, {x < \sqrt[3]{10^{12}} = 10^4}.

Question 22 (Rochester 2003) An {n}-digit number is “{k}-transposable” if {N = [d_1 d_2 \dots d_n]} and {kN = [d_2 d_3 \dots d_n d_1]}. For example, {3 \times 142857 = 428571} is {3}-transposable. Show that there are two 6-digit numbers which are 3-transposable and find them.

\noindent Big Idea: Consider repeating decimal expansions.
Observe that {10 \times 0.[d_1 d_2 d_3 \dots] = d_1 . [d_2 d_3 d_4 \dots]}.
Find a number with a repeating decimal of length six.

Question 23 Suppose that you write the numbers {\{1, 2, \dots, 100\}} on the blackboard. You now proceed as follows: pick two numbers {x} and {y}, erase them from the board, and replace them with {xy + x + y}. Continue until there is a single number left. Does this number depend on the choices you made?

Tagged with: ,

Science Unlimited — Knot Theory and Cat’s Cradle: A Brief Introduction to Storer Calculus

Posted in Lecture Notes by pgadey on 2018/08/14

This slideshow requires JavaScript.

The handout for the talk is available here:

Tagged with: , , ,

MAT B41 — Final Exam Details

Posted in 2018 -- MAT B41 by pgadey on 2018/08/01


MAT B41 — Week 12

Posted in 2018 -- MAT B41, Lecture Notes by pgadey on 2018/07/31
You made it to the last week! You’re done!

On Homework 5, you solved the Napkin Ring Problem. Check it out! That is super cool!

Additional resources:

Suggested Exercises:

  • 6.1 Geometry of Maps from \mathbb{R}^2 to \mathbb{R}^2: 1, 3, 6, 11
  • 6.2 The Change of Variables Theorem: 3, 4, 7, 10, 11, 21, 23, 26, 28
  • 6.3 Applications : 1, 3, 4, 5, 6, 11, 13, 16


The notes are available here.

Tagged with: ,

Mock Final Exam!

Posted in 2018 -- MAT B41 by pgadey on 2018/07/28
The Mock Final is now available!

Thanks everyone, who came out and wrote today! We had about thirty people in total. The last writer finished at approximated 14:50pm. It seems like the final will take approximately three hours. Please attempt the mock final, it is the best preparation for the real final.

Tagged with: , ,

MAT B41 — Week 11

Posted in 2018 -- MAT B41, Lecture Notes by pgadey on 2018/07/24


(Archimedes Thoughtful by Domenico Fetti 1620 from Wikimedia)
Homework 5 is due! Homework 6 (tex) is now available!

The Mock Midterm will be Friday July 27 in SY110 from 12–3pm.

Additional resources:

Suggested Exercises:

  • 5.4 Changing the Order of Integration: 2,3,7,9,14
  • 5.5 The Triple Integral: 1,3,4,9,10,11,12,16,18,20,21


Tagged with: ,

MAT B41 — Week 10

Posted in 2018 -- MAT B41, Lecture Notes by pgadey on 2018/07/17
(Photo by Ian Alexander) Homework #5 (tex) is available. Drop deadline next Monday.

There has been a minor change to the syllabus: Homework 6 will now be assigned in Week 11 and due in Week 12.

Additional resources:

Geogebra Demonstrations:

Suggested Exercises:

  • 5.1 Introduction to Double and Triple Integrals: 1,2,3,8,9,13
  • 5.2 The Double Integral over a Rectangle: 1,2,3,4,5,6
  • 5.3 The Double Integral over a More General Regions: 1,2,3,7,13

Past Finals:

  • Final 2015: Find the volume of the solid B bound by the parabolic cylinder x = (y-4)^2 + 3 and the planes z=x+2y-4, z=x+4y-7, and x+2y=11.
  • Final 2015: Evaluate \int_D e^{x+y} dA where D is the region bounded by y=x-1 and y=12-x for 2 \leq y \leq 4.
  • Final 2016: Evaluate \int_D (1-2x) dA where D is triangle with vertices (0,0), (2,3), and (5,3).
  • Final 2016: Evaluate \int_0^1 \int_x^{\sqrt[3]{x}} e^{x/y} dy dx.


Tagged with: ,

MAT B41 — Week 9

Posted in 2018 -- MAT B41, Lecture Notes by pgadey on 2018/07/10

Homework 4 (tex) is now available.

Additional resources:

Suggested Exercises:

  • 3.4 Constrained Extrema and Lagrange Multipliers: 1a, 3, 4, 5, 13, 14, 15, 19, 20, 28

Past Finals:

  • Final 2016: Find the minimum value of f(x,y) = 4x^2y - x^3y - x^2y^2 on the closed triangular region in \mathbb{R}^2 with vertices (0,0), (6,0), and (0,6).
  • Final 2015: Find the maximum values of f(x,y,z) = x^2 - 4x + y^2 - 2y + z^2 - 4z - 1 on the solid ball x^2 + y^2 + z^2 \leq 9.
  • Final 2015: Find the points on the intersection of the paraboloid z=x^2+y^2 and the plane x+y+z=1 that are closest and farthest from the origin.


Tagged with: ,

MAT B41 — Week 8

Posted in 2018 -- MAT B41, Lecture Notes, Uncategorized by pgadey on 2018/07/03
Parker comes back! Public lecture on Friday in IC 200 at 11am.

Additional resources:

Suggested Exercises:

  • Course Notes: Quadratic forms and determinants
  • 3.3 Extrema of Real-Valued Functions: 1,2,3,11,13,21,29,31,52

Past Finals:

  • Final 2015: Let f(x,y,z) = x^3 + x^2 + y^2 + z^2 - xy - zx. Find and classify the critical points of f.
  • Final 2016: Let f(x,y,z) = z^3 - x^2 + y^2 - 6yz + 4x + 4y + 6z + 1. Find and classify the critical points of f.


Tagged with: ,

MAT B41 — Week 7

Posted in 2018 -- MAT B41, Lecture Notes, Uncategorized by pgadey on 2018/06/26
Midterms are graded! New list of suggested exercises is available!

There is a new list of suggested exercises available here.

Suggested Exercises

  • Chapter 1 Review (p. 71): 1, 4, 5, 7, 8, 16, 18, 20
  • Chapter 2 Review (p. 145): 1, 2, 3, 5, 6, 10, 15, 25
Tagged with: ,