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 10^{n}-1 is divisible by the fraction denominator *d*. In terms of modular arithmetic, this means that 10^{n}≡1 (mod *d*). This is called the multiplicative order of 10 modulo *d*, and denoted as ord_{d}(10) or O_{d}(10). Let us make a chart of the multiplicative orders of 10 modulo the first few whole numbers coprime with 10:

*d* |
ord_{d}(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, ord_{d}(10) is *d*-1; however, this is obviously not a general rule. For the other primes, such as 3, though, we have ord_{d}(10) dividing *d*-1; this does hold for *d* a prime. Note however, that while ord_{9}(10)=1 divides 9-1=8, ord_{21}(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* |
ord_{d}(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, ord_{d}(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 ord_{d}(10). For example, *φ*(23)=22, so ord_{23}(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 ord_{23}(10) must be 11 or 22 (ord_{23}(10)=22).

.

### Like this:

Like Loading...

*Related*

Tags: Math, Modular Arithmetic, Monday Math, Multiplicative Order, Repeating Decimals, Totient

This entry was posted on August 10, 2009 at 3:20 am and is filed under Math/Science. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply