Remainder orbits

Richard Suchenwirth 2004-07-10 - When you do integer division, a non-zero remainder may occur, which the modulo operator % gives us:

 10/7 = 1
 10%7 = 3

In manual division, the remainder is multiplied by 10 and again integer-divided by the divisor, until a zero remainder is reached (or the person calculating is exhausted). Periodic decimal fractions are known to never terminate, because no zero remainder ever comes:

 10/7. = 1.42857142857...

The "142857" part will repeat as long as you wish (you'd stop before "forever"), like a circular graph of digits, a ring. Such remainder rings (not sure whether that's the correct term, but searching Mathworld brought me no better one) ...

Lars H interrupts: What you are describing in the rest of this page is rather remainder orbits (they are technically the orbits of the multiply-by-10-modulo-b map). A ring is an algebraic structure which (at least) supports the three operations + (addition), - (subtraction), and * (multiplication).

... have ever again fascinated me a bit, and today I wanted to play with them in Tcl.

 proc rem-orbit {a b} {
    set res {}
    while 1 {
        set rem [expr {$a % $b}]
        if {$rem==0} {error "aperiodic $b"}
        if [in $res $rem] {return $res}
        lappend res $rem
        set a ${rem}0 ;# fancy multiplication by 10 :-)
    }
 }
 proc in {list element} {expr [lsearch -exact $list $element]>=0}

Lars H again: Reaching $rem==0 does not (as the above procedure claims) mean that the sequence of remainders is aperiodic, but simply that the period length is 1. Compare with decimal fractions: a number has an aperiodic decimal fraction if and only if it is irrational.

Some tests:

 % rem-orbit 1 7
 1 3 2 6 4 5
 % rem-orbit 2 7
 2 6 4 5 1 3

The orbits look different - and yet are the same: if you just rotate the second one so that the smallest element comes first, it equals the first. This normalization can be easily coded:

 proc normalize ring {
    set pos [lsearch $ring [min $ring]]
    if $pos {
        concat [lrange $ring $pos end] [lrange $ring 0 [expr $pos-1]]
    } else {set ring} ;# return it unchanged
 }
 #-- numeric minimum of a list
 proc min list {lindex [lsort -integer $list] 0}

Test:

 % normalize [rem-orbit 2 7]
 1 3 2 6 4 5

How many distinct remainder orbits does a natural number have? Depends on the number, of course. Here's a routine that for a number n, tries all remainders of dividing from 1 to n-1 by n; normalizes the resulting rings, and keeps only the distinct ones:

 proc rem-orbits n {
    set res {}
    for {set i 1} {$i<$n} {incr i} {
        ladd res [normalize [rem-orbit $i $n]]
    }
    set res
 }
 #-- add an element to a list, if not contained yet
 proc ladd {listVar element} {
    upvar 1 $listVar list
    if ![in $list $element] {lappend list $element}
 }

Here's how to get the period (the sequence of repeating digits) from a remainder orbit:

 proc period {remorbit n} {
    set res ""
    foreach i $remorbit {append res [expr {(10*$i)/$n}]}
    set res
 }

Test again:

 % period [rem-orbit 1 17] 17
 0588235294117647
 % period [rem-orbit 2 17] 17
 1176470588235294
 % period [rem-orbit 3 17] 17
 1764705882352941

And now, let's just look at various numbers and their rem-orbit sets. The most interesting and regular results come from prime numbers. I made the following observations:

