Posts Tagged ‘Modular Arithmetic’

Monday Math 123

June 14, 2010

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?


Monday Math 84

August 10, 2009

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