Colossal

次の命題(☆)が成り立ちます。

☆: 任意の整数$a$, 正整数$m$, $\phi(m)\leq b$なる整数$b$について、$a^b\equiv a^{(b\bmod \phi(m)) + \phi(m)}\pmod m$が成り立つ。

$\phi(m)$は$O(\sqrt m)$、累乗は$O(\log M)$などで計算することができ、本問は$O(\sqrt M)$で解くことができました。

証明

まず、以下の補題を示します。
補題: $\phi(m)\leq c$なる整数$c$について、$a^c\equiv a^{c+\phi(m)}\pmod m$が成り立つ。

1.補題

$m$の素因数について、$m_1$を$a$と互いに素な成分の総積、$m_2$を$a$と共通する素因数のみからなる成分の総積とする。

• $m_1$について、オイラーの定理から$a^{\phi(m_1)}\equiv 1\pmod{m_1}$。また、$\phi(m_1)\mid\phi(m)$より、$a^{\phi(m)}\equiv 1\pmod{m_1}$であるから、$a^c\equiv a^{c+\phi(m)}\pmod{m_1}$
• $m_2$について、$m_2$の任意の素因数$p$に対してその指数を$k$とすると、$\phi(m)\geq\phi(p^k)=p^k(1-\frac{1}{p})\geq2^{k-1}\geq k$が成り立つため、$a^c\equiv a^{c+\phi(m)}\equiv 0\pmod{m_2}$

$m_1\perp m_2, m_1\cdot m_2 = m$なる$m_1$、$m_2$それぞれについて$a^{c+\phi(m)}-a^c\equiv 0$であることが示されました。よって、crtから$a^c\equiv a^{c+\phi(m)}\pmod m$です。

2.☆

$b\bmod \phi(m) = r, \lfloor \frac{b}{\phi(m)}\rfloor = q$とすると、補題から $a^b=a^{r+q\phi(m)}\equiv a^{r+(q-1)\phi(m)}\equiv\dots\equiv a^{r+\phi(m)}\pmod m$
ここで、$r=b\bmod\phi(m)$なので、$a^b\equiv a^{(b\bmod \phi(m)) + \phi(m)}\pmod m$が示されました。