APPLICATIONS OF THE ORDER FUNCTION

4. Ir rationality Theorem

In this section we will see that is irrational unless n is a kth power. For example,
is irrational since 5 is not a square, is irrational since 4 is not a cube , is irrational
since 10 is not a 5th power. We will also see an example of how to show certain logarithms
are irrational.

One problem with these results is that they are not phrased in terms of integers . They
appeal to certain real numbers and assert that these number are not in Q. Fortunately we
can convert these results into number theory problems.

Begin by supposing that is rational, and can be written as a/b. Then
Thus nb^k = a^k. In other words, the equation ny ^k = x^k has a solution with positive x , y.
Conversely, any solution to to ny^k = x^k with x, y positive integers gives a fraction x/y for
the root So we can rephrase the problem of showing is irrational to the problem
of showing that ny^k = x^k has no solution with x, y positive integers.

We begin with a couple illustrations. Then we consider the general theorem.

Theorem 20. The equation x² = 5y² has no positive integer solutions. In other words,
is irrational.

Proof. Suppose otherwise, that 5y² = x² has solution x₀, y₀. So Thus

This implies that

The left hand side is an even integer, the right hand side is an odd integer. Contradiction.

Theorem 21. The equation x³ = 2y³ has no positive integer solutions. In other words,
is irrational.

Proof. Suppose otherwise, that x³ = 2y³ has solution x₀, y₀. So Thus

This implies that

3 Ord₂(x₀) = Ord₂(2) + 3 Ord₂(y₀) = 1 + 3 Ord₂(y₀)

The left hand side is divisible by three , but the right hand side is not. Contradiction.

Theorem 22. Suppose n is a positive integer and that n is not of the form m^k with m ∈ Z.
Then ny^k = x^k has no positive integer solutions. In other words, is irrational unless n
is a kth power.

Proof. Suppose otherwise, that ny^k = x^k has solution x₀, y₀. Let p be a prime. Then

Thus

Ord_p(n) + k Ord_p(y₀) = k Ord_p(x₀).

This implies that

Ord_p(n) ≡ 0 mod k

By the fol lowing lemma , this implies that n is a kth power, contradicting the hypothesis.

Lemma 23. Let n be a positive integer. Then n is a kth power if and only if k | Ord_p(n)
for all primes p.

Proof. If n = m^k then (Proposition 6). Thus k | Ord_p(n) for all p.

Conversely, suppose k | Ord_p(n) for all primes p. Let be a finite sequence of
distinct primes that include all primes dividing n. Then for some non-
negative integer a_i (since By the product formula ,

Thus n is a kth power.

Now we will see why is irrational. Of course, this generalizes to other logarithms
as well. To do so, we convert the problem into a diophantine equation.

If for integers x₀, y₀ with y₀ ≠ 0, then by definition of logarithms

In other words, This implies that 10^x = 2^y has a solution with y ≠ 0. Conversely,
if such a solution exists, then is rational. We show this cannot happen.

Theorem 24. The equation 10^x = 2^y has no solution with x, y ∈ Z and y ≠ 0. In other
words, is irrational.

Proof. Suppose that where y₀ ≠ 0. Apply Ord5 to both sides:

But Thus x₀ = 0. This implies that 10⁰ = 2^y. So 2^y = 1.
Apply Ord₂ to both sides. This implies that yOrd₂(2) = Ord₂(1). But Ord₂(2) = 1 and
Ord₂(1) = 0. Thus y₀ = 0, a contradiction.

5. Zeros of n!

How many zeros are at the end of n! ? For example,

15! = 1307674368000

has three zeros at the end of its decimal expansion , and

50! = 30414093201713378043612608166064768844377641568960512000000000000
has 12 zeros.

The number of zeros at the end of a number's decimal expansion is just the largest power
of ten dividing that number.

Lemma 25. The largest power of 10 dividing n is
Exercise 4. Prove the above.
To use the above formula it helps to have a formula for Ord_p(n!).

Lemma 26. If p is a prime, and n is a positive integer, then

Proof. Use the formula and apply Proposition 5.

Exercise 5. How many zeros does 56! have? How many zeros does 231! have? Hint:
so it is enough to compute Ord₅.

6. Exercises

Here are some exercises that can be solved with the order functions Ord_p. (They can also
be solved with the unique factorization theorem , but the solutions using the order functions
should be a bit easier).

Exercise 6. Show that if a^k | b^k then a | b.

Exercise 7. Show that if 3a³b | c² then a | c.

Exercise 8. Show that if a⁵c | b⁴ then a | b.

Exercise 9. Show that if ab is a square, and if a and b are relatively prime, then a and b are
squares. Give a counter example when a and b are not relatively prime.

Exercise 10. Show that if p | a^k where p is a prime, then p | a.

Exercise 11. Show that is irrational.