# Prime Divisibility

For coprime positive integers $n$ and $k$, we define $\text{ord}_n (k)$ to be the smallest positive integer such that $k^{\text{ord}_n (k)} \equiv 1 \pmod{n}$.

Let $L= \text{lcm} \left \{ \text{ord}_{36097} (1), \text{ord}_{36097} (2) , \cdots , \text{ord}_{36097} (36096) \right \}.$ Find the last three digits of $L+1$.

Details and assumptions

• To put it in words, $L$ is the smallest positive integer which is a multiple of all of the following numbers: $\text{ord}_{36097}(1), \text{ord}_{36097} (2) , \cdots , \text{ord}_{36097} (36096) .$

• You may use the fact that $36097$ is a prime.

• Even though $1^0 \equiv 1 \pmod{36097}$, $\text{ord}_{36097} (1) \neq 0$, since the order is defined to be positive. In this case, $\text{ord}_{36097} (1) = 1$.

×