What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 7

Suppose that two positive integers are chosen at random. What is the probability that they are relatively prime (that is, have no common factors except 1)?

The answer is exactly what you’d expect it be (Gamma, p. 68): 6/\pi^2, or about 60.8%.

Yes, that was a joke.

Indeed, if k positive integers are random, the probability that they are relatively prime is 1/\zeta(k), where Riemann’s zeta function arises once again.

Even more, the probability that k random positive integers lack a nth power common divisor is 1/\zeta(nk).

I’ll refer the interested reader to Gamma and also to Mathworld (and references therein) for more details.

 

green line

When I researching for my series of posts on conditional convergence, especially examples related to the constant \gamma, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

Lessons from teaching gifted elementary school students (Part 4c)

Every so often, I’ll informally teach a class of gifted elementary-school students. I greatly enjoy interacting with them, and I especially enjoy the questions they pose. Often these children pose questions that no one else will think about, and answering these questions requires a surprisingly depth of mathematical knowledge.

Here’s a question I once received:

What is the chance of winning a game of BINGO after only four turns?

When my class posed this question, I was a little concerned that the getting the answer might be beyond the current abilities of a gifted elementary student. As discussed over the past couple of posts, for a non-standard BINGO game with 44 numbers, the answer is

\displaystyle 4 \times \frac{4}{44} \times \frac{3}{43} \times \frac{2}{42} \times \frac{1}{41} = \displaystyle \frac{4}{135,751}

After we got the answer, I then was asked the question that I had fully anticipated but utterly dreaded:

What’s that in decimal?

With these gifted students, I encourage thinking as much as possible without a calculator… and they wanted me to provide the answer to this one in like fashion. For my class, this actually did serve a purpose by illustrating a really complicated long division problem so they could reminded about the number of leading zeroes in such a problem.

Gritting my teeth, I started on the answer:

biglongdivisionAt this point, I was asked the other question that I had anticipated but utterly dreaded… motivated by child-like curiosity mixed perhaps with a touch of sadism:

How long do we have before the digits start repeating?

My stomach immediately started churning.

I told the class that I’d have to figure this one later. But I told them that the answer would definitely be less than 135,751 times. My class was surprised that I could even provide this level of (extremely) modest upper limit on the answer. After some prompting, my class saw the reasoning for this answer: there are only 135,751 possible remainders after performing the subtraction step in the division algorithm, and so a remainder has to be repeated after 135,751 steps. Therefore, the digits will start repeating in 135,751 steps or less.

What I knew — but probably couldn’t explain to these elementary-school students, and so I had to work this out for myself and then get back to them with the answer — is that the length of the repeating block n is the least integer so that

135751 \mid 10^n - 1

which is another way of saying that we’ve used the division algorithm enough times so that a remainder repeats. Written in the language of group theory, n is the least integer that satisfies

10^n \equiv 1 \mod 135751

(A caveat:this rule works because neither 2 nor 5 is a factor of 135,751… otherwise, those factors would have to be taken out first.)

Some elementary group theory can now be used to guess the value of n. Let G be the multiplicative group of integers modulo 135,751 which are relatively prime which. The order of this group is denoted by \phi(135751), called the Euler totient function. In general, if m = p_1^{a_1} p_2^{a_2} \dots p_r^{a_r} is the prime factorization of m, then

\phi(m) = n \left( \displaystyle 1 - \frac{1}{p_1} \right) \left( \displaystyle 1 - \frac{1}{p_2} \right) \dots \left( \displaystyle 1 - \frac{1}{p_r} \right)

For the case at hand, the prime factorization of 135,751 can be recovered by examining the product of the fractions near the top of this post:

135751 = 7 \times 11 \times 41 \times 43

Therefore,

\phi(135,751) = 6 \times 10 \times 40 \times 42 = 100,800

Next, there’s a theorem from group theory that says that the order n of an element of a group must be a factor of the order of the group. In other words, the number n that we’re seeking must be a factor of 100,800. This is easy to factor:

100,800 = 2^6 \times 3^2 \times 5^2 \times 7

Therefore, the number n has the form

n = 2^a 3^b 5^c 7^d,

where 0 \le a \le 6, 0 \le b \le 2, 0 \le c \le 2, and 0 \le d \le 1 are integers.

So, to summarize, we can say definitively that n is at most 100,800, and that were have narrowed down the possible values of n to only 7 \times 3 \times 3 \times 2 = 126 possibilities (the product of one more than all of the exponents). So that’s a definite improvement and reduction from my original answer of 135,751 possibilities.

At this point, there’s nothing left to do except test all 126 possibilities. Unfortunately, there’s no shortcut to this; it has to be done by trial and error. Thankfully, this can be done with Mathematica:

biglongdivision2The final line shows that the least such value of n is 210. Therefore, the decimal will repeat after 210 digits. So here are the first 210 digits of \displaystyle \frac{4}{135,751} (courtesy of Mathematica):

0.000029465712959757202525211600651192256410634175807176374391348866675015285338597874048809953517837805983013016478699972744215512224587664\
179269397647162820163387378361853688002298325610861061796966504850792996…

For more on this, see https://meangreenmath.com/2013/08/23/thoughts-on-17-and-other-rational-numbers-part-6/ and https://meangreenmath.com/2013/08/25/thoughts-on-17-and-other-rational-numbers-part-8/.

Thoughts on 1/7 and other rational numbers (Part 8)

In Part 6 of this series, I mentioned the following fact concerning the decimal representation of \displaystyle \frac{a}{b}: if neither 2 nor 5 is a factor of b, then the repeating block in the decimal representation of \displaystyle \frac{a}{b} has a length k that must be a factor of \phi(b). This function is the Euler toitent function or the number of integers less than b that are relatively prime with b.

In this post, I’d like to provide a justification for this theorem.

As discussed earlier, k is the least integer so that b is a factor of 10^k - 1. In the language of congruence, k is the least integer so that

10^k \equiv 1 (\mod b)

In other words, let G_b be the multiplicative group of numbers less than b that are relatively prime with b. By assumption 10 \in G_b. Then k is the order¬†of 10 in G_b, and there’s a theorem that states that the order of an element of a group must be a factor of the order of the group, or the number of elements in the group. In our case, the order of G_b is the number of integers less than b that are relatively prime with b, or \phi(b).

In other words, using these ideas from group theory, we can prove that k \mid \phi(b).

green line

Naturally, we don’t expect middle school students seeing long division for the first time to appreciate this property of decimal representations. Still, my main purpose in writing this post was to give a concrete example of how ideas from higher-level mathematics — like group theory — actually can shed insight into ideas that are first seen in school — even middle school. In other words, there’s a reason why UNT (and other universities) requires that college students who want to earn mathematics teaching certification with their degrees must have a major in mathematics.