After some reading I can put bounds on the answer. There is a theorem that says that for all a there is some r <= N s.t. a^(x + r)%N = a^x%N where r is the cycle length and x is the maximum number of powers of primes in the factorisation of N (1000 = 2³5³, so x = 3). The Carmichael function for 1000 is 100 which gives the maximum cycle length as 100, but it can be smaller. So a possible answer is A = 103, B = 3 for C = 106. I've been looking at (11^n)%1000 = 1 which can be solved using the Binomial theorem, using {n, m} to mean the binomial coefficient n!/(n-m)!m! :
(10 + 1)^n%1000 = sum(m = 0 ... n, {n, m} (10)^m%1000)%1000
Terms in m>2 vanish since they are multiples of 1000, so
(10 + 1)^n%1000 = [1 + 10n + 100 * ½ n(n - 1)]%1000
= [1 - 40n + 50n²]%1000
This is equal to 1 when 50n² = 40n or if the individual terms are zero mod 1000. 50n²=40n if n = 0 (11^0 = 1) or if n = 4/5. So we need 50n² %1000 = 0 and 40n%1000 = 0. If a%1000 = 0, a has three factors of 2 and three of 5. 50 has 2 prime factors of 5 and 1 of 2, so the smallest square that has the missing factors is n² = 100, if 40n%100 = 0, then there are two factors of 5 missing which means that n = 25. The least common multiple of 10 and 25 is 50 which is the cycle time of (11^50)%1000 = 1.
The cycle time is the least common multiple of 50 and whatever the cycle time for (2^N)%1000 is.
Recreational Mathematics Problem 2
06 Nov '14 00:27
Back to Top