## Math Club Number Theory Training Session

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 1If we write for the statement “ divides .”

Formally, means for .

Question 2What is the largest such that is divisible by ? Idea: Find a factorization where is a small constant.

Fact 3The “divisors” of are all such that . We say is “prime” if its divisors are . We say that is “composite” if it is not prime.

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

Question 5Show that is irrational. Generalize!

Question 6Show that there are infinitely many primes. Euclid’s idea: Suppose there are finitely many and consider .

Question 7Show that there are arbitrarily large gaps between primes. That is, show that for any there are consecutive numbers which are all composite.

Question 8 (Germany 1995)Consider the sequence and . Show that this sequence contains infinitely many composite numbers.

**3. Congruence **

Fact 9 (The Division Algorithm)For any there is a unique pair such that and .

Fact 10We write if . For any there is \mbox{} such that . We say that “ is congruent to modulo ”. Congruence preserves the usual rules of arithmetic regarding addition and multiplication.

Question 11Suppose that has digits in decimal notation.

- Show that .
- Show that .
- Show that .
- Show that .

Question 12What are the last two digits of ?

Question 13Show that any perfect square is congruent to or . Conclude that no element of is a perfect square.

Question 14Show that 3 never divides .

**4. The Euclidean Algorithm **

Fact 15The “greatest common divisor” of and is:

Question 16Show that where and is the unique pair of numbers given by the division algorithm.

Question 17The Fibonacci numbers are defined so that , and for . Show that .

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 then the Euclidean algorithm takes at most steps to calculate . Check out this great write-up at Cut the Knot.

** 4.1. Parity **

Question 18Suppose that is odd and is a permutation. Show that the number

must be even.

Question 19A room starts empty. Every minute, either one person enters or two people leave. Can the room contain people after minutes?

Idea: Consider the “mod-3 parity” of room population.

**5. Contest Problems **

Question 20Show that is not an integer for any .

Idea: Consider the largest power . 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. . Prove that less than a tenth of them can be expressed in the form where , , and are positive integers.

Idea: None of , , or can be very big. For example, .

Question 22 (Rochester 2003)An -digit number is “-transposable” if and . For example, is -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 .

Find a number with a repeating decimal of length six.

Question 23Suppose that you write the numbers on the blackboard. You now proceed as follows: pick two numbers and , erase them from the board, and replace them with . Continue until there is a single number left. Does this number depend on the choices you made?

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

The handout for the talk is available here:

## MAT B41 — Week 12

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

- Khan Academy on triple integrals (Pt. 1).
- Khan Academy on triple integrals (Pt. 2).
- Kristal King on triple integrals.
- PatrickJMT on triple integrals.

**Suggested Exercises:**

- 6.1 Geometry of Maps from to : 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.

## Mock Final Exam!

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

## MAT B41 — Week 11

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

- Khan Academy on triple integrals (Pt. 1).
- Khan Academy on triple integrals (Pt. 2).
- Kristal King on triple integrals.
- PatrickJMT on triple integrals.

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

## MAT B41 — Week 10

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

- Khan Academy on constrained optimization.
- Eugene Khutoryansky on Double Integrals (after five minutes the video goes beyond our course).
- PatrickJMT on Changing Order of Integration (Pt.1)
- PatrickJMT on Changing Order of Integration (Pt.2)

**Geogebra Demonstrations:**

- Cavalieri’s Principle with Triangles by Irina Boyadzhiev
- Archimede’s Cone-Sphere Theorem by Brian Sterr

**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 bound by the parabolic cylinder and the planes , , and .*Final 2015*: Evaluate where is the region bounded by and for .*Final 2016*: Evaluate where is triangle with vertices , , and .*Final 2016*: Evaluate .

**Notes:**

## MAT B41 — Week 9

**Homework 4 (tex) is now available.**

**Additional resources:**

- Khan Academy on constrained optimization.
- Kristal King on Lagrange multipliers.

**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 on the closed triangular region in with vertices , , and .*Final 2015*: Find the maximum values of on the solid ball .*Final 2015*: Find the points on the intersection of the paraboloid and the plane that are closest and farthest from the origin.

**Notes:**

## MAT B41 — Week 8

**Parker comes back! Public lecture on Friday in IC 200 at 11am.**

**Additional resources:**

- Khan Academy on multivariate maxima and minima.
- Kristal King on local extrema.

**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 . Find and classify the critical points of .*Final 2016*: Let . Find and classify the critical points of .

**Notes:**

## MAT B41 — Week 7

**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

leave a comment