Prime Divisibility

*Claim 1: * If $k^m \equiv 1 \pmod{n}$ for some $m \in \mathbb{N}$ , then $\text{ord}_n (k)$ must divide $m$ .

*Proof: * Write $m = a \times \text{ord}_n (k) + b$ , where $a, b \in \mathbb{Z}^+$ and $0 \leq b < \text{ord}_n (k)$ by the division algorithm. Note that $\begin{array}{lrcl} & k^m & \equiv & 1 \pmod{n} \\ \implies & k^{a \times \text{ord}_n (k) + b} & \equiv & 1 \pmod{n} \\ \implies & \left( k^{\text{ord}_n (k)} \right) ^ a \times k^b & \equiv & 1 \pmod{n} \\ \implies & 1^a \times k^b & \equiv & 1 \pmod{n} \\ \implies & k^b & \equiv & 1 \pmod{n} \end{array}$ However, $b>0$ contradicts the minimality of $\text{ord}_n (k)$ . The only possible value of $b$ , thus, is $0$ . It follows that $\text{ord}_n (k)$ divides $m$ . $\blacksquare$

*Claim 2: * Let $p$ be any prime. For all integers $n$ between $2$ and $p-2$ (inclusive), $p \mid 1^n + 2^n + \cdots + (p-1)^n .$

*Proof: * On the contrary, assume there exists an integer $n$ between $2$ and $p-2$ such that $p$ doesn't divide $1^n + 2^n + \cdots + (p-1)^n$ . WLOG let $n$ be the smallest positive integer satisfying the property. It is well known that for all $n, p \in \mathbb{N}$ , $\sum \limits_{k=1}^{n} \binom{n+1}{k} \left( 1^k + 2^k + \cdots + p^k \right) = (p+1)^{n+1} - 1.$ So, $\sum \limits_{k=1}^{n-1} \binom{n+1}{k} \left( 1^k + 2^k + \cdots + p^k \right) + \dbinom{n+1}{n} \left( 1^n + 2^n + \cdots + p^n \right) = (p+1)^{n+1} - 1.$ By our assumption, $p \left. \right | \sum \limits_{k=1}^{n-1} \binom{n+1}{k} \left( 1^k + 2^k + \cdots + p^k \right) ,$ since $n$ is the smallest positive integer such that $1^n + 2^n + \cdots + p^n$ is a multiple of $p$ . Also note that $(p+1)^{n+1} \equiv 1^{n+1} - 1 \equiv 0 \pmod{p}$ . It follows that $p$ divides $\dbinom{n+1}{n} \left( 1^n + 2^n + \cdots + (p-1)^n \right)$ . But since $n \leq p-2$ , $\gcd (n+1, p) = 1$ and hence $p \left. \right | 1^n + 2^n + \cdots + (p-1)^n$ , which is a contradiction. $\blacksquare$

By FLT, $n^{36096} \equiv 1 \pmod{36097}$ whenever $\gcd (n, 36097) = 1$ . By claim 1, it follows that $\text{ord}_{36097} (k)$ must divide $36096$ for all $k$ coprime to $36097$ , so $L | 3606$ . Now note that $1^L + 2^L + \cdots + 36096^L \equiv \underbrace{1 + 1 + \cdots + 1}_{36096 \text{ times}} \equiv 36096 \pmod{36097}.$ By claim 2, $L$ cannot be less than $36096$ . Hence $L= 36096$ , and $L+1= 36097$ , whose last three digits are $\boxed{097}$ .

What the problem describes is exactly Carmichael's Function $\lambda$ (Reduced Totient Function) . And $\lambda(36097)=\phi(36097)$ , the Euler Totient function, because $36097$ is a power of an odd prime.

Euler's Totient function $\phi(36097)=36096$ , so $L=36096+1$ with last three digits $\boxed{097}$ .

From basic group theory, we know that $(\mathbb{Z}/p)^\times$ is a cyclic group of order $p-1$ for prime $p$ . That is, the generator of the group has order $p-1$ . Since the order of every element divides the order of the generator, the least common multiple of all of the orders must be $p-1$ .

Read the hints! 36097 is prime, so by FLT anything to the 36096th power is 1 mod 36097. it is known that the order divides 36096 in this case, but it clearly can't be more than 36096 because 36096 works. We must have a primitive root by some theorem that I don't know how to prove, so 36096 is the desired LCM.