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

leave a comment