Uncovering the Rule of 'Cyclic' Primes

In summary: I think this works!so we now know that 11 and 13 are NOT cyclic---that is, they do not divide a repunit (string of 1's) ------and we have a simple formula for the cyclic primes:they are those p which divide a repunitand we also know the noncyclic primes:they are the ones that divide no repunitI hope this is right!I hope this is right!Oh, it's right. :) It's not hard to
  • #1
arcnets
508
0
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?
 
Mathematics news on Phys.org
  • #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..
 
  • #3
I think by "cyclic" he means that the period of the decimal expansion of p has length p-1.
 
  • #4
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
 
  • #5


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
 
  • #6


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 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 don't have a proof so must be cautious
 
Last edited:
  • #7
Thanks, marcus!
The next one is 29.
29 divides 100,000,000,000,001
Seems to work!
 
  • #8
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 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
 
  • #9
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:
  • #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,...
 
  • #11
Originally posted by Hurkyl
(proof available upon request).
Yes, please.
 
  • #12
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.
 
  • #13
this is neat!
I really like the casual way this came up and Hurkyl nailed it!
 
  • #14
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.
 
  • #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.
 
  • #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?
 
  • #17
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.
 
  • #18
Interesting. So my first guess (most primes are cyclic) is obviously wrong.
 

1. What are cyclic primes?

Cyclic primes are prime numbers that, when their digits are shifted to the right or left, the resulting numbers are also prime. For example, the number 197 is a cyclic prime because 197, 971, and 719 are all prime numbers.

2. How many cyclic primes are there?

The number of cyclic primes is infinite, but they become increasingly rare as the number of digits in the prime increases. As of 2021, the largest known cyclic prime has 179,424 digits.

3. What is the significance of studying cyclic primes?

Studying cyclic primes can help us better understand the distribution of prime numbers and their patterns. It also has potential applications in cryptography and computer science.

4. How are cyclic primes identified?

Cyclic primes can be identified by using algorithms and computer programs that check the primality of numbers and their shifted digits. The discovery of new cyclic primes relies heavily on advancements in computing power.

5. Are there any other types of cyclic numbers?

Yes, there are other types of cyclic numbers besides primes. For example, cyclic composite numbers are numbers that, when their digits are shifted, the resulting numbers are all composite. There are also cyclic Harshad numbers, which are cyclic numbers that are divisible by the sum of their digits.

Similar threads

  • General Math
Replies
7
Views
1K
  • General Math
Replies
24
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
751
  • General Math
Replies
14
Views
3K
  • Precalculus Mathematics Homework Help
Replies
14
Views
1K
  • General Math
Replies
4
Views
876
Replies
1
Views
2K
Replies
9
Views
2K
  • General Discussion
Replies
4
Views
2K
Back
Top