# Lecture VII - Number Theory

Number theory encompasses anything relating to properties of integers. In
contests, we

typically encounter problems involving divisibility and factorization. In this
lecture we will

let p_{1}, p_{2}, . . . represent the prime numbers in ascending order so that p_{n} is
the nth prime

number. We let gcd(p, q) represent the greatest common denominator and let lcm(p,
q) the

least common multiple of integers p and q.

## 1 Divisibility and Factoring

The Fundamental Theorem of Arithmetic says that any positive integer n can be
represented

in exactly one way as the product of prime numbers, so that the factorizations
of p and q

are identical if and only if p = q.

The number f divides n if and only if none of the powers of the primes in the
factorization

of f are greater than those of n. Specifically, f divides n k times if and only
if there is no

prime p is the factorization of f that appears more than 1/k times as often as
it appears in

the factorization of n.

On a related note, if some integer f divides integers p and q, then f divides
mp + nq,

where m and n are any integers.

Quick question: How many times does 3 divide 28!?

We reason that the answer is the sum of how many times 3 divides each of 1,
2, . . . , 28. Of the

numbers 1 through 28, exactly
a multiples of 3,
are multiples of 3^2, etc. (where

is the floor function and represents the greatest integer less than or equal to
x). To count the

total number of p’s appearing in their factorizations, we compute 9+3+1+0+0+0+·
· · = 13.

The generalized result:

Theorem : Aprime number p divides n! exactly times.

This fact enables us to determine how many 0’s appear at the end of n!.
Because there

are more 2’s than 5’s in the factorization of n!, the number of 0’s at the end
of n! is the

number of 5’s in its factorization.

Quick question: How many factors does 120 have?

We factor 120 and find that 120 =
.
Therefore, any m =
that

divides 120 must satisfy
.
There are 4 possible m_{1}, 2

possible m_{2}, and 2 possible m_{3}, meaning that there are 4 · 2 · 2 = 16 positive
integers that

divide 120. Moreover:

Theorem : factors.

The greatest common divisor of m and n is defined to be the largest integer
that divides

both m and n. Two numbers whose largest common divisor is 1 are called
relatively prime

even though neither m nor n is necessarily prime. There are two notable ways to
compute

gcd(m, n).

• Factoring - Let
such that

0. Then gcd(m, n) is the positive integer whose prime factorization contains p_{i}
exactly

min(m_{i}, n_{i}) times for all positive integers i. Remark - This is useful if the
factorizations

of m and n are readily available, but if m and n are large numbers such as 4897,
they

will be difficult to factor.

• Euclidean Algorithm - Let n > m. If m divides n, then
gcd(m, n) = m. Otherwise,

gcd(m, n) = gcd(m, n − m · ). Remark - This
is useful when factoring

fails. For example, finding gcd(4897, 1357). 1357 does not divide 4897, so
= 3,

4897 − 3 · 1357 = 826 and gcd(4897, 1357) = gcd(1357, 826). 826 does not divide

1357, so gcd(1357, 826) = gcd(826, 531). 531 does not divide 826 so gcd(862,
531) =

gcd(531, 295). Continuing this process, gcd(531, 295) = gcd(295, 236) = gcd(236,
59) =

59.

The least common multiple of m and n is defined to be the
least number that is divisible

by both m and n. Other than listing multiples of m and n, we can determine the
lcm by the

formula : lcm(m, n) = . Note that because
gcd(m, n) ≥ 1, we have lcm(m, n) ≤ mn.

The Euler Phi function, ,
denotes the number of positive integers less than or equal

to n that are relatively prime to n. If we let
denote all of the distinct prime

numbers that divide p, then:

## 2 Modulo Trickery

The division algorithm states that when dividing n by p ≠
0, there is exactly one integer q

such that n = pq + r, where . We define n
modulo p (or simply m mod p) to be

r in this equation . We use the notation r n
(mod p) when solving equations . There are

a number of theorems that apply to modulos, some of which are outlined here:

• k · n + c c (mod n),
for any integers k, n, and c. This follows from the definition

of modulos.

• (mod n), for any
integers k, n, and c, and any positive integer m.

This is the result of binomial expansion of the left side.

• (mod p), for
relatively prime integers a and p, where p is prime. A result

known as Fermat’s Little Theorem.

• (mod n), for any
relatively prime integers a and n, where is
the Euler

Phi function. This is Euler’s Generalization of Fermat’s Little Theorem.

• (p − 1)! −1 (mod p), for any prime p. This is Wilson’s Theorem.

Whenever the word remainder appears, you should
immediately think modulos. Likewise,

determining the last few digits of a number should make you consider modulos.

The above theorems are merely suppliments to the algebra
that can be performed on

modular equations, which we outline here. The rules of modular arithmetic can be
summarized

as follows:

1. The only numbers that can be divided by m in modulo n
are those that are multiples

of gcd(m, n).

2. When multiplying by m in modulo n, the only numbers
that can result are multiples

of gcd(m, n).

3. Taking the square root of both sides is “normal” only
in prime modulos. (For example,

the solutions to (mod 8) are not only
(mod 8) but more completely

(mod 8).)

4. When solving for integer solutions in modulo n, any
integer multiple of n can be added

to or subtracted from any number. (This includes adding multiples of n to square
roots

of negative numbers.)

5. All other operations behave normally according to the
standard rules of algebra over

the integers.

Consider, for example, solving for all positive n ≤ 100
for which is divisible by

43. Of course we set up (mod 43). We apply
the quadratic formula and

find that (mod 43). Because −123
−123 + 43k (mod 43), we replace

-123 with −123 + 5 · 43 = 49 and continue:
(mod 43), so n 3,−4 (mod 43).

Therefore, all such n are 3, 39, 46, 82, and 89.

## 3 Practice

All of the following problems can be solved with the techniques enumerated above.

1. How many factors does 800 have?

2. How many times does 7 divide 100!?

3. What is the smallest positive integer n for which
is non-zero and reducible?

4. In Mathworld , the basic monetary unit is the Jool, and
all other units of currency are

equivalent to an integral number of Jools. If it is possible to make the
Mathworld

equivalents of $299 and $943, then what is the maximum possible value of a Jool
in

terms of dollars ?

5. What are the last three digits of

6. Compute the remainder when 2000! is divided by 2003.

7. (ARML 1999) How many ways can one arrange the numbers
21, 31, 41, 51, 61, 71, and

81 such that any four consecutive numbers add up to a multiple of 3?

8. Determine all positive integers n ≤ 100 such that is divisible by 73.

Prev | Next |