解説

方針・初手

$4$ の累乗をそのまま計算すると大きくなるので、$27$ を法とする合同式で周期を調べる。まず $4^9$ が $27$ で割ると $1$ 余ることを示し、指数を $9$ で整理する。

解法1

まず、$4^9$ を $27$ で割った余りを調べる。

$$ 4^3=64\equiv 10 \pmod{27}

$$

したがって、

$$ 4^9=(4^3)^3\equiv 10^3=1000 \pmod{27}

$$

ここで、

$$ 1000=27\cdot 37+1

$$

より、

$$ 4^9\equiv 1 \pmod{27}

$$

である。

**(1)**

$4^7$ については、$4^3\equiv 10 \pmod{27}$ を用いて計算する。

$$ 4^7=4\cdot (4^3)^2

$$

より、

$$ 4^7\equiv 4\cdot 10^2=400 \pmod{27}

$$

ここで、

$$ 400=27\cdot 14+22

$$

だから、

$$ 4^7\equiv 22 \pmod{27}

$$

よって、$4^7$ を $27$ で割った余りは $22$ である。

**(2)**

$4^{31}$ については、$4^9\equiv 1 \pmod{27}$ を用いて指数を小さくする。

$$ 31=9\cdot 3+4

$$

より、

$$ 4^{31}=4^{9\cdot 3+4}=(4^9)^3\cdot 4^4

$$

したがって、

$$ 4^{31}\equiv 1^3\cdot 4^4=4^4 \pmod{27}

$$

さらに、

$$ 4^4=256

$$

であり、

$$ 256=27\cdot 9+13

$$

だから、

$$ 4^{31}\equiv 13 \pmod{27}

$$

よって、$4^{31}$ を $27$ で割った余りは $13$ である。

解説

累乗の余りを求める問題では、底の累乗が $1$ に戻る周期を見つけるのが基本である。

この問題では、

$$ 4^9\equiv 1 \pmod{27}

$$

が成り立つため、指数を $9$ で割った余りに注目すればよい。ただし、（1） の $4^7$ のように指数が周期より小さい場合は、周期で無理に処理するより、$4^3\equiv 10 \pmod{27}$ を利用して直接計算する方が早い。

答え

**(1)**

$22$

**(2)**

$13$