Uncovering the Rule of 'Cyclic' Primes

[arcnets]

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?

 

[Tyger]

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..

 

[Hurkyl]

I think by "cyclic" he means that the period of the decimal expansion of p has length p-1.

 

[marcus]

Originally posted by arcnets
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?

One condition is that the prime p must
divide the number
10^(p-1)/2 + 1

 

[marcus]

Originally posted by marcus
One condition is that the prime p must
divide the number
10^(p-1)/2 + 1

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

 

[marcus]

Originally posted by marcus
One condition is that the prime p must
divide the number
10^(p-1)/2 + 1

I will try the condition for p = 23
See if 23 divides 10¹¹ + 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 don't have a proof so must be cautious

 

[arcnets]

Thanks, marcus!
The next one is 29.
29 divides 100,000,000,000,001
Seems to work!

 

[marcus]

Originally posted by arcnets
Thanks, marcus!
The next one is 29.
29 divides 100,000,000,000,001
Seems to work!

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 10^p-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

 

[Hurkyl]

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

 

[arcnets]

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,...

 

[arcnets]

Originally posted by Hurkyl
(proof available upon request).

Yes, please.

 

[Hurkyl]

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.

 

[marcus]

this is neat!
I really like the casual way this came up and Hurkyl nailed it!

 

[marcus]

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 10^x -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 10^x -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 10^x -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 10^x -1

And pleasantly enough, 37 does divide 999
since it goes into it 27 times.

 

[Tyger]

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 n^p&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.

 

[Tyger]

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?

 

[Hurkyl]

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.

 

[arcnets]

Interesting. So my first guess (most primes are cyclic) is obviously wrong.