Monday Math 84

Last week, I showed that for a fraction that converts to a pure repeating decimal, one with a denominator coprime with 10, the number of digits in the repeat is equal to the smallest whole number n such that 10n-1 is divisible by the fraction denominator d. In terms of modular arithmetic, this means that 10n≡1 (mod d). This is called the multiplicative order of 10 modulo d, and denoted as ordd(10) or Od(10). Let us make a chart of the multiplicative orders of 10 modulo the first few whole numbers coprime with 10:

d ordd(10)
3 1
7 6
9 1
11 2
13 6
17 16
19 18
21 6

You might note that in several cases, all prime, ordd(10) is d-1; however, this is obviously not a general rule. For the other primes, such as 3, though, we have ordd(10) dividing d-1; this does hold for d a prime. Note however, that while ord9(10)=1 divides 9-1=8, ord21(10)=6 does not divide 21-1=20. So what is our general rule for all d coprime with 10?
Consider Euler’s totient function φ(n), and note that for p prime, φ(p)=p-1. So, redoing the chart to add φ(d):

d ordd(10) φ(d)
3 1 2
7 6 6
9 1 6
11 2 10
13 6 12
17 16 16
19 18 18
21 6 12

From this, we see that in every case here, ordd(10) divides
φ(d). This is the general rule. However, proving that this is true requires group theory. This rule does limit the valid possibilities for ordd(10). For example, φ(23)=22, so ord23(10) must be 1, 2, 11, or 22. Now, we can rule out 1 and 2, as 9 and 99 are not divisible by 23. Thus ord23(10) must be 11 or 22 (ord23(10)=22).



Tags: , , , , ,

Leave a Reply

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

You are commenting using your 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: