## 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:

• 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!

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

Notes:

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.

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

Notes:

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.

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$.

Notes:

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.

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.

Notes:

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.

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$.

Notes:

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: ,