Tag: arithmetic

Fun with Logarithms

Olly / / Math Posts

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.1 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. ↩︎

Logarithmisches Tafelwerk

Olly / / Math Posts

I was very busy today, at least for me. I didn’t have time for any study until evening, when I sat down to look at a copy of Gauss’s Fünfstelliges logarithmisches Tafelwerk that I just received.

No, not that Gauss. This Gauss is Friedrich Gustav Gauss (1829-1915), my great-great-great-grandfather. He was a surveyor for the Prussian government (at that time a very mathematical profession) and later an administrator in the same department. He also published several books of logarithmic tables, one of which was republished in the 1970s in the compact edition shown below.

Interior
Fünfstelliges logarithmisches Tafelwerk (Book of Five-digit Logarithmic Tables)

I tried for quite a while to make sense of the tables in this book. Some of them are dedicated the logarithms of integers and others to the logarithms of trigonometric functions evaluated for particular angles, but that’s about as much as I could understand. The actual values tended not to be what I thought they should, so I was clearly missing a lot. The fact that the book was in German was not that great a hindrance, I don’t think. There was not much explanatory material. The publishers clearly expected the book’s users to be familiar with tables of this kind.

Elegance and Regret

Olly / / Math Posts

I didn’t do any trigonometry today, but instead read more of Steven Strogatz’s The Joy of X and worked on the propositions about digit sums that I found in my notebook.

The most interesting tidbit from The Joy of X was Strogatz’s comment regarding a particular proof of the Pythagorean Theorem that, “The proof does far more than convince; it illuminates. That’s what makes it elegant.” That caught my attention and had me wondering whether all elegant proofs must be illuminating. I haven’t come to a conclusion yet.

To be illuminating is certainly not the only requirement for an elegant proof. The main proposition I worked on today was “the sum of the digits of any multiple of 9 is also a multiple of 9.” I came up with the outline of a proof by induction, the meat of which was a description of what happens to the digit sum when you add 9 to any natural number. It was full of cases and loops and was decidedly not elegant. I do think it gave a good sense of what was happening, though, and it could have been reworked to prove the general theorem that, in base $n$, the digit sum of any multiple of $n-1$ is also a multiple of $n-1$.

I was sure there must be a better proof, however, and I ended up searching for guidance on the Internet. I regret that, as I would rather have discovered the answer I found for myself. I did get to generalize it, at least, since it applied only to two-digit numbers. I’m not sure I would say that the result is illuminating. I don’t think it reveals why the theorem is true, except in as much as “why” is that 9 is one less than the base of the number system being used. It is simple, though. Does that make it elegant?

Proposition: For all $n\in\mathbb{N}$, the digit sum of $9n$ is a multiple of 9.

When $n$ is a natural number, $9n = 10^md_m+10^{m-1}d_{m-1}+…+10d_1+d_0$, where $d_m, d_{m-1},…,d_1, d_0$ are the digits of $9n$, in order.

$$10^md_m+10^{m-1}d_{m-1}+…+10d_1+d_0=$$ $$\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]+\left[d_m+d_{m-1}+…+d_1+d_0\right]$$

Thus, $$d_m+d_{m-1}+…+d_1+d_0=9n-\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]\text{.}$$

Note that the left-hand side of the equation is the digit sum of $9n$.

Note also that, for any natural number $x$, $$10^x-1=\sum_{i=0}^{x-1}10^i(9)=9\sum_{i=0}^{x-1}10^i\text{.}$$

[For instance, $10^3-1=1000-1=999=9(111)$.]

Hence, because each term of the expression is a multiple of 9, $$9n-\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]=9p$$ for some integer $p$.

It follows that the digit sum of $9n$ is a multiple of 9 for all $n\in\mathbb{N}$.

This proof could also be rewritten to cover all bases. In addition, the same argument could be used to prove that, in base 10, the digit sum of any multiple of three is also a multiple of three.

(And it occurs to me as I write this that you could also use it to prove the analogous fact, in base $n$, for any factor of $n-1$. That’s very cool and makes me feel like I have come up with something worthwhile on my own today.)

More Notebook Archeology

Olly / / Math Posts

I hoped I might finish the exercises from the review of conics today, but I am still feeling under the weather, so I didn’t push that. Instead I read some of The Joy of X by Steven Strogatz and poked around in the same old notebook where I unearthed the problem about superprimes. There I found a nifty, non-inductive proof that $\sum_{i=0}^{n-1}x^i=\frac{x^n-1}{x-1}$, which is a theorem from the first chapter of Number Theory by George E. Andrews, where it is proven by induction.

I also found two unproven propositions about digit sums and the question, “What is the pattern of the sums of digits for multiples of 9?” I worked a bit on the latter, but couldn’t make much of the results. That led me to look them up in the On-Line Encyclopedia of Integer Sequences, a resource I’d heard of but never before used. The sequence I was working with didn’t prove to have any very interesting properties, but I found some others I want to look into further, such as the binary weight of $n$ and the sequence $n$ minus the sum of the digits of $n$, the terms of which are always multiples of 9.1 (Whoa.) I’ll have to be careful, though. The OEIS looks worse than Wikipedia or even TV Tropes for trapping in the unwary browser.

  1. To do. ↩︎

