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 1 If
we write
for the statement “
divides
.”
Formally,means
for
.
Question 2 What is the largest
such that
is divisible by
? Idea: Find a factorization
where
is a small constant.
Fact 3 The “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 5 Show that
is irrational. Generalize!
Question 6 Show that there are infinitely many primes. Euclid’s idea: Suppose there are finitely many
and consider
.
Question 7 Show 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 10 We 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 11 Suppose that
has digits
in decimal notation.
- Show that
.
- Show that
.
- Show that
.
- Show that
.
Question 12 What are the last two digits of
?
Question 13 Show that any perfect square
is congruent to
or
. Conclude that no element of
is a perfect square.
Question 14 Show that 3 never divides
.
4. The Euclidean Algorithm
Fact 15 The “greatest common divisor” of
and
is:
Question 16 Show that
where
and
is the unique pair of numbers given by the division algorithm.
Question 17 The 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 18 Suppose that
is odd and
is a permutation. Show that the number
must be even.
Question 19 A 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 20 Show 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 23 Suppose 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