Tag: number theory

My concentration is better today, and I spent three and a half hours ironing out the wrinkles in my logarithm proof. I’ve had the general outline written down for some time, but there turned out to be a lot of details that needed attention, so that I think I’m justified in counting the effort as my study for the day, even though I don’t usually include time spent blogging.

The proof uses several supporting facts that I’ve listed below as Notions 1-3. I haven’t decided yet whether I want to prove them, but I may at some point.¹ I’ve also stated and used the Fundamental Theorem of Arithmetic without proving it. The course I took my first semester at college in which we developed the tools to prove that theorem, was one of the turning points in my life. I can no longer remember how it’s done, however.

I’m not entirely happy with this proof. I think it’s sound, but unclear in places. I had fun making it, though, and I hope someone enjoys it.

---

Definition: Two integers are relatively prime if they have no common factors besides $1$.

Notion 1: Every rational number can be written as the ratio of two integers that are relatively prime and at least one of which is positive.

Notion 2: If $a>1$, then $a^n>1$ if and only if $n$ is positive.

Notion 3: If $a$ divides $bc$ and $a$ and $b$ are relatively prime, then $a$ divides $c$.

---

The Fun(damental) Theorem of Arithmetic: Every integer greater then $1$ can be expressed as a product of primes in exactly one way, ignoring order.

---

Proposition: Given two natural numbers $a$ and $b$ that are both greater than $1$, if $\log_a b$ is rational, then both $a$ and $b$ are powers of a natural number $c$.

Suppose that $a$ and $b$ are natural numbers greater than $1$ and that $\log_a b$ is rational.

Then, using Notion 1, there exist integers $n$ and $m$ such that $a^{\frac{n}{m}}=b$, $n$ and $m$ are relatively prime, and $n$ or $m$ is positive.

A bit of algebra yields $a^n=b^m$.

Since both $a$ and $b$ are greater than $1$ and $n$ or $m$ is positive, the equal expressions $a^n$ and $b^m$ are both greater than $1$ by Notion 2. It follows, again by Notion 2, that both $n$ and $m$ are positive.

Consequently, because the integers are closed under multiplication, the value $a^n=b^m$ is an integer.

Let it be called $d$.

By the Fundamental Theorem of Arithmetic, $a$, $b$, and $d$ can all be expressed as a product of primes in exactly one way.

If the prime factorization of $a$ is $(a_1)(a_2)…(a_i)$, with some values possibly equal, then since $d=a^n$, the prime factorization of $d$ is $(a_1)^n(a_2)^n…(a_i)^n$.

Likewise, if the prime factorization of $b$ is $(b_1)(b_2)…(b_j)$, then since $d=b^m$, the prime factorization of $d$ is $(b_1)^m(b_2)^m…(b_j)^m$.

Notice that the prime factorization of $d$ contains the same factors as the prime factorization of $a$ and that the prime factorization of $d$ also contains the same factors as the prime factorization of $b$. It follows that the prime factorizations of $a$ and $b$ contain the same factors as one another, as well, though not necessarily the same number of times.

[This relationship between $a$ and $b$ is one I found very early on. I thought there was probably a name for it, but inquiries on Math Stack Exchange only turned up the notion of a radical, which is the product of one copy of every one of an integer’s prime factors. In those terms, what I’m saying is that $a$ and $b$ have the same radical.]

Now consider $p$, an arbitrary prime factor of $a$, $b$, and $d$. Let the number of occurrences of $p$ in the prime factorizations of each number be called $O_{a,p}$, $O_{b,p}$, and $O_{d,p}$, respectively.

Because an exponent represents repeated multiplication by the same value, it multiplies the number of occurrences of each factor. Thus, the relationships among $a$, $b$, and $d$ mean that $(O_{a,p})(n)=O_{d,p}=(O_{b,p})(m)$.

By Notion 3, since $(O_{a,p})(n)=(O_{b,p})(m)$ and $n$ and $m$ are relatively prime, $m$ divides $O_{a,p}$ and $n$ divides $O_{b,p}$. Thus, for the arbitrary prime factor $p$, $\frac{O_{a,p}}{m}=\frac{O_{b,p}}{n}$ is an integer. Furthermore, since all values involved are positive, it is a positive integer.

Therefore, it is possible to construct a natural number $c$ such that, for each prime factor $p$ in the prime factorizations of $a$ and $b$, the prime factorization of $c$ contains $\frac{O_{a,p}}{m}=\frac{O_{b,p}}{n}$ occurrences of $p$.

Now, by construction, the prime factorization of $c$ contains the same factors as the prime factorization of $a$.

Furthermore, by the reasoning used above, the prime factorization of $c^m$ contains the same factors as the prime factorization of $c$. Thus the prime factorization of $c^m$ also contains the same factors as the prime factorization of $a$.

Since an exponent multiplies the number of occurrences of each factor, given any prime factor $p$ in the prime factorization of $a$, the number of occurrences of $p$ in the prime factorization of $c^m$ is $\frac{O_{a,p}}{m}(m)=O_{a,p}$.

Recall that this is the number of occurrences of $p$ in the prime factorization of $a$. Hence $c^m$ has the same prime factors as $a$ with the same number of occurrences for each factor. It follows that $c^m=a$.

The same reasoning can be used to show that $c^n=b$, so the proposition is proven.

[Phew.]

1. To do. ↩︎