Rational-a-Rama

Olly / / Math Posts

Today I will be sharing my proof that the decimal representations of rational numbers must repeat. This proof is based on a simple idea, but turned out to be pretty involved, with several parts.

The fundamental idea can be illustrated using long division. Consider the rational number $\frac{8}{7}$. We can find its decimal representation using the long division calculation below.

Long Division Remainders

Each step of this calculation begins with the remainder from the previous step (circled in red). Since the remainder on division by 7 must be an integer between 0 and 6, there are only 7 possible remainders. Thus, the remainder must repeat within no more than 8 steps. Once it repeats, the calculation will begin to cycle, causing the decimal representation it produces to repeat, as this one does.

Now let’s prepare for the more formal proof by proving two lemmas. I think the first of these is quite interesting and not immediately obvious. The second one is obvious, but I wanted to be assured of it, since it is vital to the main proof.

Lemma 1: Given a rational number $x$, if there exist two distinct digits $d_1$ and $d_2$ in the decimal representation of $x$ such that the sequence of digits following $d_1$ is the same as the sequence of digits following $d_2$, then the decimal representation of $x$ repeats.

Assume that two such digits exist and let the one which appears first be called $d_1$. Then the decimal representation of $x$ begins as follows: $s_1.s_2d_1s_3d_2$, where $s_1$ is a sequence of at least one digit and $s_2$ and $s_3$ are sequences of zero or more digits.

Now, since the sequence of digits following $d_2$ is the same as the sequence of digits following $d_1$, the decimal representation must continue: $s_1.s_2d_1s_3d_2s_3d_2$. Yet this further specifies the sequence of digits following $d_1$, so the same digits must appear again in the sequence following the initial appearance of $d_2$, yielding $s_1.s_2d_1s_3d_2s_3d_2s_3d_2$. This process (illustrated below) will continue infinitely, so $x=s_1.s_2d_1\overline{s_3d_2}$.

Thus, the lemma holds.

Two Digits With Sequences

(I realize the notation was a little sloppy here, with $d_2$ representing both a digit and a digit with its position, but I couldn’t find a good way to fix it.)

Lemma 2: Let $x$ be a non-negative rational number such that $x=\frac{n}{m}$, where $n$ and $m$ are non-negative integers and $m\neq 0$. There is no more than one way to represent $x$ as a mixed number $q\frac{r}{m}$ such that $q$ and $r$ are non-negative integers and $r<m$.

Suppose $\frac{n}{m}=q_1\frac{r_1}{m}$ and $\frac{n}{m}=q_2\frac{r_2}{m}$ where $q_1$, $q_2$, $r_1$, and $r_2$ are non-negative integers and $r_1,r_2<m$.

It follows that $q_1+\frac{r_1}{m}=q_2+\frac{r_2}{m}$ and thence that $q_1-q_2=\frac{r_1-r_2}{m}$.

Since $0<r_1<m$ and $0<r_2<m$, $-1<\frac{r_1-r_2}{m}<1$.

Thus $-1<q_1-q_2<1$, from which it follows that $q_1=q_2$, since $q_1$ and $q_2$ are integers.

Hence $\frac{r_1-r_2}{m}=0$, so $r_1=r_2$.

Therefore, both mixed numbers are the same, and the theorem holds.

Finally, we come to the main theorem.

Proposition: If $x$ is a rational number, then the decimal representation of $x$ repeats.

For any $x$, if the decimal representation of $x$ repeats, then the decimal representation of $-x$ repeats. Thus, it is sufficient to show that the theorem holds for all non-negative $x$.

Let $x$ be a non-negative rational number. Then $x=\frac{n}{m}$ for some non-negative integers $n$ and $m$, where $m\neq 0$.

The fraction $\frac{n}{m}$ can be expressed as a mixed number $q_1\frac{r_1}{m}$ such that $q_1$ and $r_1$ are non-negative integers and $r_1<m$. By Lemma 2, there is only one way to do this.

Using algebra we have: $$q_1\frac{r_1}{m}=q_1+\frac{r_1}{m}=q_1+\frac{r_1}{m}\left(\frac{10}{10}\right)=q_1+\frac{10r_1}{m}\left(\frac{1}{10}\right)$$

As above, the fraction $\frac{10r_1}{m}$ can be expressed uniquely as a mixed number $q_2\frac{r_2}{m}$ such that $q_2$ and $r_2$ are non-negative integers and $r_2<m$.

This yields $$q_1+\frac{10r_1}{m}\left(\frac{1}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)\text{.}$$

Notice that $q_2$ has only one digit, since $0\leq\frac{r_1}{m}<1$ and $0\leq q_2\leq\frac{10r_1}{m}$. Notice also that $0\leq\frac{r_2}{m}\left(\frac{1}{10}\right)<\frac{1}{10}$, since $0\leq\frac{r_2}{m}<1$. This means that $q_2$ is the tenths-place digit of the decimal expansion of $x$.

