1377. How Long Until It Comes Back To One
For each query print the smallest k with k ≥ 1 and
a^k ≡ 1 (mod p), where p is prime and 1 ≤ a ≤ p-1.
a = 2, p = 7 -> 3 2, 4, 1
a = 3, p = 7 -> 6 3, 2, 6, 4, 5, 1
a = 6, p = 7 -> 2 6, 1
Such a k always exists, because a^(p-1) ≡ 1 by Fermat's little theorem
whenever p is prime and a is not a multiple of p. So the question is
never whether, only how small.
## What most people try first
Multiply by a repeatedly and count until the value returns to 1. It is
correct and it is O(k), and k can be as large as p - 1, which is
10^9. With 100 queries that is 10^11 multiplications.
## The answer always divides p-1
This is the fact that turns the problem from a scan into a search. The powers
of a form a cycle of length k, and a^(p-1) is 1, so p-1 lands on the
start of the cycle, which can only happen when k divides p-1. So the
candidates are exactly the divisors of p-1, and there are at most 1344 of
them below 10^9.
## Divide p-1 down, one prime factor at a time
Enumerating every divisor works, but there is a shorter route. Start with
k = p-1, which always satisfies the condition, and then for each prime factor
f of p-1:
while k is divisible by f and a^(k/f) = 1 mod p:
k = k / f
p = 7, p-1 = 6 = 2 * 3, a = 2
f = 2: a^3 = 1 -> k = 3
f = 3: a^1 = 2, not 1 -> stop
answer 3
## Why it is correct
The loop keeps the invariant that a^k = 1, since it only moves to k/f after
checking that. So the final k is a valid exponent. It is also the smallest:
suppose the true order d were a strict divisor of the final k. Then
k/d > 1 has some prime factor f, and f divides k, and a^(k/f) is 1
because d divides k/f. But the loop would have taken that step for f, so
it cannot have finished. Hence no such d exists and k is the order.
Factorising p-1 is trial division up to its square root, about 31623 steps
for p near 10^9.
## Overflow
Every multiplication inside the fast power is two values below p, which
reaches 10^9 + 7, so the products reach 10^18. That needs a signed 64-bit
integer: 32 bits stops at 2147483647 and a 32-bit build reports p-1 for
a = p-1 instead of 2. JavaScript must avoid a plain Number above 2^53.
## Cost
O(sqrt(p) + log(p)^2) per query, dominated by factorising p-1.
Constraints - `1 ≤ q ≤ 100` - `2 ≤ p ≤ 1000000007`, and `p` is prime - `1 ≤ a ≤ p - 1`
Input
The first line contains q, the number of queries.
Each of the next q lines contains a and the prime p.
Output
For each query print one line: the smallest k ≥ 1 with a^k congruent to 1 modulo p.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.