1

Which is the less "b" natural number, for which the less period of "1/b" is 7?

I have already tried this way:

I have the following formula: 10^i ≡ 1 (mod b), where "i" is the less period of "1/b". So I replaced this "i" with 7 (b | 10^7 - 1), and calculated the unknown "b" this way. The solution for "b" would be 239, but I got this only for the fourth time with the above formula. Can you please help me with an another, faster algorithm to calculate this "b"?

Thanks in advance!

mrsbean
  • 11
  • 1
    I don't think there is a faster way than this. There are observations which reduce the number of primes you have to test as potential factors. – Mark Bennet Jun 17 '20 at 08:55
  • 3
    $10^7-1 = 3^2\cdot 239\cdot 4649$, $3$ and $9$ clearly don't fit as the period will be $1$. – Alexey Burdin Jun 17 '20 at 08:59
  • Factoring $10^7-1$ (in general $10^n-1$) is the fastest way. Even more inefficient would be to determine the order of all primes upto $10^7$ (in general $10^n$). If $n$ is a prime (like here $7$) , the prime factors have the form $k\cdot n+1$, which allows to speed up the trial division to find small factors. – Peter Jun 17 '20 at 09:32
  • Yes, I meant "the least". – mrsbean Jun 17 '20 at 10:03

0 Answers0