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

## Canada Math Camp — Storer Calculus

Posted in Math by pgadey on 2018/07/31

This slideshow requires JavaScript.

The handout for the talk is available here:

Tagged with: , , ,

## Homework #5 Question 4

Posted in Math by pgadey on 2018/07/20

Consider a solid ball of radius $R$. Cut a cylindrical hole, through the center of the ball, such that the remaining body has height $h$. Call this the donut $D(R,h)$. Use Cavalieri’s principle to calculate the volume of $D(R,h)$. Calculate the volumes of $D(25,6)$ and $D(50,6)$.

Several students have asked what $D(R,h)$ looks like. Here are some pictures that I found to illustrate the concept. The donut $D(R,h)$ is the region between the red sphere and blue cylinder. The golden balls below show various views of the donut. The donut should fit between the two planes $z=h/2$ and $z=-h/2$, so that it has total height $h$.

Tagged with: ,

Posted in Math by pgadey on 2018/07/11

I was looking through the Geogebra site and found this lovely applet Orthographic Projection by Malin Christersson.

This is a lovely tool for investigating one of my favourite facts about hexagons:

The area maximizing orthogonal projection of a cube is the regular hexagon.

It turns out that Malin has tonnes of awesome geometry stuff online!

Awesome math art!

Tagged with: , ,

## Public Talks for UTSC

Posted in Math by pgadey on 2018/07/05

## From Colourings to Fixed Points

The notes for the talk are available here.

## Uniform Convergence

The notes for the talk are available here.

Tagged with:

## MAT 134 — Post-Term Test #1 Survey

Posted in 2018 -- MAT 134, Math, Uncategorized by pgadey on 2018/05/31

Thank you for filling out MAT 134 Post-Term Test #1 Survey.

Here is what Parker learned about the class!

Tagged with: ,

## MAT 134 Survey Results

Posted in Math by pgadey on 2018/05/09
Tagged with:

## Final Poster Presentation Demo

Posted in Math by pgadey on 2018/04/29
Tagged with: ,

## String Figure Poster Sketch

Posted in Math by pgadey on 2018/04/19

We’re almost ready for our final string figure presentation on May 2nd.

Now we just have to put it all together!

Tagged with: ,

## Mathematical Knots and String Figures

Posted in Lecture Notes, Math by pgadey on 2018/04/01
Tagged with: , ,