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 $n$ th 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.

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:

At 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:

The 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/.