Number Theory

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 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² = 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² = −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 Divisibility and Primes

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