group – Mean Green Math

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

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)$ .

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.