Problem Dealing with Digit Cycles

[rjmack]

Not sure if cycle is the best word here..

Let k and b (both > 1) be such that b does not divide k-1 (with the exception that b may equal k-1).

If n is the smallest power so that k^n is equivalent to 1 mod b (so n is the length of the digit cycle of 1/b in base k),

then bn is the smallest power so that k^(bn) is equivalent to 1 mod b^2 (so bn is the length of the digit cycle of 1/(b^2) in base k).


In base 10, 1/81 has length 9. 1/9 has length 1. I've checked many other examples.

 

[dodo]

I'm not sure if I follow. What about k=10, b=22 ? And why are these two statements equivalent: "n is the smallest power so that k^n is equivalent to 1 mod b", and "n is the length of the digit cycle of 1/b in base k" ?

 

[rjmack]

Sorry I forgot an important part...

Let k and b (both > 1) be such that b does not divide k-1 (with the exception that b may equal k-1) and k and b are relatively prime.

If n is the smallest power so that k^n is equivalent to 1 mod b (so n is the length of the digit cycle of 1/b in base k),

then bn is the smallest power so that k^(bn) is equivalent to 1 mod b^2 (so bn is the length of the digit cycle of 1/(b^2) in base k).

Sketches of equivalence proofs:

Let n be the smallest power so that k^n is equivalent to 1 mod b. (we know such a power exists because k and b are relatively prime and k^0 starts the period at 1, and it must return there or we get a contradiction) So k^n - 1 = xb for some x, and for each m < n this is not the case. So 1/b = x/(k^n - 1). Rewrite in base k digit notation by using the geometric series. Notice our digit cycle is of length n. We might ask what if there is a smaller cycle within that cycle, but this is not the case because n was chosen smallest. Going the other way is a similar game.

 

[rjmack]

Also...

On a more general note we can say this:

Let k and b (both > 1) be such that b does not divide k-1 (with the exception that b may equal k-1) and b has at least one factor that is relatively prime with k.

If n is the smallest power so that k^n is equivalent to 1 mod c where c is the entire part of b that is relatively prime with k (so n is the length of the digit cycle of 1/b in base k),

then cn is the smallest power so that k^(cn) is equivalent to 1 mod c^2 (so cn is the length of the digit cycle of 1/(b^2) in base k).

Now your example of k=10 b=22 works.

1/22 has length 2, 1/484 has length 11*2 = 22.

With equivalence proofs we can just factor off those parts of b that are factors of k and they will end up as digits before the other digits begin their cycle (which is where I begin counting the length of the cycle, the minimal length, no cycles within cycles).

I am just messing with this for fun. I don't know if any of it is true yet...still searching for a nice proof.

 

[rjmack]

I am trying to solve this piece so I can show that

For each prime p and k > 1 where k-1 = (a_1^b_1)*(a_2^b_2)*(a_3^b_3)*...*(a_n^b_n) in prime factorization,

(k^p - 1) / c is squarefree where c = (a_1^(b_1 - 1))*(a_2^(b_2 - 1))*(a_3^(b_3 - 1))*...*(a_n^(b_n - 1))

 

[rjmack]

Sorry, This is Not True in General

Let k and b (both > 1) be such that b does not divide k-1 (with the exception that b may equal k-1) and k and b are relatively prime.

If n is the smallest power so that k^n is equivalent to 1 mod b (so n is the length of the digit cycle of 1/b in base k),

then bn is the smallest power so that k^(bn) is equivalent to 1 mod b^2 (so bn is the length of the digit cycle of 1/(b^2) in base k).

-------------------------------------------

5 is the smallest power so that 9^5 is equivalent to 1 mod 11.

9^1 - 1 = 8
9^2 - 1 = 80
9^3 - 1 = 728 = 8*7*13
9^4 - 1 = 6560 = 32*5*41

9^5 - 1 = 59048 = 8*11*11*61

But 11*5 is not the smallest power so that 9^(11*5) - 1 is a multiple of 11^2.
5 is the smallest power. For certain values of k we may have this property, but not in general.