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

'cyclic' primes

  1. Jul 10, 2003 #1
    1/7 = .142857... (repeated)
    2/7 = .285714...
    3/7 = .428571...
    4/7 = .571428...
    5/7 = .714285...
    6/7 = .857142...
    So, you get all n/7 from the same 'cycle' of 6 digits.
    Let's call 7 a 'cyclic' integer.
    The next cyclic integers are
    17, 19, 23,...
    They are all prime. But 11, 13, or 37 are NOT cyclic.

    Anybody know a rule do determine if a prime is 'cyclic' or not?
     
  2. jcsd
  3. Jul 10, 2003 #2
    Sorry but

    I have to burst your bubble a bit. I dabble is number theory as a hobby and all primes have a cycle, it just may be very large. 999=9×111, 111=3×37, etc..
     
  4. Jul 10, 2003 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think by "cyclic" he means that the period of the decimal expansion of p has length p-1.
     
  5. Jul 10, 2003 #4

    marcus

    User Avatar
    Science Advisor
    Gold Member
    2015 Award
    Dearly Missed

    One condition is that the prime p must
    divide the number
    10(p-1)/2 + 1
     
  6. Jul 11, 2003 #5

    marcus

    User Avatar
    Science Advisor
    Gold Member
    2015 Award
    Dearly Missed

    Re: Re: 'cyclic' primes

    I mean for example

    7 divides 1001

    17 divides 100,000,001

    19 divides 1,000,000,001

    I didnt check it out, just saw your question so this
    is a raw guess, but it might help find something better
    Maybe it could help find the next one after 19
     
  7. Jul 11, 2003 #6

    marcus

    User Avatar
    Science Advisor
    Gold Member
    2015 Award
    Dearly Missed

    Re: Re: 'cyclic' primes

    I will try the condition for p = 23
    See if 23 divides 1011 + 1

    Well, yes it does, on my calculator at least.
    23 divides 100,000,000,001

    I imagine this might be an iff-----a necessary and sufficient
    condition for a prime to be of that "cyclic" kind you
    are talking about.

    But dont have a proof so must be cautious
     
    Last edited: Jul 11, 2003
  8. Jul 11, 2003 #7
    Thanks, marcus!
    The next one is 29.
    29 divides 100,000,000,000,001
    Seems to work!
     
  9. Jul 11, 2003 #8

    marcus

    User Avatar
    Science Advisor
    Gold Member
    2015 Award
    Dearly Missed

    Great!

    I am still not sure if it always works. Proving it
    would be something for Hurkyl or Lethe or Tyger.

    Last night when I read your post i just guessed
    at that condition because I was pretty sure that
    another (more difficult to check) condition would
    work namely

    p divides 10p-1 - 1

    and it seemed intuitive that that harder-to-check condition
    was much the same thing as saying

    p divides 10(p-1)/2 + 1

    but this is really still an open problem as far as I am concerned
    and I hope some of the others see it a bit more clearly
    it is actually an intriguing thing you came up with arcnets
    and altho very much in the recreational-math class in the
    present form it might generalize somehow to something in
    numbertheory proper---Tyger says he knows something of
    numbertheory so he might know something this relates to
     
  10. Jul 11, 2003 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, it's easy to show that the decimal expansion of any fraction with prime denominator p (other than 2 and 5) repeats every n digits if and only if p is a factor of (10^n - 1)

    Also, it's clear that p is a factor of 10^(p-1) - 1 (via Fermat's little theorem)


    Therefore, a prime p is cyclic if and only if the smallest positive integer x such that 10^x = 1 (mod p) is x = p - 1.

    One can also see that it is sufficient to check only factors of p - 1 (proof available upon request).


    I don't see an easy way to get any better than that.


    edit: used ^ instead of superscripts because the superscripts were barely perceptible for some reason
    edit: fixed a mistake
     
    Last edited: Jul 11, 2003
  11. Jul 11, 2003 #10
    marcus,
    I'm really glad you're taking a close look at this, and I guess you might eventually find the answer.
    I have really no idea what's behind this, I just have been fiddling about with a calculator for some time.
    All I know is, the next cyclic number is 31. I have not found out so far the 1000...1 which is divided by 31. But I'm sure there exists one.
    Another thing: I guess most primes are cyclic, and exceptions will be very rare. Here's what we got so far (cyclic=red):
    2,3,5,7,11,13,17,19,23,29,31,37,...
     
  12. Jul 11, 2003 #11
    Yes, please.
     
  13. Jul 11, 2003 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ok.


    The equation

    E := 10^x = 1 (mod p) (x a nonnegative integer)

    has at least one nonzero solution, so it must have a minimum nonzero solution... call it n.

    Now, suppose m is a solution of E. We may write

    m = a n + b where a and b are positive integers, and b is less than n.

    Then:

    10^b = 10^(m - an) = 10^m / 10^(an) = 1 / (10^n)^a = 1 / 1^a = 1 (mod p)

    So b is a solution to the equation to E that is smaller than n... therefore b must be zero (because of the minimality of n). Thus m = a n, proving that n divides m.


    Since p - 1 is a nonzero solution to E, n must be a factor of p - 1... so it is sufficient to test only the factors of p - 1 to check if they are a solution to E.




    BTW, I did misspeak; I didn't mean to say that the only possible solutions are factors of p - 1, just that the smallest solution must be a factor of p - 1.
     
  14. Jul 11, 2003 #13

    marcus

    User Avatar
    Science Advisor
    Gold Member
    2015 Award
    Dearly Missed

    this is neat!
    I really like the casual way this came up and Hurkyl nailed it!
     
  15. Jul 11, 2003 #14

    marcus

    User Avatar
    Science Advisor
    Gold Member
    2015 Award
    Dearly Missed

    it often helps me to rephrase things
    if I understand H. then p fails to be cyclic only
    in those cases where there exists an x < p-1
    such that
    p divides 10x -1

    and if it is going to fail to be cyclic then there will be
    some x which is a divisor of p-1 and for which that is true
    so one only has to check the divisors of p-1 (H. says)


    and arcnets says 11 fails to be cyclic

    so there must be some x divisor of 10, like 2 or 5,
    for which
    11 divides 10x -1

    good, 11 divides 99

    and arcnets says 13 fails to be cyclic

    so there must be some x divisor of 12, like 2, 3, 4, 6,
    for which
    13 divides 10x -1

    By jove! 13 does in fact divide 999,999

    this is so nice I must do one more:
    and arcnets says 37 fails to be cyclic

    so there must be some x divisor of 36, like 2, 3, 4, 6, 9, 12, 18,
    for which
    37 divides 10x -1

    And pleasantly enough, 37 does divide 999
    since it goes into it 27 times.
     
  16. Jul 12, 2003 #15
    I've been pretty busy

    the last three days and didn't get a chance to join this topic but I see things have progressed nicely.

    Euler, who developed many deep proofs in number theory, was inordinately fascinated by the fairly trivial problem of "repeating fractions" as they are known. Basically every prime has a repeating fraction in every base number system, except those that factor the base, e.g. 2 & 5, for base ten.

    Most of the proofs given are related to the proof that np&minus;n is factorable by p if p is prime. Euler proved this by proving the case for n=2 and using the method of ascent for other cases, but if you represent n as (1+1+1+....+1) and use polynomial expansion you can prove it in one step.
     
  17. Jul 12, 2003 #16
    I can see now that

    I was misunderstanding what you meant by cyclic, which is different from just repeating. I see that the number of cyclic primes and noncyclics is about the same. Does this mean another famous conjecture is in the works? The arcnets conjecture?
     
  18. Jul 12, 2003 #17

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Running a quick program, I find that of the first 9592 primes (aka those less than 100,000), 3617 are cyclic and 5975 are not.
     
  19. Jul 13, 2003 #18
    Interesting. So my first guess (most primes are cyclic) is obviously wrong.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: 'cyclic' primes
  1. Cyclic Groups (Replies: 6)

  2. Cyclic Rule (Replies: 1)

  3. Cyclic codes (Replies: 4)

  4. Prime numbers (Replies: 8)

Loading...