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:
https://pgadey.ca/teaching/2019-math-club/number-theory-training-talk/number-theory-training-talk.pdf (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: ,

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:
https://pgadey.ca/teaching/talks/cmc-2018-storer-calculus.pdf

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

donut

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.

SphericalRingSolid_800napring2

Tagged with: ,

Malin Christersson’s Cube Toy

Posted in Math by pgadey on 2018/07/11

cube-toy

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

rocky

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

Here is what Parker learned about the class!

(more…)

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.

20180414_182202

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