## Orlando Presentation

A presentation of the following article was given at the Joint Mathematics Meetings, January 10-13, 1996, Orlando, Florida.

## Carousel Numbers: A Lead-in to Number Theory

#### Gary Klatt Mathematics and Computer Science Dept. Univ. of Wisconsin - Whitewater Whitewater, WI 53190 fax: (414) 472-5238 e-mail: klattg@uwwvax.uww.edu phone: (414) 472-5173

```------------------------------------------------------------------------
0.     BACKGROUND/OVERVIEW
------------------------------------------------------------------------

PROJECT FOR ALGEBRA AND NUMBER THEORY
COURSE FOR PRE-SERVICE TEACHERS

-    Ideal for discovery learning
-    Students work in groups and individually
-    Uses Derive and custom programs
-    Students write up results in a paper

FOUR DIVERSE PROBLEMS

-    Each generates interesting questions and conjectures
-    3 of the 4 are elementary
-    Surprising connections to the main problem
-    Some questions remain open

THE PROBLEMS
1    CAROUSEL NUMBERS (the appetizer problem)
2    PERIODS OF DECIMALS (the main problem)
3    NINE NUMBERS & ONE NUMBERS (useful aside)
4    GROUP OF UNITS MOD N (final battleground)

------------------------------------------------------------------------
1.     CAROUSEL NUMBERS  (the appetizer problem)
------------------------------------------------------------------------

N = 142857 has a neat property:

142857                        142857
x2                            x3
------                        ------
285714                        428571

We see the same digits and in the same order as the
original 142857 but just cycled around.

Multiplying 142857 by 4, 5 and 6 gives the same result -
the other three possible cyclic permutations of the 6
digits.

Try 4ùN, 5ùN or 6ùN on your calculator. What is 7ùN?

We call the number 142857 a CAROUSEL NUMBER.

The next carousel number we know is

M = 0588235294117647

It has 16 digits and we need the leading zero to make it
work. Try multiplying it by 2 to see why.

0588235294117647         0599235294117647
x2                      x
----------------         ----------------
1176470588235294

Here all the multiples from 2 through 16 produce cyclic
permutations of the digits of M.

Note this is too large a number for most calculators to
handle. Do today's students still know how to multiply by
hand? Do you? (Prove it by trying another case above.)

Some natural questions arise:

ARE THERE MORE?                                        (Yes, lots)

HOW MANY?                                          (No one knows!)

CAN ONE HAVE 2 DIGITS? ... 3 DIGITS?                 (No. Try it!)

HOW DO WE FIND THEM?                                  (Read on...)

--------------------------------------------------------------------------
2.     PERIODS OF DECIMALS  (the real problem)
--------------------------------------------------------------------------

Most math students know the decimal for any rational
number, m/n, will repeat. For example,

1/7 = .142857142857...              repeats with a period of 6, and

5/12 = .41666...                    repeats with a period of 1 after a
delay of 2.
1/13 = .076923...                   has period 6, half the max of 12

1/17 = .05882352941887647...        has period 16 (the max it could have)

RELATIONSHIP WITH CAROUSEL NUMBERS

As hinted above with 1/7 and 1/17, every n where 1/n
has maximal period n-1 will produce a carousel number.

Only prime n's work and only some primes at that: 7, 17,
19, 23, and 29 are the first five.

We call these CAROUSEL PRIMES.

Our main interest in the algebra/number theory course has been
investigating what determines the period of decimals.

This begins with long division done by hand, but quickly
leads to writing computer programs to generate data and
check out conjectures. Lots of questions yield to easy
conjecture, but surprisingly no one knows the complete
story.

It is too big a story to detail in this short talk, but here is
one small part. We look at period of 1/p for prime p's.

prime,p        p-1    per(1/p)    (p-1)/per(1/p)
-------        ---    --------     ------------
3            2       1              2
7            6       6              1
11           10       2              5
13           12       6              2
17           16      16              1
19           18      18              1
23           22      22              1
29           28      28              1
31           30      15              2
37           36       3             12

The conjecture that per(1/p) divides p-1 is later proved to
be a consequence of Lagrange's theorem in group theory.
(Which says the order of a subgroup divides the order of the group.)

A similar "obvious" conjecture for per(1/p^a) turns out to
be false - the first counterexample is for 1/487^2  (reference 1).

USING THE COMPUTER

Here is a program written in QBASIC to look for primes and then find the
period of 1/p. It also shows (p-1)/per(1/p).

'per(1/p).bas   a program to find the period of the decimal for 1/p
'             (first find the primes, p, up to maxn)

maxn = 289              'how far we will look for primes

'first find the primes less than maxn by the sieve of Eritosthenes

DIM n(maxn): n(1) = 0
FOR j = 2 TO maxn: n(j) = 1: NEXT j: j = 1
DO WHILE j * j < maxn
j = j + 1
IF n(j) = 1 THEN
FOR k = 2 TO maxn / j: n(k * j) = 0: NEXT k
END IF
LOOP

'now print out the primes and the period of 1/p

numbase = 10: j = 2: m = 1
PRINT "prime"; TAB(8); "per(1/p)"; TAB(18); "(p-1)/per"
DO WHILE j < maxn
IF n(j) > 1 AND numbase MOD j > 0 THEN
remainder = 1
place = 0
DO
place = place + 1
remainder = numbase * remainder MOD j
LOOP UNTIL remainder = 1
PRINT TAB(2); j; TAB(10); place; TAB(18);
FOR k = 1 TO (j - 1) / place: PRINT "*"; : NEXT k: PRINT
m = m + 1
END IF
j = j + 1
LOOP

SOME QUESTIONS
For which n's is the decimal for 1/n terminating?
(Find all the simple cases you can. What
determines the length of the decimal?)
What determines when there is a delay? What determines
the length of the delay?  (Relate to the question above.)

How does per(1/p^a) relate to per(1/p)?
(Try small primes but 2 and 5 are special.)
How does per(1/pq) relate to per(1/p), per(1/q)?
(Try 1/707. Note per(1/7)=6, per(1/101)=4.)
How would you modify the program to just find per(1/n)?

----------------------------------------------------------------------------
3.     NINE NUMBERS AND ONE NUMBERS  (a useful aside)
----------------------------------------------------------------------------

The NINE NUMBERS, 9, 99, 999, 9999, etc., are important
players in problem 2. Their prime factorizations show
interesting patterns, and help explain the period of 1/n. Of
course, every Nine number is nine times a ONE NUMBER,
1, 11, 111, 1111, etc., so we concentrate on recognizing
patterns in the prime factors of the One numbers.

We use Derive to help with factoring. (Derive is a nice,
inexpensive, easy to learn computer algebra system.)

99 = 9ù11
999 = 9ù3ù37
9999 = 9ù11ù101
99999 = 9ù41ù271
999999 = 9ù3ù7ù11ù13ù37

As a hint at the connection with periods of decimals,
1/37 = 27/999 = .027027027... (period is 3).

These factorizations help answer the question "What is the
smallest n such that 1/n has period 4? ... has period 5?

Note One numbers are also called "repunits". They have
close connections with the polynomials
1 + x + x^2 + ... + x^(n-1) = (x^n-1)/(x-1)
In base 2 the prime One numbers are the Mersenne
primes, famous for leading to perfect numbers.

SAMPLE WORKSHEET

Here is a sample worksheet we use in our course to help guide the
discovery of patterns.

Math 452    Worksheet on Factoring "One-numbers"                                      9/28/92

I. Factoring the one-numbers: data generated by Derive

n      prime factors of 111...1 (n ones)
--      ---------------------------------
2      11 (prime)
3      3 37
4      11 101
5      41 271
6      3 7 11 13 37
7      239 4649
8      11 73 101 137
9      3 3 37 333667
10     11 41 271 9091
11     21649 5_____  (get into Derive and find the missing digits)
12     3 7 11 13 37 101 9__1
13     53 79 265371653
14     11 239 4649 909091
15     3 31 37 41 271 2906161
16     11 17 73 101 137 5882353
17     2071723 5363222357
18     3 3 7 11 13 19 37 52579 333667
19     1111111111111111111 (prime)
20     11 41 101 271 3541 8091 27961

II. Patterns and conjectures
1.  11 divides a one-number for n =
2.  3 and 37 divide for n =
3.  101 divides for n =
4.  41 and 271 divide for n =
5.  What's really going on in 1-4 is that
6.  (Other conjectures?)

MORE QUESTIONS

Characterize all n's so that 1/n has period 1, period 2,
period 3.

What is the smallest n so 1/n has period 2, period 3, period 4?
How is this related to factors of one numbers?

Explain why Ones(k) = 11...1 (k ones) cannot be prime unless
k is prime.

Look up what the prime one numbers in base 2 have to do with
perfect numbers.

----------------------------------------------------------------------------
4.     THE GROUP OF UNITS MOD n, Un  (the final battleground)
----------------------------------------------------------------------------

Un is the group of integers between 1 and n-1 that have
no factors in common with n. It is a group under
multiplication mod n. E.g. U7 = {1, 2, 3, 4, 5, 6} and
2 x 5 = 10 = 3 (mod 7).

When we do long division to find the decimal for 1/7
(say), we are actually finding the powers of 10 in U7.

.1428571...
------------
7|1.0000000
7
30                                   10 = 3 (mod 7)
28
20                            100 = 30 = 2 (mod 7)
14
60                    1000 = 300 = 20 = 6 (mod 7)
56
40                 10,000 = ... = 60 = 4 (mod 7)
35
50                  10^5 = ... = 40 = 5 (mod 7)
49
10                 10^6 = ... = 50 = 1 (mod 7)

That is, the remainder at every stage of the long division,
3, 2, 6, 4, 5, 1, is the same as the successive powers of 10
mod 7. AND THE LONG DIVISION PROCESS IS JUST REDUCTION OF POWERS
OF 10 MOD 7 (or mod n in general).

So per(1/n) = the order of 10 in Un and we may use all
the power of group theory to attack the periods of
decimals investigation. (The order of an element in a finite group
is the smallest power which gives 1.)

OTHER BASES

Note that "decimals" in other bases are fairly difficult. For
example, the "decimal" in base two for 1/7 involves writing 7 in
base 2 as (111), and doing long division in base 2.
.001...
-------
111 |1.000...
111
---
1
Since we get the remainder of 1 here everything will repeat. That is,
in base 2 the decimal for 1/7 = 1/(111) = .001001001... (base 2).

However, finding the order of 2 in U7 is easy. 2^1 = 2, 2^2 = 4, and
2^3 = 8 = 1 (mod 7). So we see "2 has order 3 in U7" exactly corresponds
to "1/7 has period 3 as a binary decimal".

EVEN MORE QUESTIONS
Find the order of 10 in a bunch of Un's to check it is the
same as per(1/n): pick n's with no 2's or 5's

Explore decimals in other bases. Find a prime, p, which has
period p-1 as a base 2 decimal. Check that the repeating
block is indeed a base 2 carousel number

Form a list of carousel primes and try to see what they
have in common. Predict a new carousel prime and test it.
(This is likely hard. Does that put you off, or inspire you?)

---------------------------------------------------------------------------
5.     THE BIG CONNECTING THEOREM
---------------------------------------------------------------------------

THEOREM
Assume m/n is a reduced fraction and n' is the result of
dividing all 2's and 5's out of n.

Then the following are equivalent:
i)   The decimal for m/n eventually repeats every k places

ii)   The decimal for 1/n' repeats every k places (with no delay)

iii)   1/n' can be written as B/99...9 (k 9's)

iv)   n' divides 99...9 (k 9's)

v)   10^k = 1 mod n'  That is, 10^k = 1 in Un'

COROLLARY
Thus the period of m/n (reduced) =
per(1/n) =
per(1/n') =
the length of the smallest Nine number n' divides =
the order of 10 in Un'

APPLICATION TO CAROUSEL NUMBERS
If p is a prime with 1/p having largest possible period p-1,
then B = 99...9(p-1 9'S)/p is a carousel number.

These carousel primes (primes where per(1/p)=p-1) are characterized by
-    the first Nines number that p divides has length p-1
-    10 is a generator of the cyclic group Up

A better characterization is needed - we would like an
easily checked property of p to make it a carousel prime.

YET EVEN MORE PROBLEMS
Prove these results

Show that every carousel number arises in this way (as a
Nines number over a carousel prime).

---------------------------------------------------------------------------
PARTIAL CAROUSEL NUMBERS
---------------------------------------------------------------------------

The number D = 076923 behaves a bit like a carousel number. It has 6
digits (again we need the leading 0), and half of the multiples
from 1D, 2D, 3D, ..., 12D are cyclic permutations of D.

For example, 3D = 230769, and 4D = 307692 give the same digits in the same
order. However 2D = 153846, and 5D = 384615 do not. (Note 5D is a cyclic
permutation of 2D. Hmmmmm... check out the other multiples)

So this number, D = 076923, is sort of "half" a carousel number. Not all
the beginning multiples produce cyclic permutations, but half do.

What is true about D = 076923 is that all of the cyclic permutations,
769230, 692307, etc are multiples of D. (Check that.)

DEFINITION
So we might define a PARTIAL CAROUSEL NUMBER to be an integer (perhaps
with leading 0's) with the property that all of its cyclic permutations
are multiples of the number.

CONNECTION WITH PERIODS OF DECIMALS
Again there is a connection with periodic decimals. 1/13 = .076923...
repeating with a period of 6 (half the max. potential period of 12).

Looking at the powers of 10 in U13 (which are the same as the
remainders in the long division process to find the decimal for 1/13)
we get          10 = 10 (mod 13)
100 = 9 (mod 13) - subtract 7 13's = 91
10^3 = 90 = 12 (mod 13)
10^4 = 120 = 3 (mod 13)
10^5 = 30 = 4 (mod 13)
10^6 = 40 = 1 (mod 13).
These are exactly the multiples that "work": 10D, 9D, 12D, 3D, 4D,
(and 1D) give the 6 cyclic permutations of the digits of D.

Further, they are in the order of how much cycling happens:
10D = 769230  cycle or "left shift" by 1
9D = 692307    left shift by 2 from D = 076923
12D = 923076    left shift by 3
etc.

So we are on to something here. We can find more interesting numbers
by not insisting that all the multiples 2X, 3X, ...dX be cyclic
permutations, but only that all cyclic permutations be multiples.

A PROBLEM ARISES
Alas, the inclusion of leading 0's develops into a real problem.

For example, 37 is not a partial carousel number because 73 is not
a multiple of 37. But 037 is!
(shift left 1) 370 = 10 times 37
(shift left 2) 703 = 19 times 37

It turns out that because 37 divides 999 (3 nines) we need the leading
zero to have a 3 digit partial carousel number.

THEOREM
(nearly) EVERY NUMBER WILL BE A PARTIAL CAROUSEL NUMBER

Idea of the proof: Nearly every number divides a Nines number. The
length of the Nines number needed is related to the period of 1/n.
Add enough leading 0's to match the length of that Nines number. You
will now have a partial carousel number.

EXAMPLE   Let n = 123. Factoring, n = 3 x 41. It turns out 1/3 has
period 1 and 1/41 has period 5, so 1/123 has period 5. We
claim 00123 has the partial carousel property. (We have added
enough leading 0's to bring the length to 5.)

COROLLARY
Maybe partial carousel numbers aren't all that interesting after all.
Oh well, you can't win them all.

---------------------------------------------------------------------------
REFERENCES
---------------------------------------------------------------------------

Carousel numbers and Carousel primes are my own names.

So are Nine numbers and One numbers.

The carousel stuff may be new, but many people rediscover the story of
periods of decimals. That is so much more fun than looking it up.

But if you would like to see more of the story, here are some references.

1.      Solved and Unsolved Problems in Number Theory
by Daniel Shanks, Chelsea Publ. Co., 2nd ed. 1978

2.      Contemporary Abstract Algebra
by Joseph A. Gallian, Heath, 2nd ed., 1990

3.      A Concrete Introduction to Higher Algebra
by Lindsay Childs, Springer-Verlag, 1979

4.      Numbers: Rational and Irrational
by Ivan Niven, MAA, 1961

5.      The Theory of Numbers, An Introduction
by Anthony A. Giola, Markham Publ. Co., 1970

6.      Excursions into Mathematics
by Beck, Bleicher, and Crowe, Worth Publ., 1969

I have lots of fun with these investigations, and continue to do so.
If you have any comments on the above, or ideas to add, I would
REALLY like to hear from you.

Dr. Gary Klatt
Dept of Mathematics and Computer Science
Univ of Wisconsin - Whitewater
Whitewater, WI  53190
email: klattg@uwwvax.uww.edu
```