The algorithm can be continued as shown below, $$q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)\left(\frac{10}{10}\right)$$ $$=q_1+q_2\left(\frac{1}{10}\right)+\frac{10r_2}{m}\left(\frac{1}{100}\right)=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+\frac{r_3}{m}\left(\frac{1}{100}\right)$$ $$=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+\frac{r_3}{m}\left(\frac{1}{100}\right)\left(\frac{10}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+q_4\left(\frac{1}{1000}\right)+\frac{r_4}{m}\left(\frac{1}{1000}\right)…$$ with $q_i\frac{r_i}{m}$ for $i>1$ always the unique mixed number representation of the fraction $\frac{10r_{i-1}}{m}$ such that $q_i$ and $r_i$ are non-negative integers and $r_i<m$. By logic similar to that above, when $i>1$, $q_i$ will always be a digit of the decimal representation of $x$, with its value given by the power of $\frac{1}{10}$ by which it is multiplied.

Since, for all $i$, $r_i$ is a non-negative integer less than $m$, there are only $m$ possible values of $r_i$. This means that, among the infinite values of $r_i$, there must exist distinct $r_j$ and $r_k$ such that $r_j=r_k$. (ETA: By the Pigeonhole Principle!)

Since the mixed number representations used by the algorithm are unique, if $r_j=r_k$, then $q_{j+1}=q_{k+1}$ and $r_{j+1}=r_{k+1}$. By induction, it therefore follows that $q_{j+h}=q_{k+h}$ for all $h$. Since, when $i>1$, each $q_i$ is a digit of the decimal representation of $x$, it follows by Lemma 1 that decimal representation of $x$ repeats.

Therefore the theorem holds.

I hope this makes some measure of sense. I had a lot of trouble making this proof lucid, and eventually I had spent too much time working on. Those whose eyes did not glaze over will note that the algorithm I employed here is essentially long division. In developing it, I did not set out specifically to reproduce the long division algorithm, and I was intrigued when I noticed they are basically the same. Here is our long division problem annotated to show the relationship:

Long Division

Stewart’s Calculus

Olly / / Math Posts

Today was better than yesterday, though I was still not at full capacity. I spent about an hour on algebra review, then thought for a while about the decimal representations of rational numbers. I also read the Wikipedia article on long division, which says that the debate about its place in the curriculum actually dates back to the 1980s. There are some interesting examples there of the ways long division problems are written in different countries, as well.

For anyone interested, here is the review of algebra I am using. It’s made available as a supplement by the publishers of Stewart’s calculus textbooks. There are also reviews of analytic geometry and conic sections, which I plan to work through as well, along with the review of trigonometry provided as an appendix to my textbook. (My textbook has reviews of algebra, analytic geometry, and conics, too, but they are not as complete as those offered on the website.)

I have a lot of affection for Stewart’s calculus texts. They were used in both my high school and my college courses, and represent good times to me. A person I met online once asked me to name a book that had changed my life, and Stewart’s Single Variable Calculus was my choice. Had I not enjoyed calculus so much in high school, I would not have been attracted to economics as a college major, would not have been encouraged to minor in math, would not have taken Discrete Math my first semester, and might never have had my love of math kindled such that I am still carrying a torch for it. His discovery of Ramanujan might have been “the one romantic incident” in Hardy’s life, but my encounter with math was mine, and Stewart’s calculus was one of the sign posts on the way.

About Division

Olly / / Math Posts

Today’s study time was devoted to more algebra review, including some problems that involved factoring using polynomial division. I have a vague memory of being taught polynomial division around the turn of the millennium, but I had heard the name more recently. There is debate these days about whether, in a society where almost everyone carries a calculator almost everywhere, it is still worth the instructional time to teach students numerical long division. (Eliminating it wouldn’t be unprecedented. I was never taught to compute square roots by hand, as older generations were.) At any rate, one of the arguments in favor of keeping numerical long division in the curriculum is that, without it, students won’t be able to do polynomial division. I’m not sure that would be much of a loss, honestly. It is a fairly niche method of factoring, and I managed to study a lot more math than most people without running into any other application of it. I think the greater drawback to eliminating long division would be that, without that tool to convert one to the other, the connection between fractions and decimals would become something mysterious only the calculator understands.

Speaking of conversion between fractions and decimals, in the portion of The Joy of X that I read last night, Steven Strogatz mentions the fact that the decimal representations of rational numbers always terminate or repeat. Of course, I wondered how one could prove that. I haven’t had time to work on it yet, but I think I can see the vague outline of how it might be done (probably using an argument related to the long division algorithm). The thing I don’t have any ideas about yet is how to prove that a number represented by a repeating decimal must be rational. I may find time to work on both of these tomorrow, but I may decide on more algebra practice instead. I am growing impatient to move on to a new review topic.