**Definitions**
Let $ m, x \in \mathbb{Z} $ with $ 2 \leq m \leq 10^{14} $, $ 1 \leq x < m $, and $ \gcd(x, m) = 1 $.
Let $ R = \{0, 1, \dots, m-1\} $ be the set of rooms.
The $ x $-mouse moves according to the transformation $ f: R \to R $, $ f(i) = (i \cdot x) \mod m $.
**Constraints**
- $ \gcd(x, m) = 1 $
**Objective**
Find the minimum number of traps (i.e., minimum size of a subset $ T \subseteq R $) such that, for every possible starting room $ i \in R $, the trajectory $ i, f(i), f(f(i)), \dots $ eventually enters $ T $.
Since $ \gcd(x, m) = 1 $, multiplication by $ x $ modulo $ m $ is a permutation of $ R $, and the dynamics partition $ R $ into disjoint cycles. The mouse, starting from any room, will follow a unique cycle. To catch the mouse regardless of its starting position, at least one trap must be placed in each cycle.
Thus, the minimum number of traps equals the number of distinct cycles in the functional graph of $ f(i) = (i \cdot x) \mod m $.
Note: The element $ 0 $ forms a fixed point (cycle of length 1), since $ 0 \cdot x \equiv 0 \mod m $.
For $ i \in \{1, 2, \dots, m-1\} $, the transformation $ i \mapsto i \cdot x \mod m $ acts on the multiplicative group $ \mathbb{Z}_m^* $, which has order $ \phi(m) $. Since $ \gcd(x, m) = 1 $, $ x $ is an element of $ \mathbb{Z}_m^* $, and the orbits under multiplication by $ x $ correspond to the cosets of the cyclic subgroup $ \langle x \rangle \leq \mathbb{Z}_m^* $.
The number of cycles in $ \mathbb{Z}_m^* $ under multiplication by $ x $ is $ \frac{\phi(m)}{d} $, where $ d $ is the multiplicative order of $ x $ modulo $ m $.
Therefore, the total number of cycles in $ R $ is:
$$
1 + \frac{\phi(m)}{\operatorname{ord}_m(x)}
$$
where $ \operatorname{ord}_m(x) $ is the smallest positive integer $ d $ such that $ x^d \equiv 1 \pmod{m} $.
However, observe that the entire group $ \mathbb{Z}_m^* $ is partitioned into cycles of equal length $ d = \operatorname{ord}_m(x) $, so the number of such cycles is $ \phi(m)/d $.
But there is a simpler insight: since $ \gcd(x, m) = 1 $, the mapping $ i \mapsto i \cdot x \mod m $ is a permutation of $ R $, and the number of cycles in this permutation is equal to the number of orbits under the action of the cyclic group $ \langle x \rangle $ on $ R $ by multiplication.
Actually, note that $ 0 $ is fixed. For the nonzero elements, the action is on $ \mathbb{Z}_m^* $, and the number of orbits is $ \frac{\phi(m)}{d} $, where $ d = \operatorname{ord}_m(x) $.
Thus, total number of cycles = $ 1 + \frac{\phi(m)}{d} $.
But wait — there is a known result: **When $ \gcd(x, m) = 1 $, the number of cycles in the functional graph of $ i \mapsto i \cdot x \mod m $ is $ \gcd(x-1, m) $?** No, that is not standard.
Let’s reframe.
Actually, consider the orbits under the transformation $ i \mapsto i \cdot x \mod m $.
- $ 0 $ is always a fixed point → 1 cycle.
- For $ i \in \mathbb{Z}_m^* $, the orbit of $ i $ is $ \{ i \cdot x^k \mod m \mid k \in \mathbb{Z} \} $. This is the coset $ i \cdot \langle x \rangle \subseteq \mathbb{Z}_m^* $.
So the number of orbits in $ \mathbb{Z}_m^* $ is the index of $ \langle x \rangle $ in $ \mathbb{Z}_m^* $, which is $ \frac{\phi(m)}{d} $, where $ d = \operatorname{ord}_m(x) $.
Hence, total number of cycles = $ 1 + \frac{\phi(m)}{d} $.
But this is **not** minimal traps needed. We need **one trap per cycle**, so the answer is $ 1 + \frac{\phi(m)}{d} $.
However, note the examples:
**Example 1**: $ m = 4, x = 3 $.
$ \gcd(3,4)=1 $.
Trajectories:
- 0 → 0
- 1 → 3 → 1 → 3 → ... (cycle: 1,3)
- 2 → 2·3 = 6 ≡ 2 mod 4 → fixed point? But $ \gcd(2,4) \ne 1 $, so 2 is not in $ \mathbb{Z}_4^* $.
Wait — we made a mistake. The state space is all $ i \in \{0,1,2,3\} $, and the transformation is $ i \mapsto (i \cdot x) \mod m $. Even if $ \gcd(i,m) \ne 1 $, we still apply the map.
So the state space is $ \mathbb{Z}/m\mathbb{Z} $, and the map is multiplication by $ x $ mod $ m $, with $ \gcd(x,m)=1 $.
This map is **not** a permutation of $ \mathbb{Z}/m\mathbb{Z} $ if $ m $ is composite? Wait — if $ \gcd(x,m)=1 $, then multiplication by $ x $ mod $ m $ **is** a bijection on $ \mathbb{Z}/m\mathbb{Z} $.
Proof: $ x $ invertible mod $ m $ ⇒ multiplication by $ x $ is invertible (multiply by $ x^{-1} $) ⇒ bijection.
So the functional graph is a permutation of $ m $ elements → decomposes into disjoint cycles.
We need the number of cycles in the permutation $ f(i) = (i \cdot x) \mod m $.
We know:
- $ f(0) = 0 $ → cycle of length 1.
- For $ i \ne 0 $, $ f(i) = i \cdot x \mod m $.
But $ \mathbb{Z}/m\mathbb{Z} $ is not a group under multiplication, but we can decompose it via the Chinese Remainder Theorem.
Alternatively, we can use group action: the map $ f $ generates a cyclic subgroup of the symmetric group $ S_m $, and we want the number of cycles in its cycle decomposition.
There is a known formula:
> The number of cycles in the permutation $ i \mapsto a \cdot i \mod m $, with $ \gcd(a,m)=1 $, is equal to $ \sum_{d \mid m} \frac{\phi(d)}{\operatorname{ord}_d(a)} $.
Wait — no.
Actually, here's a better approach from number theory:
The permutation $ f: i \mapsto i \cdot x \mod m $ decomposes into cycles. The length of the cycle containing $ i $ is the smallest $ k > 0 $ such that $ i \cdot x^k \equiv i \mod m $, i.e., $ i(x^k - 1) \equiv 0 \mod m $.
This depends on $ \gcd(i, m) $.
Let $ d = \gcd(i, m) $, then write $ i = d \cdot i' $, $ m = d \cdot m' $, so $ \gcd(i', m') = 1 $. Then:
$$
i \cdot x^k \equiv i \mod m \iff d i' x^k \equiv d i' \mod d m' \iff i' x^k \equiv i' \mod m' \iff x^k \equiv 1 \mod m'
$$
since $ \gcd(i', m') = 1 $.
So the cycle length of $ i $ is the multiplicative order of $ x $ modulo $ m' = m / \gcd(i, m) $.
Thus, the cycle lengths depend on $ \gcd(i, m) $.
Let $ d \mid m $. Consider all $ i \in \{0, 1, \dots, m-1\} $ with $ \gcd(i, m) = d $. There are $ \phi(m/d) $ such $ i $.
For each such $ i $, the cycle length is $ \operatorname{ord}_{m/d}(x) $.
And all such $ i $ lie in cycles of the same length $ \ell_d = \operatorname{ord}_{m/d}(x) $.
So the number of cycles corresponding to $ d $ is $ \frac{\phi(m/d)}{\ell_d} = \frac{\phi(m/d)}{\operatorname{ord}_{m/d}(x)} $.
Therefore, total number of cycles is:
$$
\sum_{d \mid m} \frac{\phi(m/d)}{\operatorname{ord}_{m/d}(x)} = \sum_{d \mid m} \frac{\phi(d)}{\operatorname{ord}_d(x)}
$$
by substituting $ d \to m/d $.
So the answer is:
$$
\boxed{ \sum_{d \mid m} \frac{\phi(d)}{\operatorname{ord}_d(x)} }
$$
But note: when $ d = 1 $, $ \operatorname{ord}_1(x) $ is undefined? But $ m/d = m $, and when $ d = m $, then $ m/d = 1 $, and $ \operatorname{ord}_1(x) = 1 $, since any number mod 1 is 0, and $ x \equiv 0 \mod 1 $, but we define $ \operatorname{ord}_1(x) = 1 $ (trivial group).
Actually, for $ d=1 $, $ \phi(1)=1 $, $ \operatorname{ord}_1(x) = 1 $, so term is 1.
But let’s test with example:
**Example 1**: $ m = 4, x = 3 $
Divisors of $ m = 4 $: $ d = 1, 2, 4 $
- $ d=1 $: $ \phi(1)=1 $, $ \operatorname{ord}_1(3) = 1 $ → term = 1
- $ d=2 $: $ \phi(2)=1 $, $ \operatorname{ord}_2(3) $: 3 mod 2 = 1, so $ 3^1 \equiv 1 \mod 2 $ → ord = 1 → term = 1
- $ d=4 $: $ \phi(4)=2 $, $ \operatorname{ord}_4(3) $: 3^1 = 3 ≢ 1 mod 4, 3^2 = 9 ≡ 1 mod 4 → ord = 2 → term = 2/2 = 1
Total = 1 + 1 + 1 = 3 → matches example (traps in 0,2,3)
**Example 2**: $ m = 5, x = 2 $
Divisors: 1,5
- $ d=1 $: $ \phi(1)/\operatorname{ord}_1(2) = 1/1 = 1 $
- $ d=5 $: $ \phi(5)=4 $, $ \operatorname{ord}_5(2) $: 2^1=2, 2^2=4, 2^3=3, 2^4=1 → ord=4 → term = 4/4=1
Total = 1 + 1 = 2 → matches (trap in 0 and one other)
Perfect.
So the answer is:
**Objective**
Compute:
$$
\sum_{d \mid m} \frac{\phi(d)}{\operatorname{ord}_d(x)}
$$
where $ \operatorname{ord}_d(x) $ is the multiplicative order of $ x $ modulo $ d $, defined as the smallest positive integer $ k $ such that $ x^k \equiv 1 \pmod{d} $, and for $ d=1 $, define $ \operatorname{ord}_1(x) = 1 $.
Note: Since $ \gcd(x, m) = 1 $, and $ d \mid m $, then $ \gcd(x, d) = 1 $, so $ x $ is invertible mod $ d $, and $ \operatorname{ord}_d(x) $ is well-defined for all $ d \mid m $.
Thus, the minimum number of traps required is:
$$
\boxed{ \sum_{d \mid m} \frac{\phi(d)}{\operatorname{ord}_d(x)} }
$$