3 ms·

That Wikipedia article on repeating decimals is probably where I started looking into it, but the article is somewhat weird. For many problems Wikipedia article

That Wikipedia article on repeating decimals is probably where I started looking into it, but the article is somewhat weird. For many problems Wikipedia articles say we know this and that but those other things are still unknown, this article has a lot of information but does not talk about unknown things at all. The length of the repeating fractional part of 1 / n divides φ(n)...and then nothing. Is this all we know or is there more but just not in this article? I still remember that quite well because that was probably the first and only time that I was unable to find someone stating that we do not know any better, and not only the Wikipedia article but everywhere I looked there was no such statement to be found. I eventually gave up after a couple of evenings but it obviously kept stuck somewhere in my mind and that is why I wrote the initial comment.

jcranmer 9y ago
MathWorld is often a decent resource for finding this kind of information: <http://mathworld.wolfram.com/DecimalPeriod.html> http://mathworld.wolfram.com/DecimalPeriod.html>, but it's often difficult to arrive at those pages if you don't have any idea where to start.
- yorwba 9y ago
  There's an extra > at the end of your link.
- danbruc 9y ago
  I certainly also looked through MathWorld but I failed to make some - in hindsight - rather obvious connections or did not pay enough attention. I certainly knew what the discrete logarithm problem is and that it is hard but I did not realize until a few minutes ago that finding the multiplicative order is just that only with a different name. And now being aware of that the MathWorld article spells exactly this out in a way that it seems impossible to miss.
yorwba 9y ago
The repeating digits in the fractional part are essentially the output of a linear congruence random number generator. Finding the period is almost the same as determining the order of an element of the state space, but by chance you might get a shorter repetition that fits into the longer one. Finding the order of an element in a group is a hard problem on par with factoring http://mathworld.wolfram.com/GroupOrder.html http://mathworld.wolfram.com/GroupOrder.html I'm not sure about cases where the state space doesn't form a multiplicative group, but I doubt that it gets much easier.

jcranmer 9y ago

MathWorld is often a decent resource for finding this kind of information: <http://mathworld.wolfram.com/DecimalPeriod.html> http://mathworld.wolfram.com/DecimalPeriod.html>, but it's often difficult to arrive at those pages if you don't have any idea where to start.

yorwba 9y ago
There's an extra > at the end of your link.
danbruc 9y ago
I certainly also looked through MathWorld but I failed to make some - in hindsight - rather obvious connections or did not pay enough attention. I certainly knew what the discrete logarithm problem is and that it is hard but I did not realize until a few minutes ago that finding the multiplicative order is just that only with a different name. And now being aware of that the MathWorld article spells exactly this out in a way that it seems impossible to miss.

yorwba 9y ago

The repeating digits in the fractional part are essentially the output of a linear congruence random number generator. Finding the period is almost the same as determining the order of an element of the state space, but by chance you might get a shorter repetition that fits into the longer one. Finding the order of an element in a group is a hard problem on par with factoring http://mathworld.wolfram.com/GroupOrder.html http://mathworld.wolfram.com/GroupOrder.html I'm not sure about cases where the state space doesn't form a multiplicative group, but I doubt that it gets much easier.