What is the smallest number of integers needed, such that one is guaranteed to have a subset of three integers whose sum is divisible by three?

Solution:

## Posts Tagged ‘Modular Arithmetic’

### Monday Math 123

June 14, 2010### Monday Math 84

August 10, 2009Last 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

*(10). Let us make a chart of the multiplicative orders of 10 modulo the first few whole numbers coprime with 10:*

_{d}d |
ord(10)_{d} |
---|---|

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

*(10) dividing*

_{d}*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(10)_{d} |
φ(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

*(10). For example,*

_{d}*φ*(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).

.