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 Ord_{p}(m) is the largest
integer k such that p^{k} divides m.
Proposition 2. Let p be a prime and m be a nonzero
integer. Then p  m if and only if
Ord_{p}(m) > 0.
Proposition 3. Let m be a nonzero integer, and p be
a prime. Then Ord_{p}(m) = k if and
only if m = up^{k} for some u relatively prime to m.
Proposition 4. If p is a prime and u is an integer such that p u, then Ord_{p}(up^{k}) = k.
Proposition 5. Let p be a prime. If a, b ∈ Z are nonzero then
Ord_{p}(ab) = Ord_{p}(a) + Ord_{p}(b):
More generally, if each is nonzero then
Ord_{p}(a_{1}… a_{n}) = Ord_{p}(a_{1}) +… + Ord_{p}(a_{n}):
Proposition 6. If a ∈ Z is nonzero and if k ≥ 0 then
Ord_{p}(a^{k} ) = k Ord_{p}(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  Ord_{p}(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
Ord_{p}(n) = Ord_{p}(n):
Proposition 10. Suppose m and n are positive integers. If Ord_{p}(m) = Ord_{p}(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 nonzero. Then
m  n if and only if Ord_{p}(m) ≤ Ord_{p}(n) for all primes p.
Remark. Since Ord_{p}(m) = Ord_{p}(n) = 0 for all p not dividing m and n, we only need
to check
the righthand condition for p dividing m or dividing n.
Proof. Suppose m  n. Then n = ml for some l ∈ Z. So Ord_{p}(n) = Ord_{p}(m) + Ord_{p}(l)
for
all primes p. This implies that Ord_{p}(m) ≤ Ord_{p}(n) for all primes p.
Now suppose that Ord_{p}(m) ≤ Ord_{p}(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 p_{i} in the sequence
For p not in the sequence,
Ord_{p}(ml) = Ord_{p}(m) + Ord_{p}(l) = 0 + 0 = 0 = Ord_{p}(n):
By Proposition 10, ml = n. So m  n as desired.
If m and n are not both positive, then Ord_{p}(m) Ord_{p}(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 nonzero. Then d is a common divisor of a
and b if
and only if Ord_{p}(d) ≤ min (Ord_{p}(a), Ord_{p}(b)) for all primes p.
Corollary 13. Suppose a and b are nonzero
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 n_{i},
for all p_{i} in the finite sequence, and Ord_{p}(g) = 0 for other p. Thus
Ord_{p}(g) = min (Ord_{p}(a), Ord_{p}(b))
for all primes p. By Corollary 12, g is a common divisor .
Suppose d is any other positive divisor. By Corollary 12,
Ord_{p}(d) ≤ min (Ord_{p}(a), Ord_{p}(b)) = Ord_{p}(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 nonzero. Then m is a common multiple of
a
and b if and only if Ord_{p}(m) ≥ max (Ord_{p}(a), Ord_{p}(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 Ord_{p}(a) ≤ Ord_{p}(m) and Ord_{p}(b) ≤ Ord_{p}(m) for all primes p. In other words,
Ord_{p}(m) ≥ max (Ord_{p}(a), Ord_{p}(b)) for all primes p.
If Ord_{p}(m) ≥ max (Ord_{p}(a), Ord_{p}(b)) for all primes p, then Ord_{p}(a)
≤ Ord_{p}(m) and
Ord_{p}(a) ≤ Ord_{p}(m). By Theorem 11, m is a common multiple of a and b.
Theorem 15. Suppose a and b are nonzero 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 n_{i} and p_{i} 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 n_{i},
for all p_{i} in the finite sequence, and Ord_{p}(g) = 0 for other p. Thus
Ord_{p}(M) = max (Ord_{p}(a), Ord_{p}(b))
for all primes p. By the previous proposition , M is a common multiple.
Suppose c is any other common multiple. By Corollary 12,
Ord_{p}(c) ≥ max (Ord_{p}(a), Ord_{p}(b)) = Ord_{p}(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 m_{p} = Ord_{p}(a) and n_{p} = Ord_{p}(b). Then, by Corollary
13,
Theorem 15, and Proposition 7,
By the following lemma,
min(m_{p}, n_{p}) + max(m_{p}, n_{p}) = m_{p} + n_{p} = Ord_{p}(a) + Ord_{p}(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 nonzero 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 nonzero 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 