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

Next Post
Leave a comment

2 Comments

  1. Lessons from teaching gifted elementary school students: Index | Mean Green Math
  2. Lessons from teaching gifted elementary school students: Index (updated) | Mean Green Math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: