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:

n p q 3 2 1 7 1 6 9 8 1 11 5 2 13 2 6 17 1 16 19 1 18 23 1 22 29 1 28 31 2 15 37 12 3 41 8 5 43 2 21 47 1 46 53 4 13 ...

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.