# APPLICATIONS OF THE ORDER FUNCTION

In this lecture we will explore several applications of order functions including formulas
for GCDs and LCMs , a method of showing certain numbers are irrational, and counting the
number of zeros at the end of n!.

## 1. Review

We begin with a review of results from the previous lecture .

Definition 1. If m is a nonzero integer and if p is a prime, then Ordp(m) is the largest
integer k such that pk divides m.

Proposition 2. Let p be a prime and m be a nonzero integer. Then p | m if and only if
Ordp(m) > 0.

Proposition 3. Let m be a nonzero integer, and p be a prime. Then Ordp(m) = k if and
only if m = upk for some u relatively prime to m.

Proposition 4. If p is a prime and u is an integer such that p u, then Ordp(upk) = k.

Proposition 5. Let p be a prime. If a, b ∈ Z are non-zero then

Ordp(ab) = Ordp(a) + Ordp(b):

More generally, if each is nonzero then

Ordp(a1… an) = Ordp(a1) +… + Ordp(an):

Proposition 6. If a ∈ Z is non-zero and if k ≥ 0 then

Ordp(ak ) = k Ordp(a):

Proposition 7. Suppose are distinct primes. Then

Proposition 8 (Product formula). Let n be a positive integer, and let be a nite
sequence of distinct primes that includes every prime divisor of n . Then

Exercise 1. Let n be a positive integer . Show that n is a perfect square if and only if
2 | Ordp(n) for all primes p. Hint: one direction uses the product formula.

## 2. Additional Results

Here are a few useful formulas involving order.

Proposition 9. If n ∈ Z is nonzero, and p is a prime, then

Ordp(-n) = Ordp(n):

Proposition 10. Suppose m and n are positive integers. If Ordp(m) = Ordp(n) for all
primes p, then m = n.

Proof. Let be a finite sequence of distinct primes that include all primes dividing
m and n. By the product formula

The connection between the order functions and divisibility is described by the following
theorem.

Theorem 11. Suppose m, n ∈ Z are both non-zero. Then

m | n   if and only if   Ordp(m) ≤ Ordp(n) for all primes p.

Remark. Since Ordp(m) = Ordp(n) = 0 for all p not dividing m and n, we only need to check
the right-hand condition for p dividing m or dividing n.

Proof. Suppose m | n. Then n = ml for some l ∈ Z. So Ordp(n) = Ordp(m) + Ordp(l) for
all primes p. This implies that Ordp(m) ≤ Ordp(n) for all primes p.

Now suppose that Ordp(m) ≤ Ordp(n) for all primes p. First assume that m and n are
positive. Let be a nite sequence of distinct primes that includes all prime divisors
of m and n. Let and By assumption, Define l ∈ Z by
the formula

By Proposition 7, Thus, for all pi in the sequence

For p not in the sequence,

Ordp(ml) = Ordp(m) + Ordp(l) = 0 + 0 = 0 = Ordp(n):

By Proposition 10, ml = n. So m | n as desired.

If m and n are not both positive, then Ordp(|m|) Ordp(|n|) for all primes p (Proposi-
tion 9). Thus |m| | |n| by the above argument. But |m| | |n| implies that m | n.

Corollary 12. Suppose a, b, d ∈ Z are non-zero. Then d is a common divisor of a and b if
and only if Ordp(d) ≤ min (Ordp(a), Ordp(b)) for all primes p.

Corollary 13. Suppose a and b are non-zero integers. Let be a finite sequence of
distinct primes that include all divisors of a and b. Then

where
Proof. Let Proposition 7 and definition of ni,

for all pi in the finite sequence, and Ordp(g) = 0 for other p. Thus

Ordp(g) = min (Ordp(a), Ordp(b))

for all primes p. By Corollary 12, g is a common divisor .

Suppose d is any other positive divisor. By Corollary 12,

Ordp(d) ≤ min (Ordp(a), Ordp(b)) = Ordp(g)

for all primes p. Thus d | g by Theorem 11. Thus d ≤ g. This shows that g is the greatest
common divisor .

## 3. Least common multiplies (LCM)

We start with a criterion for a number to be a common multiple.

Proposition 14. Suppose a, b,m ∈ Z are non-zero. Then m is a common multiple of a
and b if and only if Ordp(m) ≥ max (Ordp(a), Ordp(b)) for all primes p.

Proof. If m is a common multiple of a and b , then a | m and b | m. By Theorem 11, this
means that Ordp(a) ≤ Ordp(m) and Ordp(b) ≤ Ordp(m) for all primes p. In other words,
Ordp(m) ≥ max (Ordp(a), Ordp(b)) for all primes p.

If Ordp(m) ≥ max (Ordp(a), Ordp(b)) for all primes p, then Ordp(a) ≤ Ordp(m) and
Ordp(a) ≤ Ordp(m). By Theorem 11, m is a common multiple of a and b.

Theorem 15. Suppose a and b are non-zero integers. Then there is a unique least common
positive multiple (LCM) M of a and b. Furthermore, an integer c is a common multiples of
a and b if and only if c is a multiple of M. The least common (positive) multiple M is given
by the formula

where is a finite sequence of distinct primes that include all divisors of a and b.
and

Proof. Let where ni and pi are as above. We will show that M has all the
desired properties. Obviously M is positive (closure under multiplication). By Proposition 7
and definition of ni,

for all pi in the finite sequence, and Ordp(g) = 0 for other p. Thus

Ordp(M) = max (Ordp(a), Ordp(b))

for all primes p. By the previous proposition , M is a common multiple.
Suppose c is any other common multiple. By Corollary 12,

Ordp(c) ≥ max (Ordp(a), Ordp(b)) = Ordp(M)

for all primes p. Thus M | c by Theorem 11. A similar argument shows that if M | c then
c is a common multiple. So c is a common multiple of a and b if and only if c is a multiple
of M.

In particular, if c is a positive common multiple, then M | c, so M ≤ c. Thus M is smaller
than any other common multiple. So M is a least common multiple. Uniqueness is obvious
(M ≤ M' and M' ≤ M implies M = M').

Here is an interesting formula relating LCM (a, b) and GCD(a, b) :

Theorem 16. Let a and b be positive integers. Then

LCM(a, b) GCD(a, b) = ab

Proof. For any prime p, let mp = Ordp(a) and np = Ordp(b). Then, by Corollary 13,
Theorem 15, and Proposition 7,

By the following lemma,

min(mp, np) + max(mp, np) = mp + np = Ordp(a) + Ordp(b)

Thus LCM(a, b) GCD(a, b) and ab have the same order (for all p). By Proposition 10, they
are equal.

Lemma 17. Let m, n ∈ Z. Then min(m, n) + max(m, n) = m + n.

Exercise 2. Prove the above lemma.

Remark. This lemma does not use any special properties of Z . In fact, it is true of m, n ∈ U
where U is any linearly ordered set, and + is any commutative binary operation on U.

This above theorem generalizes:

Proposition 18. Let a and b be non-zero integers. Then

LCM(a, b) GCD(a, b) = |ab|.

Proof. Apply Theorem 16 to |a| and |b|. Then use the following lemma.

Lemma 19. Let a and b be non-zero integers. Then

LCM(a, b) = LCM (|a|, |b|),  GCD(a, b) = GCD (|a|, |b|).

Exercise 3. Prove the above by showing that a and b have the same common divisors (and
multiples) as |a| and |b|.

 Prev Next