this lecture, we’ll introduce the field of number theory
and the set Z of integers.
In subsequent lectures, we’ll begin to be less formal in our proofs and worry
less about making
explicit our as sumptions regarding the common functions + and ·. For example,
we’ll allow ourselves
to write a + b + c, not caring whether the formal ex pression is really (a + b) +
c or a + (b + c),
since associativity tells us these two expressions always evaluate in the same
way. After discussing
a variety of properties expressible using integers, we’ll then go back and show
how these properties
can actually be expressed just as well without really using Z at all. All
theorems about Z can be
expressed and proven using only the three initial axioms of N and some carefully
chosen definitions.
1. Number Theory
Loosely speaking, number theory is the study of the set of integers. Many topics
in number
theory deal only with positive integers , but some can be expressed in terms of
all integers in a more
transparent way. Many theorems in the field of Number theory have two
characteristic properties.
(1) They are very easy to state
(2) They are very difficult to prove
Because of these characteristics, many mathematicians choose to like number
theory, and many
choose to dislike it. In our treatment of number theory in this course, we will
try to state a lot of
theorems, and only prove the ones that are relatively easy. We’ll also try to
give some motivation
for why some of the easily-expressed statements are so difficult to prove.
2. The Integers
The set of integers Z can be informally defined as the set {· · · − 3,−2,−1, 0,
1, 2, 3 . . . }. We are
all familiar with the set of integers. They include the natural numbers together
with all the additive
inverses of natural numbers. Later in the course, we’ll show how we can
construct a copy of the
integers within the structure 
For now, we’ll just assume
that the integers come
equipped with the standard binary functions 
the additive inverse 1-ary
function −Z, and the
constants 
A list of the properties we’ll assume about Z is given below.
Later we’ll show how
we can avoid assuming these properties, and actually prove them from our axioms
about N.
Properties of integers:
(1) are associative and commutative, and the distributive property holds.
(2) For every 
(3) For every 
(4) For every 
(5) For every 
(6) For every a, b ∈ Z, and for every 
I’ll probably need to go back and edit this list later. Basically, we’ll assume
any of the standard
properties of +, ·, −, 0, and 1 with which you are familiar from grade school.
We will not assume
any properties of ÷ or admit to the existence of rational numbers . everything
we’ll do will involve
integers.
For now, we’ll proceed to discussing some real theorems
about integers, the first of which is the
division theorem.
3. The Division Theorem
The Division theorem is an essential result that is necessary to prove many of
the common
properties of integers involving any form of divisibility. For the next several
weeks, you will have
to use this theorem, so it might be a good idea to memorize it.
The Division Theorem:
For any m, n ∈ Z, with n > 0, there exists unique integers q, r ∈ Z such that
First we’ll give a motivation for the theorem. Then we’ll show how to formalize
it. Then we’ll
prove it.
3.1. motivating the division theorem. One way to think of the division theorem,
is that it’s
just a formalization in Z of the statement in Q that we can always express a
fraction uniquely as a
mixed number. For example, we can write 
as
, and we can write
as 
We can also
deal with negative numbers , since 
There is an algorithm for doing this. It’s called
long division. To write as a mixed number we divide 6 into 73,
and we get 12 with remainder 1. So
If we divide both sides of this equation by 6 we
get an expression involving no fractions, 73 = 6 · 12 + 1. In the above
algorithm, the number 73 is
called the dividend, 6 is called the divisor, 12 is called the quotient and 1 is
called the remainder.
The division theorem just says that for any integer dividend m, and non-zero
integer divisor n, we
can do long division to get a unique quotient q and remainder r. The equation m
= qn + r is just
a re-wording of the equation 
that says how
we would write 
as a mixed number. The
condition 0≤ r < n just expresses our halting condition for the long division
algorithm that says we
are not done until the last number at the bottom is smaller than our dividend.
When we’re done,
the last number at the bottom is r and our dividend is n, so 0 ≤r < n. While our
motivation for
this theorem involves fractions, the division theorem itself does not deal with
fractions, only with
integers; and our proof of it will need to use only integers as well.
3.2. formalizing the division theorem. Every part of the division theorem is
easily expressible
in first order logic except for the part that says ”unique”. To say that q, r
are unique with respect to
the two properties listed above means that if q', r' are any pair of integers
satisfying both properties,
then q' = q and r' = r.
We can formulate the division theorem using first order logic if we introduce
the ”unique existential”
quantifier 
. First, if P is any predicate in one variable x, then
is an
abbreviation for the sentence 
.
Similarly, if P is a
predicate in m variables 
then
is an abbreviation for
We just gave the definition for as a quantifier over the set Z, but the
definition is analogous
for N or any other set X in place of Z.
In this new notation, we can formally express the division
theorem as the following first order
sentence.
4. Exercises
These exercises will be due Wednesday, February 23.
(1) Modify the example in the lecture notes involving the Well-Ordering
Principle, to prove
that
is irrational whenever s is not a perfect square (i.e. not the square of any
natural
number). [You may assume as hypotheses any of the arithmetic and ordering
properties of
rational numbers].
(2) Show that the usual definition of the choose function in terms of factorials
satisfies the recursive condition
[Hint: You don’t need to use induction,
just algebra . (Various versions of the recursive condition above are often
referred to as the
Addition Formula for Binomial Coefficients )].
(3) What is the coefficient of x 10 in the expansion of (x + 3)12? [Hint: Use the
Binomial
Theorem].
(4) Use telescoping sums to derive a formula for the sum of the first n cubes,
(5) Suppose that f : N →N is a function satisfying the following two
properties.
• 
• The range of f is finite, and contains exactly n elements.
(a) Show that f(0) = 0 [Hint: At some point, you will need to use the fact that
0 + 0 = 0,
and also the cancellation law for addition].
(b) Show that 
[Hint: pigeonhole principle]
(c) Show that 
[Hint: Fix a, b ∈ N satisfying the
property
above. Either a < b or b < a. Use the c you get from the definition of <.]
(d) How many different natural numbers c must satisfy f(c) = 0? [Hint: If f(c) =
0, what
is f(c + c) and f(c + (c + c))?]
(e) Show that if f(c) = 0 and b = a + c, then f(a) = f(b)
(f) Show that if k ∈ N and 0 < k < n, then f(k) ≠ 0. [Hint: you may need to use
some
form of proof by contradiction here].
(g) What must be the value of f(n)? [Give a proof along with your answer].
(h) Suppose that f(1) = m. Give a description of the elements in the range of f
in terms
of m and n.
