In my opinion, number theory is an extremely fascinating
subject. There is much crazy

number theory out there (ever heard of the Riemann Hypothesis?). Fortunately,
the stuff in

contest math is much simpler than that. It is mostly ignored in high school
curriculum, we

seem to like to do a lot of algebra and calculus. However, do not less this fool
you, number

theory is not nearly as “advanced” as those subjects. At the core, number theory
is very

simple. In fact, most of the time, the problems can be stated in very simple
terms and at

the same time, the tools we have are much more limited than in other subjects.
This is good

news and bad news. Good news is it doesn’t take long to learn the tools. Bad
news is it

requires much trickiness.

Now that the little introductory blurb is done. Let us go over some common
notation.

1. N,Z,Z_{p},Z/pZ,Q,Q0,R, and C We will take these to be the
natural numbers, integers,

p-adic integers, integers in mod p, rational numbers, irrational numbers, reals,
and

complex numbers respectively. Don’t worry about the p-adic numbers if you don’t

know what those are, that was just thrown in to warn some people of the real
standard

notations.

2. The above things are all systems or playgrounds. They
are where we are working.

Most of the time, in math class without even knowing it, we make the assumption

we are working in the reals. Sometimes, we venture into the complex numbers. For

example, what if I asked two simple questions:

• Solve for x: x^{2} = 1 Well the answer is, it depends.
What if I told you that 3 is

a solution? What if I told you, that indeed there are 4 solutions: x = 1, 3, 5,
7?

You would think I was crazy until you realized that I was working in mod 8.

• Solve for x: x^{2} = −1 What is the answer? You might be
more suspicious now.

In the reals there are no solutions! In fact, this is essentially the only
polynomial

equation that has no solutions in the reals. As soon as we add i to the reals,

we can solve this equation. We also happen to now be able to solve all such

equations. We have created the complex numbers! But I claim that in fact the

solutions could be x = 2, 3 You are probably on to me now. I’m talking about

mod 5! But maybe crazier than that, x = i, j, k, are also solutions. Working
with

quaternions (this is where those vectors and cross products and stuff come
from),

we have these solutions. Our ARML shirt was blatantly wrong last year, since

i * j = k which is certainly not real.

I hope you are all sufficiently confused now. Apparently,
an innocent polynomial

equation could have more than the degree number of solutions, no solutions, or
not

even make any sense at all. Fortunately, all you have to avoid all this
craziness is make

sure you specify the system you are working in. In that spirit, let us learn
some more

ways to specify the system you are in. If we put a little floating plus to the
right of

any of these symbols we get the positive numbers. Most of the time, we put a
little

cross floating to the right of these signs we get the same system with zero
removed.

For example N is essentially the same as
.
Also, sometimes you might see things

that look like R[x]. What this means, is we add x as an element to the reals and
see

what kind of system we get. In this case, we get polynomials. Another example is
that

R[i] is essentially the same as C. As you can tell all of these systems can be
related to

each other. It is extremely important to understand the relationships between
them.

In fact, I believe all of these systems can be based directly back to the
integers, so if

ever there is some sort of contradiction in math and the whole thing collapses,
we must

have gotten the integers wrong. All these systems have rules and we start
calling them

groups, rings, fields, etc. As you learn more math, I’m sure you will study them
if you

haven’t already. Maybe one day you’ll finally understand Druker’s shirt.
ring to

rule them all: {0}.

3. In general, variable names in math are actually quite
standard. For example, for some

reason w, x, y, z are useful as variables. Maybe the numbers at the beginning of
the

alphabet are used for constants most often. Often times, s, t, u, v are most
useful as

some sort of parameters. p is almost always a prime and in the case when we need

two primes, we either use subscripts or sometimes venture to use q. m, n are
often

generic integers, with m frequently used for mods and n for numbers. i, j, k are
most

useful as indices, but sometimes k gets used in division. q, r are obviously
related and

commonly related to division as quotient and remainder. These are not strict
rules,

but I have seen an instructor change all the ps in an equation to ms just
because we

pointed out it didn’t necessarily have to be prime.

Other notation and terminology will be explained as they
come up. As a note about

the general style of the lecture, it is bad. But beyond that, I am going to omit
most

proofs so as to not turn this into a textbook. If you have any questions, you
can always

talk to me personally.

**2.1 Preliminary Notions**

Most of us know what it means for something to divide
something else. However, for our

purposes, it is important to define exactly what it means. For a, b ∈
Z and a ≠ 0, we say

that adividesb iff
s.t. b = ka We write a|b to indicate that adividesb. a is called a

divisor of b and b is called a multiple of a. A prime p is prime iff it has
exactly two distince

postive divisors. Any other integer is composite except 1 and −1.

Here are two more concepts that most everybody is already
familiar with. The greatestcommondivisor

of two integers a, b(not both 0) is k = gcd(a, b) = (a, b) where
s.t. d|a, d|b , k ≥ d Two

integers a and b are relativelyprime or coprime, if (a, b) = 1. The
leastcommonmultiple

of integers a and b is defined as the smallest positive integral multiple of
both a and b. We

write it as lcm[a, b] = [a, b].

Work out for yourself this gcd and lcm junk for those
crazy numbers 0 and 1. Also, note

that these definitions can be generalized in many different ways. One way is by
defining gcd

and lcm for n numbers and the other is to generalize to different systems, not
the integers.

**2.2 Fundamental Theorem of Arithmetic**

There are several fundamental theorems that lead up to the
Fundamental Theorem of Arithmetic.

We will briefly cover them and omit the proofs.

**1. Division Algorithm** Most of you probably know how
to divide, but probably never

thought of it in this way. Thankfully given any two integers a and b with b ≠ 0,
you can

divide a by b. In more precise terms: Given a, b ∈ Z,
0 ≤ r < |b|.

We call a, b, q, and r the dividend, divisor, quotient, and remainder
respectively. This

is known as the division algorithm for unkown reasons.

**2. Bezout’s Identity** Using the division algorithm
we can solve an extremely interesting

question. Given two integers a and b, the equation ax + by = 1 has integers
solutions

iff (a, b) = 1. This is an extremely important idea that was on the AMC 12A as a

problem this year. Notice that this also implies that ax + by = d has solutions
for all

integer d. What d can you solve for if (a, b) ≠ 1?

**3. Euclid’s Lemma** This can be easily proven with
Bezout’s Identity. It states that if

a|bc and (a, b) = 1, then a|c This is an interesting and intuitive fact to know.
However

it is most useful in proving the final result.

**4. Fundamental Theorem of Arithmetic** This is also
known as unique factorization.

It states that given any integer n, it can be uniquely expressed as the product
of distinct

prime powers with a sign in front. Everybody’s been prime factoring since 4th
grade,

but now you know for sure that no matter how you do it, you’ll get the same
answer.

Using the fundamental theorem of arithmetic it is very
easy to see exactly some things

about gcds lcms. The gcd of two numbers will simply be the product of the
highest prime

powers that will divide both of the numbers. Just imagine lookin at the prime
factorizations

one prime at a time and just taking the minimum of the two prime powers in each
factorization.

The lcm of two numbers would simply be the max of the prime powers. Taking these

two results it is easy to conclude that (a, b) * [a, b] = ab