Period fraction 966

Find minimal integer number N N , that period of fraction 1 N \frac{1}{N} is 966 966 .

Give N N , as answer.


The answer is 2021.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Patrick Corn
Jan 7, 2021

It's well-known that if gcd ( 10 , N ) = 1 , (10,N) = 1, the period of 1 N \frac1{N} is the multiplicative order of 10 10 mod N N , i.e. the smallest positive exponent k k such that 1 0 k 1 10^k \equiv 1 mod N . N. I'm not sure if there is an obvious way without brute force to enumerate the N N for which the multiplicative order of 10 10 mod N N is 966 , 966, but a simple Python loop solved the problem immediately. I get the first five solutions to be 2021 , 2303 , 5969 , 5977 , 6063. 2021, 2303, 5969, 5977, 6063. So the answer is 2021 . \fbox{2021}.

(If N N is not coprime to 10 , 10, there will be some digits before the repeating part, but the period will be the same as the period of N / g c d ( 10 , N ) , N/{\rm gcd}(10,N), so we get the minimal N N when that gcd is 1. 1. )

Thanks for attention. I use Python. First solutions are

2021,2303 ,4042 ,4606 ,5969 ,5977 ,6063,6769,6811 ,6909, 8084,9212 ,10105,11515 ,11938,11954,12126,12571,13538,13573, 13622,13818,14147, 16168,17653,17907,17931 ,18189,18424,20210, 20287, 20307,20433,20727,...

Happy New Year!!!

Yuriy Kazakov - 5 months ago

Periods of mod p are always a factor of (p-1)/k for some arbitrary k. In this problem 966 factors into 2 3 7 23. So solving this problem your goal is to find the smallest few numbers which have periods in some combination of these products. You'd have to do a bit of an exhaustive search (and an out of the way step) to find 2021 = 43 47 = (42+1)(46+1)=(2 3 7+1)(2*23+1).

You can also find cases where there are \phi(p^n)=(p-1)p^{n-1}. In the case of 2303 = 7^2 47 we find \phi(2023)=(6 7)*46. A similar period setup to the previous example.

Finding a minimal is a bit more on the exhaustive side doing this by hand if you don't know which primes with periods p-1. This problem is an example of RSA encryption where the public key of 966 can apply to many different modulus.

Jaleb Jay - 2 weeks, 1 day ago

Log in to reply

Fine result - “ Periods of mod p are always a factor of (p-1)/k for some arbitrary k”. Thanks for attention.

Yuriy Kazakov - 2 weeks, 1 day ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...