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