A number n has n-1 possible non-zero remainders
They either form one big orbit, or p orbits of q elements (e.g. 13: p=2,q=6) where p*q+1=n
For primes, the numbers in an orbit add up to n, or a multiple of it (counterexample: 9)
If the orbits are not all of equal length, the number is not prime

 % rem-orbits 3
 1 2
 % rem-orbits 5
 aperiodic 5 ;# because it divides 10 without remainder
 % rem-orbits 7
 {1 3 2 6 4 5}
 % rem-orbits 9
 1 2 3 4 5 6 7 8 ;# eight tiny one-element orbits...
 % rem-orbits 11
 {1 10} {2 9} {3 8} {4 7} {5 6} ;# five two-orbits, that all add up to 11
 % rem-orbits 13
 {1 10 9 12 3 4} {2 7 5 11 6 8} ;# two six-orbits
 % rem-orbits 17
 {1 10 15 14 4 6 9 5 16 7 2 3 13 11 8 12}
 % rem-orbits 19
 {1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2}
 % rem-orbits 21 ;# this is funny - you see the heritage of factors 7 and 3
 {1 10 16 13 4 19} {2 20 11 5 8 17} {3 9 6 18 12 15} 7 14
 % rem-orbits 23
 {1 10 8 11 18 19 6 14 2 20 16 22 13 15 12 5 4 17 9 21 3 7}
 % rem-orbits 29
 {1 10 13 14 24 8 22 17 25 18 6 2 20 26 28 19 16 15 5 21 7 12 4 11 23 27 9 3}
 % rem-orbits 31 ;# two 15-orbits
 {1 10 7 8 18 25 2 20 14 16 5 19 4 9 28} {3 30 21 24 23 13 6 29 11 17 15 26 12 27 22}
 % rem-orbits 37 ;# twelve 3-orbits
 {1 10 26} {2 20 15} {3 30 4} {5 13 19} {6 23 8} {7 33 34}
 {9 16 12} {11 36 27} {14 29 31} {17 22 35} {18 32 24} {21 25 28}
 % rem-orbits 39
 {1 10 22 25 16 4} {2 20 5 11 32 8} {3 30 27 36 9 12} {6 21 15 33 18 24}
 {7 31 37 19 34 28} 13 {14 23 35 38 29 17} 26 ;# see? not prime!
 % rem-orbits 41
 {1 10 18 16 37} {2 20 36 32 33} {3 30 13 7 29} {4 40 31 23 25}
 {5 9 8 39 21} {6 19 26 14 17} {11 28 34 12 38} {15 27 24 35 22}
 % rem-orbits 43 ;# two 21-orbits
 {1 10 14 11 24 25 35 6 17 41 23 15 21 38 36 16 31 9 4 40 13}
 {2 20 28 22 5 7 27 12 34 39 3 30 42 33 29 32 19 18 8 37 26}
 % rem-orbits 47 ;# one long orbit
 {1 10 6 13 36 31 28 45 27 35 21 22 32 38 4 40 24 5 3 30 18 39 14
 46 37 41 34 11 16 19 2 20 12 26 25 15 9 43 7 23 42 44 17 29 8 33}
 % rem-orbits 51
 {1 10 49 31 4 40 43 22 16 7 19 37 13 28 25 46}
 {2 20 47 11 8 29 35 44 32 14 38 23 26 5 50 41}
 {3 30 45 42 12 18 27 15 48 21 6 9 39 33 24 36} 17 34 ;# not prime!
 % rem-orbits 53 ;# four 13-orbits
 {1 10 47 46 36 42 49 13 24 28 15 44 16}
 {2 20 41 39 19 31 45 26 48 3 30 35 32}
 {4 40 29 25 38 9 37 52 43 6 7 17 11}
 {5 50 23 18 21 51 33 12 14 34 22 8 27}

Lars H: The second of your observations above isn't too hard to prove. What happens is that when n is a prime then the nonzero elements, in the ring Z_n of integers modulo n, form a group under multiplication. The element 10 generates a subgroup of this group, which shows up as the "rem-ring" containing the element 1 in your lists above. The other "rem-rings" are the remaining cosets of this subgroup. It is a fairly basic theorem in group theory that all cosets of a subgroup have the same size. One way to prove it is to observe that multiplication by a suitable group element gives rise to a bijection between the elements of the cosets. q is simply the size of the subgroup generated by 10 and p is the number of its cosets.

RS: Hm.. that goes over my head a bit, but I won't object :) In any case, I find it interesting how unpredictible (for me) the value of p is. Condensed from the above experiments:

What makes a prime have p=1? Will there be more primes for which q=3? Why?

Lars H: If memory serves, the relation between the size of a subgroup (q) and the number of its cosets (p) is used in the group-theoretic proof of Fermat's Little Theorem, which in turn is related to the RSA system for cryptography, so it's not so strange that things are hard to predict in this area.

As for q=3, this will happen precisely when 1000 (i.e., 10^3) is congruent to 1 modulo n but 10 is not. 1000 is congruent to 1 modulo n iff n divides 999, and since 999 = 3^3 * 37 it follows that 37 is indeed the only prime for which q is 3. A similar argument (10000-1 = 9999 = 3*3*11*101) shows that n=101 is the unique prime for which you get q=4.

Category Mathematics