English | Español

Try our Free Online Math Solver!

Online Math Solver

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


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