Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Problem Dealing with Digit Cycles

  1. Jan 11, 2008 #1
    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.
     
  2. jcsd
  3. Jan 11, 2008 #2
    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" ?
     
  4. Jan 11, 2008 #3
    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.
     
  5. Jan 11, 2008 #4
    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.
     
    Last edited: Jan 11, 2008
  6. Jan 11, 2008 #5
    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))
     
  7. Jan 31, 2008 #6
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Problem Dealing with Digit Cycles
  1. Singer Cycles (Replies: 13)

  2. Power of a cycle (Replies: 4)

  3. Disjoint Cycles (Replies: 5)

Loading...